So I have a graph, roughly grid shaped, that is about 300*300 nodes large. Even at this size, however, traditional a star takes 20 seconds to run in some cases. So I implemented an HPA* algorithm to shorten pathfinding time. HPA* looks somewhat like this, chopping up the graph into small chunks that can be pathed quickely:
The algorithm works by first finding places to put hierarchical nodes along certain sized edges, then, for every node, finding a path between itself and all other nodes that it shares a square with, or cluster. In the image above, this is shows as the red dots as hierarchical nodes, and the red lines as the paths between the hierarchical nodes.
To find the path between all the nodes in a cluster, I used A*. While the paths are not that big between each node, and thus the A* does not take too long, I need to find many, many of them. For my project, I have hundreds of hierarchical nodes, and, therefore, thousands of searches needed to build the hierarchical graph.
This is an annoyance for testing my game, rebuilding the graph whenever I change something in the scene, it is a nightmare when I wan to do dynamic map changes, often taking seconds and even minutes to get it done.
I have tried many things to speed up the build process, such as doing a modified flood fill for every cluster to just see if the hierarchical nodes are connected and that making the distance between the euclidean, sacrificing accuracy. But the modified flood fill was about as slow as A*, and it did not work.
Is there anything to speed up the HPA* build time for dynamic maps, any special algorithms or speedups or shortcuts I need to know? I would be willing to sacrifice a lot of path accuracy for anything to make it faster. Thank you for all your help.
P.S. The problem is with the fact that it has to do hundreds or even, in some cases, thousands of A* pathfinds during the build phase.