1
\$\begingroup\$

So I have a game where the player can move on a grid 108 X 192 large. It uses a simple A* path-finding algorithm to move. Unfortunately, After 0.03 seconds, it would have only looked at about 300 nodes, meaning that if the end node is blocked from passage, it would take about 2 seconds for it to realize this (A* without optimizations returns failed when the open list is empty, when it has inspected every path and realized there was no solution). And I want at least 20 fps!

I have not used any optimizations, and each point in the grid is a boolean blocked or unblocked. Any ways to speed it up?

For example, in Dota 2 (a popular MOBA), the map is full of trees and cliffs, and is 15,000 game units by 15,000 game units big, but the character starts moving as soon as you click where you want it to go. How do they do that, and is it a simple thing I am missing?

\$\endgroup\$
  • 1
    \$\begingroup\$ Are you sure you need to calculate the path every time? Why not just calculate it every 1-2 seconds, cache the last calculated value, and have the user/AI move according to the last known/good path? \$\endgroup\$ – ashes999 Apr 17 '16 at 17:26
  • \$\begingroup\$ @ashes999 I want the path to be made only once, when the player clicks on the place where they want the sprite to move. It would return the path, which until the player reaches its destination, it moves the x and y until it reaches the next node. Basically, it only generates once. I just want a shortcut to make it so that it takes less than 0.02 seconds, so it runs at a good fps, and not lag when the player clicks. \$\endgroup\$ – Demandooda Apr 17 '16 at 17:35
  • 1
    \$\begingroup\$ Hierarchical nodes. First pass pathfinding of a sparse set of nodes, then only a subset of the entire map surrounding each node's area that you pass through. That might do it. \$\endgroup\$ – Patrick Hughes Apr 18 '16 at 3:12
  • \$\begingroup\$ Dota 2 uses navmesh - param-pam-pam. End of story. \$\endgroup\$ – Candid Moon _Max_ Feb 5 '18 at 14:00
3
\$\begingroup\$

As you yourself have stated, you still didn't have resorted yet to optimizations. So yes, there are many ways to speed that up.

But since you were talking in general terms, I will stick with what I think is the best general guidance for improving path-finding performance: decrease the size of the problem. Or in other words, search less and search smaller.

1a) On the one hand, searching less means assuring that only some agents search paths at a time. But I guess by your answer that you are not struggling with many agents path-finding, so...

1b) ... on the one hand, to search in smaller areas means reducing the possible paths that have to be evaluated in a path-finding step. For that, spatial partitioning is often used. The scene is divided in areas so that the path-finding can be performed in smaller search-spaces at a time. Also, there are search algorithms such as the HPA* and the HAA* that implement inherently a hierarchical path-finding, by partitioning the scene.

The idea of partitioning the space is the following. You will cluster the map into regions. When the agent has to find a path, it will first do path-finding at the higher level, i.e. find from which region to which region it should go. Them, it will find its path within the current region it is in. When it changes the region, then another within-region path-finding will be performed.

For more on that and a nice visualization, see one of the answers to the following question: What is the most appropriate path-finding solution for a very large proceduraly generated environment?

\$\endgroup\$
  • \$\begingroup\$ thank you so much for the answer, and I have been implementing it. But I came across a stumbling block. Let's just say that the player is moving a block to an area, and that blocks off of a region from another. In other words, how do I do this for a dynamic environment? Thank you for any help. \$\endgroup\$ – Demandooda Apr 21 '16 at 23:43
  • \$\begingroup\$ If you want a realistic reaction to a newly blocked location, wait until the "character" (or whatever it is you're moving) gets to the block and realizes that it is there and then run the pathfinder again. If your character is this ominscient being that can see everywhere then first make the steps of the path it's following available outside of the character and whatever is moving blockages around must check to see if it covers a step on that path. If it does affect the current path somehow then force a new path finding so the character can follow it. \$\endgroup\$ – Patrick Hughes Apr 22 '16 at 23:56
3
\$\begingroup\$

300 nodes in 0.03 seconds means only 10,000 nodes per second, which seems rather slow. Before implementing more complicated approaches such as hierarchical partitioning, the first thing I'd do is to optimize the code.

  1. Run the profiler to find out which functions are using the most time. It is often surprising where the time goes, and it is a waste of your time to optimize something you think is slow when it turns out not to be the slow part after all.
  2. Check the data structures being used. You should have no loops through the open/closed sets! The open set is a priority queue, and should use a priority queue data structure, which can find the best node without searching the entire data structure. I usually use a binary heap. The closed set can either be implemented as an internal structure, as a boolean flag on each node, or as an external structure, as a set (hash table or array). I have sample code in C++ and Python (and incomplete C# code) if you want to take a look.
  3. If the end node being blocked is a common problem, connected components (“island id”) is extremely simple and fast to implement. You preprocess the map once. Loop over each node. If it already has an island id, then skip it. If it does not have one, run breadth or depth first search from that node, and mark all visited nodes with the new island id. When you run A* you will first compare island ids. If they are different, you will know right away that there is no path. (Note: this only is useful if all edges are two-way. One-way edges complicate this.)
  4. Only if you're already using good data structures and the system is still too slow would I suggest investigating hierarchies or waypoints or contraction hierarchies or more advanced techniques. A 15000x15000 map may need such things but your 108x192 grid should not.
\$\endgroup\$
  • \$\begingroup\$ You mentioned that a 108x192 grid should not require hierarchies, waypoints, etc. Are you sure? I have been working on an A* algorithm for a few days, and I am pretty sure it is almost as fast as I can make it. I may be able to cut the times in half once more, but that does not feel like enough. In a 15x250 grid, it is taking about 1.5 ms to calculate a single path, on average. 1500 ms for 1000 iterations. Connectivity is only 4, and the path itself is not mazelike at all. Two straight shots. What kind of performance should I be expecting? \$\endgroup\$ – dpaz Dec 5 '17 at 6:20
  • \$\begingroup\$ No, I can't be sure; it will depend on your requirements. But the original post here said it processed 300 nodes in 30 ms, which seems much slower than what you're talking about. For the 1.5ms (which seems good!), how many nodes did it explore in that time? \$\endgroup\$ – amitp Dec 6 '17 at 19:00
  • \$\begingroup\$ 300 nodes ÷ 30ms = 10 nodes / ms. I would expect somewhere between 100 nodes/ms and 1000 nodes/ms with a standard heap data structure and without hierarchies/waypoints. \$\endgroup\$ – amitp Dec 6 '17 at 19:10
  • \$\begingroup\$ I am not sure, and I do not have the code on hand at the moment. The path itself was probably around 400 nodes long, so that is an absolute minimum of 400 nodes processed in 1.5 ms. Based on what you are telling me, that seems quite acceptable for C# on an old i7 920. It makes me feel better about having spent all of my free time outside of work for two days getting it to where it's at. \$\endgroup\$ – dpaz Dec 6 '17 at 19:36
0
\$\begingroup\$

The quickest way to vastly speed up A* is:

The algorithm frequently tests whether a node is in OPEN or CLOSED set. It is vital that this test is O(1). You do not want to traverse the entire set to see if it is in there or not.

Much faster is two booleans for each node, which will tell you if a node is in OPEN or CLOSED set.

This change alone will make your implementation of A* many times faster.

But yes, you do make a good point: if the goal is not reachable, then every node that is reachable will be traversed unfortunately. So unreachable nodes are the most expensive to pathfind for.

\$\endgroup\$
0
\$\begingroup\$

My implementation of A* in C++ finds path to closest position on grid map 256x256 in 26 ms worst case.

You can try Jump Point Search (JPS). It also checks every cell, but works surprisingly about 4 times faster. In my case 7.5 ms.

JSP+ precalculates jump points for every cell on grid map and finds closest path to unreachable position on my map in 0.5 ms.

Also Dota 2 uses wall/obstacle tracing for short paths. It works in continuous space and founded paths are not guaranteed be shortest, but in most cases resulted path looks good. My version finds short paths in just 0.1 ms.

All tests were running on Macbook with i5-4258U. Code can be found here

\$\endgroup\$

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.