TY - GEN
T1 - Ultra-fast optimal pathfinding without runtime search
AU - Botea, Adi
PY - 2011
Y1 - 2011
N2 - Pathfinding is important in many applications, including games, robotics and GPS itinerary planning. In games, most pathfinding methods rely on runtime search. Despite numerous enhancements introduced in recent years, runtime search has the disadvantage that, in bad cases, most parts of a map need to be explored, causing a time performance degradation. In this work we explore a significantly different approach to pathfinding, eliminating the need for runtime search. Optimal paths between all pairs of locations are pre-computed. Since straightforward ways to store pre-computed paths are prohibitively expensive even for maps of moderate size, precomputed data are compressed, reducing the memory requirements dramatically. At runtime, pathfinding is very fast, as it requires visiting only the locations on an optimal path. In each location, a quick computation provides the next move along the optimal path. We demonstrate the effectiveness of this approach on Baldur's Gate game maps. The compression factor reaches two orders of magnitude, bringing the memory requirements down to reasonable values. Compared to A* search, the runtime speedup reaches and even exceeds two orders of magnitude. When averaged over paths of similar cost, the speedup reaches a value of 700 in our experiments.
AB - Pathfinding is important in many applications, including games, robotics and GPS itinerary planning. In games, most pathfinding methods rely on runtime search. Despite numerous enhancements introduced in recent years, runtime search has the disadvantage that, in bad cases, most parts of a map need to be explored, causing a time performance degradation. In this work we explore a significantly different approach to pathfinding, eliminating the need for runtime search. Optimal paths between all pairs of locations are pre-computed. Since straightforward ways to store pre-computed paths are prohibitively expensive even for maps of moderate size, precomputed data are compressed, reducing the memory requirements dramatically. At runtime, pathfinding is very fast, as it requires visiting only the locations on an optimal path. In each location, a quick computation provides the next move along the optimal path. We demonstrate the effectiveness of this approach on Baldur's Gate game maps. The compression factor reaches two orders of magnitude, bringing the memory requirements down to reasonable values. Compared to A* search, the runtime speedup reaches and even exceeds two orders of magnitude. When averaged over paths of similar cost, the speedup reaches a value of 700 in our experiments.
UR - http://www.scopus.com/inward/record.url?scp=84869846976&partnerID=8YFLogxK
M3 - Conference contribution
SN - 9781577355397
T3 - Proceedings of the 7th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE 2011
SP - 122
EP - 127
BT - Proceedings of the 7th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE 2011
T2 - 7th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE 2011
Y2 - 10 October 2011 through 14 October 2011
ER -