A* pathfinding takes too long, shortcuts needed

Question

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?

Answer 1

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?

Answer 2

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.

Answer 3

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.

Answer 4

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