HPA* Pathfinding, building the hierarchical graph is too slow

Question

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.

Answer 1

You are generating the graph dynamically right?

Anyway, for each sector you should just do a flood fill for each node to get you the distance between the nodes. This should be enough but you can also get a path using this technique. Also, don't floodfill outside the sector. A couple thousand 4x4 floodfills should not take more then a couple of seconds.

When you dynamically change the map you only need to take account for the sector you changes, you update the cost for the nodes and if a node becomes unreachable you need to sync it with the other sector.

I have a traditional A* traverse a harsh 1024x1024map in less then a second with about 300k iteration steps. So you might have to consider tweaking your algorithm. What data structures you use? I often use a boolean[] as closedlist if you know where to look

if (closedList[connection.getToNode().getIndex()]) continue;
// Direct lookup, no iterations at all!

And then the openlist, I find a TreeMap<Fscore, List<Nodes> very fast but needs some extra attention.

And there might be countless of other bottlenecks in your alghorithm but these two can have the most impact.

Answer 2

It should be possible to only change the subpaths that are affected by the map change.

void updateHPA(List<Change> changes){
    Set<Square> changedSqr = new HashSet<>();
    for(Change ch : changes) {
        Square sq = grid.getSquareOf(ch.getLoc());
        if(changedSqr.contains(sq)) continue;
        changedSqr.add(sq);

        // update paths internal to sq
    }
}