Not Logged In

Near Optimal Hierarchical Path-Finding

Full Text: jogd.pdf PDF

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

University of Alberta Logo AICML Logo