FAST A* WITH ITERATIVE RESOLUTION FOR NAVIGATION
KYLE WALSH, Bikramjit Banerjee · International Journal of Artificial Intelligence Tools · 2010
We argue that A*, the popular technique for path-finding for NPCs in games, suffers from three limitations that are pertinent to game worlds: (a) the grid maps often restrict the optimality of the paths, (b) A* paths exhibit wall-hugging behavior, and (c) optimal paths are more predictable. We present a new algorithm, VRA*, that varies map-resolution as needed, and repeatedly calls A*. We also present an extension of an existing post-smoothing technique, and show that these two techniques together produce more realistic looking paths than A*, that overcome the above limitations, while using significantly less memory and time than A*.