I'm currently researching for a summary paper on the different variants of A* search algorithm and how they are used in games and I stumbled across the name HPA*. I've heard that it's much more faster than traditional A* but I don't understand it completely. There's hardly any videos or articles written about it so I tried reading a research paper on it and I'm having trouble grasping it. All I can understand is it divides the huge graph in many smaller segments(divide and rule), it creates clusters(subgrids) and precomputes optimal distance between clusters etc..

I would be grateful to any of you if you helped explain it! Thanks in advance.

  • 2
    \$\begingroup\$ We have lots of past Q&A about HPA* - have you taken a look at those discussions and examples? \$\endgroup\$
    – DMGregory
    Commented May 9, 2021 at 13:14
  • 1
    \$\begingroup\$ Does this answer your question? HAA* / HPA* C++ Algorithm / Help \$\endgroup\$
    – Krupip
    Commented May 9, 2021 at 22:07
  • \$\begingroup\$ @DMGregory I have and the past Q/As are about giving solutions to someone who already knows how HPA* works in detail. \$\endgroup\$ Commented May 17, 2021 at 20:11

1 Answer 1


One of the creators of HAA* (a generalization of HPA*) wrote a very accessible article explaining how it works on aigamedev.com. Unfortunately that site seems to be dead, but fortunately archive.org has the article archived.

I highly recommend reading it, but to summarize: HPA* breaks the map into chunks. In each chunk, you identify the possible entrances/exits to the chunk, and cache the paths/distances between them. You can then use this to create a graph of the chunks which is much smaller and faster to path-find over than the original map.


The paths you find with this method are only near optimal, but (after the initial setup cost) the pathfinding runs much more quickly than plain A*. You can even group the chunks into larger chunks recursively (hence the "H" in "HPA", meaning "Hierarchical") for greater speed benefits.

For more details, see the original paper.

  • \$\begingroup\$ Appreciate your answer. How is the grid really divided into chunks or how is the heuristic evaluated for the hierarchy? \$\endgroup\$ Commented May 17, 2021 at 20:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .