Title :
Partially Precomputed A
Author :
Hewlett, William
Author_Institution :
Dept. of Comput. Sci., Univ. of California Los Angeles, Los Angeles, CA, USA
fDate :
6/1/2011 12:00:00 AM
Abstract :
A* is a commonly used technique for finding shortest paths for navigation in video games. We propose partially precomputed A* (PPA*), which is much faster than A* at runtime, and uses much less memory than completely precalculating all shortest paths with an algorithm such as Floyd-Warshall. At runtime, PPA* is very similar to A*, so it is simple and safe to integrate into existing video game code bases.
Keywords :
computer games; graph theory; Floyd-Warshall algorithm; navigation; partially precomputed A*; shortest path; video games; Approximation algorithms; Communities; Games; Memory management; Navigation; Roads; Runtime; Autonomous agents; path planning; shortest path problem;
Journal_Title :
Computational Intelligence and AI in Games, IEEE Transactions on
DOI :
10.1109/TCIAIG.2011.2111250