Near Optimal Hierarchical Path-Finding
| Type of publication: | Article |
| Citation: | botea04 |
| Journal: | Journal of Game Development |
| Volume: | 1 |
| Number: | 1 |
| Year: | 2004 |
| Month: | March |
| Pages: | 7-28 |
| Abstract: | The problem of path-finding 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- finding 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 domain- specific 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. |
| Userfields: | date-added={2012-09-23 10:50:23 +0200}, date-modified={2012-09-23 10:50:23 +0200}, project={fremdliteratur}, |
| Keywords: | |
| Authors | |
|
Attachments
|
|
|
Notes
|
|
|
|
|
|
Topics
|
|
|
|
|