Abstract | ||
---|---|---|
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*. |
Year | DOI | Venue |
---|---|---|
2010 | 10.1142/S0218213010000054 | INTERNATIONAL JOURNAL ON ARTIFICIAL INTELLIGENCE TOOLS |
Keywords | Field | DocType |
AI algorithms, A*, navigation and path-finding | Computer science,Theoretical computer science,Artificial intelligence,restrict,Machine learning,Grid | Journal |
Volume | Issue | ISSN |
19 | 1 | 0218-2130 |
Citations | PageRank | References |
3 | 0.41 | 7 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Kyle Walsh | 1 | 3 | 0.41 |
Bikramjit Banerjee | 2 | 284 | 32.63 |