Near Optimal Hierarchical Path-Finding
- Adi Botea
- Martin Mueller
- Jonathan Schaeffer, Department of Computing Science, University of Alberta
The problem of path-nding in commercial computer games has to be solved in real time, often under constraints of limited memory and CPU resources. The computational effort required to find a path, using a search algorithm such as A*, increases with size of the search space. Hence, path- nding on large maps can result in serious performance bottlenecks. This paper presents HPA* (Hierarchical Path-Finding A*), a hierarchical approach for reducing problem complexity in path-finding on grid-based maps. This technique abstracts a map into linked local clusters. At the local level, the optimal distances for crossing each cluster are pre-computed and cached. At the global level, clusters are traversed in a single big step. A hierarchy can be extended to more than two levels. Small clusters are grouped together to form larger clusters. Computing crossing distances for a large cluster uses distances computed for the smaller contained clusters. Our method is automatic and does not depend on a specific topology. Both random and real-game maps are successfully handled using no domainspecific knowledge. Our problem decomposition approach works very well in domains with a dynamically changing environment. The technique also has the advantage of simplicity and is easy to implement. If desired, more sophisticated, domain-specific algorithms can be plugged in for increased performance. The experimental results show a great reduction of the search effort. Compared to a highly-optimized A*, HPA* is shown to be up to 10 times faster, while finding paths that are within 1% of optimal.
Citation
A. Botea, M. Mueller, J. Schaeffer. "Near Optimal Hierarchical Path-Finding". Journal of Game Development, 1(1), pp 1-22, January 2004.Keywords: | machine learning |
Category: | In Journal |
BibTeX
@article{Botea+al:JournalofGameDevelopment04, author = {Adi Botea and Martin Mueller and Jonathan Schaeffer}, title = {Near Optimal Hierarchical Path-Finding}, Volume = "1", Number = "1", Pages = {1-22}, journal = {Journal of Game Development}, year = 2004, }Last Updated: March 07, 2007
Submitted by AICML Admin Assistant