I am making a simple tile-based 2D game, which uses the A* ("A star") pathfinding algorithm. I've got all working right, but I have a performance problem with the search. Simply put, when I click an impassable tile, the algorithm apparently goes through the entire map to find a route to the impassable tile—even if I'm standing next to it.
How can I circumvent this? I guess I could reduce the pathfinding to the screen area, but maybe I am missing something obvious here?
Some ideas on avoiding searches that result in failed paths altogether:
One of the cheapest ways to effectively finish A* searches faster is to do no searches at all. If the areas are truly impassible by all agents, flood fill each area with a unique Island ID on load (or in the pipeline). When pathfinding check if the Island ID of the origin of the path matches the Island ID of the destination. If they do not match there is no point doing the search - the two points are on distinct, unconnected islands. This only helps if there are truly impassable nodes for all agents.
I limit the upper bound of the maximum number of nodes that can be searched. This helps impassable searches from running forever, but it does mean some passable searches that are very long can be lost. This number needs to be tuned, and it doesn't really solve the problem, but it mitigates the costs associated with long searches.
If what you are finding is that it is taking too long then the following techniques are useful:
Let the search run in a separate thread or a bit each frame so the game doesn't stall out waiting for the search. Display animation of character scratching head or stamping feet, or whatever is appropriate while waiting for the search to end. To do this effectively, I would keep the State of the search as a separate object and allow for multiple states to exist. When a path is requested, grab a free state object and add it to the queue of active state objects. In your pathfinding update, pull the active item off the front of the queue and run A* until it either A. completes or B. some limit of iterations is run. If complete, put the state object back into the list of free state objects. If it hasn't completed, put it at the end of the 'active searches' and move onto the next one. This has the benefit of preventing long searches for agents, such as those that are impassible, from blocking shorter, passable searches for other agents.
Make sure you use the right data structures. Here's how my StateObject works. All of my nodes are pre-allocated to a finite number - say 1024 or 2048 - for performance reasons. I use a node pool that speeds up the allocation of nodes and it also allows me to store indices instead of pointers in my data structures which are u16s (or u8 if I have a 255 max nodes, which I do on some games). For my pathfinding I use a priority queue for the open list, storing pointers to Node objects. It is implemented as a binary heap, and I sort the floating point values as integers since they are always positive and my platform has slow floating point compares. I use a hashtable for my closed map to keep track of the nodes I have visited. It stores NodeIDs, not Nodes, to save on cache sizes. The hashtable is a linear probe table and has the same size as the nodepool, and is allocated only once, when the StateObject is created.
When you first visit a node and calculate the distance to the destination, cache that in the node stored in the State Object. If you revisit the node use the cached result instead of calculating it again. In my case it helps not having to do a square root on revisited nodes. You may find there are other values you can precalculate and cache.
Further areas you could investigate: use two-way pathfinding to search from either end. I have not done this but as others have noted this might help, but is not without it's caveats. The other thing on my list to try is hierarchical pathfinding, or clustering path finding. There is an interesting description in the HavokAI documentation Here describing their clustering concept, which is different than the HPA* implementations described here.
Good luck, and let us know what you find.
AStar is a complete planning algorithm, meaning if there exists a path to the node, AStar is guaranteed to find it. Consequently, it must check every path out of the start node before it can decide the goal node is unreachable. This is very undesirable when you have too many nodes.
Ways to mitigate this:
If you know a priori that a node is unreachable (e.g. it has no neighbors or it is marked UnPassable), return No Path without ever calling AStar.
Limit the number of nodes AStar will expand before terminating. Check the open set. If it ever gets too big, terminate and return No Path. However, this will limit AStar's completeness; so it can only plan paths of a maximum length.
Limit the time AStar takes to find a path. If it runs out of time, exit and return No Path. This limits the completeness like the previous strategy, but scales with the computer's speed. Note that for many games this is undesirable, because players with faster or slower computers will experience the game differently.
If the target has only 6 tiles accessible around it and the origin has 1002 tiles accessible the search will stop at 6 (dual) iterations.
As soon as one search finds the other's visited nodes you can also limit the search scope to the other's visited nodes and finish faster.
Assuming the issue is the destination is unreachable. And that the navigation mesh isn't dynamic. The easiest way to do this is have a much sparser navigation graph (sparse enough that a full run through is relatively quick) and only use the detailed graph if the pathing is possible.
Use multiple algorithms with different characteristics
A* has some fine characteristics. In particular, it always finds the shortest path, if one exist. Unfortunately, you have found some bad characteristics as well. In this case, it must exhaustively search for all possible paths before admitting no solution exists.
The "flaw" you are discovering in A* is that it is unaware of topology. You may have a 2-D world, but it doesn't know this. For all it knows, in the far corner of your world is a staircase which brings it right under the world to its destination.
Consider creating a second algorithm which is aware of topology. As a first pass, you might fill the world with "nodes" every 10 or 100 spaces, and then maintain a graph of connectivity between these nodes. This algorithm would pathfind by finding accessable nodes near the start and end, then trying to find a path between them on the graph, if one exists.
One easy way to do this would be to assign each tile to a node. It is trivial to show that you only need to assign one node to each tile (you can never have access to two nodes which are not connected in the graph). Then the graph edges are defined to be anywhere two tiles with different nodes are adjacent.
This graph has a disadvantage: it does not find the optimum path. It merely finds a path. However, it has now shown you that A* can find an optimum path.
It also provides a heuristic to improve your underestimates needed to make A* function, because you now know more about your landscape. You are less likely to have to fully explore a dead end before finding out that you needed to step back to go forward.
Some more ideas in addition to the answers above:
Cache results of A* search. Save the path data from cell A to cell B and reuse if possible. This is more applicable in static maps and you will have to do more work with dynamic maps.
Cache the neighbours of each cell. A* implementation need to expand each node and add its neighbours to the open set to search. If this neighbours is calculated each time rather than cached then it could dramatically slow down the search. And if you havnt already done so, use a priority queue for A*.
If your map is static you can just have each separate section have there own code and check this first before running A*. This can be done upon map creation or even coded in the map.
Impassable tiles should have a flag and when moving to a tile like that you could opt not to run A* or pick a tile next to it that is reachable.
If you have dynamic maps that change frequently you are pretty much out of luck. You have to way your decision making your algorithm stop before completion or do checks on sections get closed off frequently.
How can I make A* more quickly conclude that a node is impassable?
Profile your Node.IsPassable() function, figure out the slowest parts, speed them up.
When deciding whether a node is passable, put the most likely situations at the top, so that most of the time the function returns right away without bothering to check the more obscure possibilities.
But this is for making it faster to check a single node. You can profile to see how much time is spent on querying nodes, but sounds like your problem is that too many nodes are being checked.
when I click an impassable tile, the algorithm apparently goes through the entire map to find a route to the impassable tile
If the destination tile itself is impassable, the algorithm shouldn't check any tiles at all. Before even starting to do pathfinding, it should query the destination tile to check if it's possible, and if not, return a no path result.
If you mean that the destination itself is passable, but is encircled by impassable tiles, such that there is no path, then it is normal for A* to check the whole map. How else would it know there's no path?
If the latter is the case, you can speed it up by doing a bidirectional search - that way the search starting from the destination can quickly find that there is no path and stop the search. See this example, surround the destination with walls and compare bidirectional vs. single direction.
If only your map doesn't have big continuous areas of unreachable tiles then this will work. Rather than searching the entire reachable map, the path-finding will only search the enclosed unreachable area.
If the areas that the player are connected (no teleports etc.) and the unreachable areas are generally not very well connected, you can simply do the A* starting from the node you want to reach. That way you can still find any possible route to the destination and A* will stop searching quickly for unreachable areas.
when I click an impassable tile, the algorithm apparently goes through the entire map to find a route to the impassable tile — even if I'm standing next to it.
Other answers are great, but I have to point at the obvious - You should not run the pathfinding to an impassable tile at all.
This should be an early exit from the algo:
if not IsPassable(A) or not IsPasable(B) then
return('NoWayExists');
To check for the longest distance in a graph between two nodes:
(assuming all edges have the same weight)
v.v, we'll call it d.u.u,we'll call it w.u and w is the longest distance in the graph.Proof:
D1 D2
(v)---------------------------r_1-----------------------------(u)
|
R | (note it might be that r1=r2)
D3 | D4
(x)---------------------------r_2-----------------------------(y)
y and x is greater!D2 + R < D3D2 < R + D3v and x is greater than that of v and u?u wouldn't have been picked in the first phase.Credit to prof. Shlomi Rubinstein
If you are using weighted edges, you can accomplish the same thing in polynomial time by running Dijkstra instead of BFS to find the furthest vertex.
Please note I'm assuming it's a connected graph. I am also assuming it's undirected.
A* is not really useful for a simple 2d tile based game because if I understand correctly, assuming the creatures move in 4 directions, BFS will achieve the same results. Even if creatures can move in 8 directions, lazy BFS that prefers nodes closer to the target will still achieve the same results. A* is a modification Dijkstra which is far more computationally expensive then using BFS.
BFS = O(|V|) supposedly O(|V| + |E|) but not really in the case of a top down map. A* = O(|V|log|V|)
If we have a map with just 32 x 32 tiles, BFS will cost at most 1024 and a true A* could cost you a whopping 10,000. This is the difference between 0.5 seconds and 5 seconds, possibly more if you take the cache into account. So make sure your A* behaves like a lazy BFS that prefers tiles that are closer to the desired target.
A* is useful for navigation maps were the cost of edges is important in the decision making process. In a simple overhead tile based games, the cost of edges is probably not an important consideration. Event if it is, (different tiles cost differently), you can run a modified version of BFS that postpones and penalizes paths that pass through tiles that slow the character down.
So yeah BFS > A* in many cases when it comes to tiles.
log|V| in A*'s complexity really comes from maintaining that open-set, or the size of the fringe, and for grid maps it's extremely small - about log(sqrt(|V|)) using your notation. The log|V| only shows up in hyper-connected graphs. This is an example where naive application of worst-case complexity gives an incorrect conclusion.
\$\endgroup\$
Commented
Jan 5, 2015 at 7:11