KIT | KIT-Bibliothek | Impressum | Datenschutz

A Comparison of High-level Approaches for Speeding Up Pathfinding

Sturtevant, Nathan R.; Geisberger, Robert

Abstract:
Most games being shipped today use some form of high-level abstraction such as a navmesh or waypoint graph for path planning. These structures can generally be represented in a form which is compact enough to meet the tight memory constraints in a game. But, when such a graph grows too large, finding paths can still be a complex task. This challenge was faced in Dragon Age: Origins and solved by adding an additional level of abstraction. In the last few years a variety of novel approaches have been developed for finding optimal paths through graphs with specific design applications for road networks. Currently these techniques cannot be feasibly applied to the lowest detail of movement possible in a game map, but can be applied to the high-level abstractions which are commonly found in games. In this paper we describe the pathfinding challenge faced before shipping the title Dragon Age: Origins and perform a postmortem analysis on the extended abstraction that was used in comparison to building more advanced heuristics or the use of contraction hierarchies. We show that contraction hierarchies and abstractions have similar overhead and performance and are both useful approaches for high-level planning in games.



Originalveröffentlichung
DOI: 10.1.1.684.4177
Scopus
Zitationen: 20
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Jahr 2010
Sprache Englisch
Identifikator ISBN: 978-157735478-9
KITopen-ID: 1000097649
Erschienen in Proceedings of the 6th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, Palo Alto, CA, October 11-13, 2010
Verlag AAAI Press, Menlo Park, CA
Seiten 76–82
Nachgewiesen in Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page