Hello,

Few days ago I came across this article that talks about Hierarchical Pathfinding [1] [2] and how it can reduce the time it's taken to find a path between two points in a large map by deviding that map into 5x5 chunks and connecting each chunk together. So all you have to do is find the path in that 5x5 chunks and move to the other chunk. At least that's what I understood.

I have had an idea like that a few months back when I was trying to optimize my A* algorithm, but then I found Min Heap algorithm. So I went ahead and implemented that instead. That made all the difference in the world. However my question now is, will there be any further performance improvement implementing Hierarchical Pathfinging algorithm on top of what I have already done using Min Heap? I'm sure there will be but will it be worth the effort?

Keep in mind I'm using a very large maps. Something like 1024x1024 (1,048,576) Nodes. Min Heap already reduced the time taken to find a path a great deal.

Before implementing Min Heap it took to find a path with a map size of 1024x1024 around 15,900ms (diagonal movment not allowed)
After implementing Min heap it is now taking around 908ms to find a path. (diagonal movment not allowed) and 189ms with diagonal movment allowed.

do you think implementing Hierarchical Pathfinding will drop that further by a large margin? Do you think this is a good way to speed up A* even further? do you have an alternative ideas?

900ms for a path search seems slow, even in a 1M node graph... but that's a question for a profiler.


Keep in mind that hierarchical pathfinding is an algorithmic improvement, not a micro-optimization. If you only search 5% as many nodes, you're going to be roughly 20 times faster. There's just no way around the math.

In other words: yes, in your case, implementing a hierarchical search is almost guaranteed to be a good idea.

900ms for a path search seems slow, even in a 1M node graph... but that's a question for a profiler.


Keep in mind that hierarchical pathfinding is an algorithmic improvement, not a micro-optimization. If you only search 5% as many nodes, you're going to be roughly 20 times faster. There's just no way around the math.

In other words: yes, in your case, implementing a hierarchical search is almost guaranteed to be a good idea.

ok then, well I will give it a shot. My apologize i messed up the numbers. It was 15,900ms before min heap and no diagonal movment and 908ms after min heap no diagonal movment and 189ms after diagonal movment. I'm trying to find a path from starting node of Vector2(0, 0) to Vector2(1023, 1023).

Have you tried doing any profiling to see where your biggest bottlenecks are?

Have you tried doing any profiling to see where your biggest bottlenecks are?

Actually I have, but it was so long ago that I don't remember what was the exact bottleneck. I will run another profiler when I get the chance and see what is the biggest bottleneck. I will post it soon.

[Update]

According to the profiler the most intensive task is the search function. From what I can tell I'm searching for way more nodes than I should be. I think it is caused by the hierarchy i'm using. That should be an easy fix.

I will change my heuristic function and will also implement HPA* and see the difference in performance.

Thanks :)

I have a question that I don't fully understand about HPA*. How do you decide which node to pick to create the "Highway" that connects each cluster together?

for example in this graph looking at the first cluster, why did the author pick the nodes that are marked with the blue dot to connect each cluster together? why didn't he pick any other nodes, like the ones marked with a green dot? How do you decide which node to pick?

Also these paths between each cluster, aren't they per-computed?