DHPA* and SHPA*: Efficient Hierarchical Pathfinding in Dynamic and Static Game Worlds

Authors

  • Alexander Kring Independent Researcher
  • Alex Champandard Independent Researcher
  • Nick Samarin Independent Researcher

Keywords:

pathfinding, hierarchical pathfinding, path finding, path planning, planning

Abstract

In 2004, Botea et al. published the HPA* algorithm (Hierarchical Pathfinding A*), which is the first detailed study of hierarchical pathfinding in games. However, HPA* can be optimized. In this paper, we introduce the DHPA* and SHPA* hierarchical pathfinding algorithms, along with a metric for comparing the dynamic performance of pathfinding algorithms in games. We show that DHPA* searches up to an order of magnitude faster than HPA*, but consumes significantly more memory and produces slightly less optimal paths. The SHPA* algorithm searches up to five times faster than HPA* and consumes less memory, but it also produces slightly less optimal paths, and is only fit for static environments. When comparing the algorithms in dynamic environments, our results show that DHPA* often outperforms HPA*. Unlike many other hierarchical pathfinding algorithms, both solutions presented in this paper maintain a read-only terrain representation during search, which simplifies programming and debugging, and improves multithreaded performance.

Downloads

Published

2010-10-10

How to Cite

Kring, A., Champandard, A., & Samarin, N. (2010). DHPA* and SHPA*: Efficient Hierarchical Pathfinding in Dynamic and Static Game Worlds. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 6(1), 39-44. Retrieved from https://ojs.aaai.org/index.php/AIIDE/article/view/12397