One of the creators of HPA* wrote a very accessible article explaining how HAA* (a generalization of HPA*) 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.

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.