Fast A* With Iterative Resolution for Navigation
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*.
International Journal on Artificial Intelligence Tools
(2010). Fast A* With Iterative Resolution for Navigation. International Journal on Artificial Intelligence Tools, 19(1), 101-119.
Available at: http://aquila.usm.edu/fac_pubs/934