Abstract
Real-time video games are a unique domain for pathfinding and search. Traditional approaches to search have usually assumed static worlds with a single agent. But, in real-time video games there are multiple cooperative and adversarial agents. While the search space in most games is relatively small, algorithms are expected to plan in mere milliseconds. Thus, techniques such as abstraction are needed to effectively reason and act in these worlds. We provide an overview of the research we have completed in this area, as well as areas of current and future work.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Holte, R., Perez, M., Zimmer, R., MacDonald, A.: Hierarchical A*: Searching abstraction hierarchies efficiently. In: AAAI/IAAI, vol. 1, pp. 530–535 (1996)
Botea, A., Müller, M., Schaeffer, J.: Near optimal hierarchical path–finding. Journal of Game Development 1(1), 7–28 (2004)
Sturtevant, N., Buro, M.: Partial pathfinding using map abstraction and refinement. Under Review (2005)
Bulitko, V., Sturtevant, N., Kazakevich, M.: Speeding up learning in real-time search via state abstraction. Under Review (2005)
Bulitko, V., Lee, G.: Learning in real-time heuristic search: A unifying framework. Under Review (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sturtevant, N., Bulitko, V., Buro, M. (2005). Automatic State Abstraction for Pathfinding in Real-Time Video Games. In: Zucker, JD., Saitta, L. (eds) Abstraction, Reformulation and Approximation. SARA 2005. Lecture Notes in Computer Science(), vol 3607. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11527862_34
Download citation
DOI: https://doi.org/10.1007/11527862_34
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-27872-6
Online ISBN: 978-3-540-31882-8
eBook Packages: Computer ScienceComputer Science (R0)