1
\$\begingroup\$

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:

http://aigamedev.com/static/theory/grid-hierarchy.png

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.

\$\endgroup\$
  • \$\begingroup\$ Can you clarify what specific kinds of data structures you're using? Make sure you're not making copies of things you ought to just be passing by reference. For example caching lists of references to nodes not deep copies. Also, I assume you're slowdown is in a release/production build and not a debug build which will kill execution time of algorithms like A*. \$\endgroup\$ – TOM__ Jan 18 '17 at 6:15
  • \$\begingroup\$ @TOM__ This is as good as I thought I could get it. There is a lot of messy code here, and maybe some of it I could do some performance increasing things to. But, generally, I'm looking for time-saving algorithms here. If there is a common performance increase thing I am not doing, however, enlighten me. I'm already using priority queues for A* and following some algorithms on wikipedia and other things. \$\endgroup\$ – Demandooda Jan 18 '17 at 6:22
  • \$\begingroup\$ Here's a link to a Stanford study of optimizing A* heuristics, some of which aid in greedy best-first searches for sub-optimal paths. They can help the aggregate map performance by speeding up all individual searches. \$\endgroup\$ – TOM__ Jan 18 '17 at 15:14
  • \$\begingroup\$ Profile your code - you can't speed up the slow parts until you know where they are. Once you know specifically what's slowing things, you can get specific recommendations on how to improve them; otherwise we're all just taking best guesses. \$\endgroup\$ – Pikalek Jan 18 '17 at 15:40
  • \$\begingroup\$ @Pikalek Ok I will look up how and give more info. I was looking for fast algorithms for making an HPA* graph, but I will do that, and post the results in a few hours. \$\endgroup\$ – Demandooda Jan 18 '17 at 16:01
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Can you link me to c# implementations of a a floodfill that is this fast? I tried to recreate one form the wiki page, and I did not do a good job. (Long story short, it was very slow) \$\endgroup\$ – Demandooda Jan 18 '17 at 20:34
  • \$\begingroup\$ If this works, I will mark you correct, but it may take a couple days at most. \$\endgroup\$ – Demandooda Jan 18 '17 at 20:37
  • \$\begingroup\$ Maybe a SortedDictionary<Fscore, List<Nodes> will do and a regular bool[] as a closedmap. The right data-structure is the key here, you are traversing huge lists a thousands of times. Unfortunately I cannot help you out much with this in C#. \$\endgroup\$ – Madmenyo Jan 18 '17 at 20:42
  • \$\begingroup\$ I didn't read properly, a floodfill is simple. For each node you store each neighboring node with a distance score. Make sure you stay within the sector and stop when you either flooded the whole sector or got all higher level edge nodes. The distance is all you need but you can count back from high to low to find the path to the original node if you want to. \$\endgroup\$ – Madmenyo Jan 18 '17 at 20:48
  • \$\begingroup\$ Is the algorithm from the video I just watched faster than an a star algorithm? BTW, in my game, ever cluster may be bigger. \$\endgroup\$ – Demandooda Jan 18 '17 at 21:10
0
\$\begingroup\$

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
    }
}
\$\endgroup\$
  • \$\begingroup\$ That would be good, except that, if I wan to change a large bridge or another large object, there would be a massive lag spike still. \$\endgroup\$ – Demandooda Jan 18 '17 at 15:17
  • \$\begingroup\$ @Demandooda you can delay the updates of parts of the graph (just clear the graph information of the affected squares in this frame) and defer the update to the next few frames. \$\endgroup\$ – ratchet freak Jan 18 '17 at 15:34
  • \$\begingroup\$ If I get to that point, I would probably do that and mark you correct, or give up an use unity's navmesh. But that sounds like a bit of a messy solution. As I said, I want to do that if there are no other options. \$\endgroup\$ – Demandooda Jan 18 '17 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.