DocumentCode :
1442501
Title :
Partially Precomputed A 
Author :
Hewlett, William
Author_Institution :
Dept. of Comput. Sci., Univ. of California Los Angeles, Los Angeles, CA, USA
Volume :
3
Issue :
2
fYear :
2011
fDate :
6/1/2011 12:00:00 AM
Firstpage :
119
Lastpage :
128
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;
fLanguage :
English
Journal_Title :
Computational Intelligence and AI in Games, IEEE Transactions on
Publisher :
ieee
ISSN :
1943-068X
Type :
jour
DOI :
10.1109/TCIAIG.2011.2111250
Filename :
5708170
Link To Document :
