31
\$\begingroup\$

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?

\$\endgroup\$
  • 2
    \$\begingroup\$ Do you know which tiles are impassable or do you just know it as a result of the AStar algorithm? \$\endgroup\$ – user000user Jan 1 '15 at 14:49
  • \$\begingroup\$ How are you storing your navigation graph? \$\endgroup\$ – Anko Jan 1 '15 at 18:31
  • \$\begingroup\$ If you are storing traversed nodes in lists, you might want to use binary heaps to improve speed. \$\endgroup\$ – ChrisC Jan 1 '15 at 20:38
  • \$\begingroup\$ If it is simply too slow I have a series of optimizations to suggest - or are you trying to avoid searches altogether? \$\endgroup\$ – Steven Jan 1 '15 at 22:32
  • 1
    \$\begingroup\$ This question would probably have been better suited to Computer Science. \$\endgroup\$ – Raphael Jan 2 '15 at 6:47

12 Answers 12

44
\$\begingroup\$

Some ideas on avoiding searches that result in failed paths altogether:

Island ID

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.

Limit upper bound

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:

Make it Asynchronous & Limit Iterations

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.

Choose the Right Data Structures

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.

Cache What You Can

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.

\$\endgroup\$
  • \$\begingroup\$ If there are different agents with different rules, but not too many, this can still be generalized fairly efficiently by using a vector of IDs, one per agent class. \$\endgroup\$ – MSalters Jan 2 '15 at 17:29
  • 4
    \$\begingroup\$ +1 For recognizing that the issue is likely barriered-off areas (not just impassible tiles), and that this kind of problem can be solved easier with early load-time calculations. \$\endgroup\$ – Slipp D. Thompson Jan 3 '15 at 4:21
  • \$\begingroup\$ Flood fill or BFS each area. \$\endgroup\$ – wolfdawn Jan 3 '15 at 14:32
  • \$\begingroup\$ Island IDs don't need to be static. There is a simple algorithm which would be suitable in case there is a need to be able to join two separate islands, but it cannot split an island afterwards. Page 8 through 20 in these slides explain that particular algorithm: cs.columbia.edu/~bert/courses/3137/Lecture22.pdf \$\endgroup\$ – kasperd Jan 4 '15 at 17:55
  • \$\begingroup\$ @kasperd of course there is nothing preventing island ids being recalculated, merged at runtime. The point is that the island ids allow you to confirm if a path exists between two nodes quickly without doing astar search. \$\endgroup\$ – Steven Jan 4 '15 at 18:07
26
\$\begingroup\$

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.

\$\endgroup\$
  • 13
    \$\begingroup\$ I would like to point out that changing the mechanics of your game depending on the CPU speed (yes, route finding is a game mechanic) might turn out to be a bad idea because it can make the game quite unpredictable and in some cases even unplayable on computers 10 years from now. So I would rather recommend to limit A* by capping the open set than by CPU time. \$\endgroup\$ – Philipp Jan 2 '15 at 9:49
  • \$\begingroup\$ @Philipp. Modified the answer to reflect this. \$\endgroup\$ – mklingen Jan 2 '15 at 14:41
  • 1
    \$\begingroup\$ Note that you can determine (reasonably efficient, O(nodes)) for a given graph the maximum distance between two nodes. This is the longest path problem, and it provides you with a correct upper bound for the number of nodes to check. \$\endgroup\$ – MSalters Jan 2 '15 at 17:25
  • 2
    \$\begingroup\$ @MSalters How do you do this in O(n)? And what is 'reasonably efficient'? If this is only for pairs of nodes are you not just duplicating work? \$\endgroup\$ – Steven Jan 2 '15 at 18:19
  • \$\begingroup\$ According to Wikipedia, the longest path problem is NP-hard, unfortunately. \$\endgroup\$ – Desty Jan 2 '15 at 21:28
21
\$\begingroup\$
  1. Run a dual A* search from the target node in reverse as well at the same time in the same loop and abort both searches as soon as one is found unsolvable

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ There is more to implementing a bidirectional A-star search than is implied by your statement, including verifying that the heuristic remains admissible under this circumstance. (Links: homepages.dcc.ufmg.br/~chaimo/public/ENIA11.pdf) \$\endgroup\$ – Pieter Geerkens Jan 1 '15 at 18:52
  • 4
    \$\begingroup\$ @StephaneHockenhull: Having implemented a Bidirectional A-* on a terrain map with asymmetric costs, I assure you that ignoring the academic blah-blah will result in faulty path selection and incorrect cost calculations. \$\endgroup\$ – Pieter Geerkens Jan 2 '15 at 22:07
  • 1
    \$\begingroup\$ @MooingDuck: Total number of nodes is unchanged, and each node will still only be visited once, so worst case of map split exactly in half is identical to unidirectional A-*. \$\endgroup\$ – Pieter Geerkens Jan 2 '15 at 22:09
  • 1
    \$\begingroup\$ @PieterGeerkens: In the classic A*, only half the nodes are reachable, and thus visited. If the map is split exactly in half, then when you search bidirectionally, you touch (almost) every node. Definitely an edge case though \$\endgroup\$ – Mooing Duck Jan 2 '15 at 22:24
  • 1
    \$\begingroup\$ @MooingDuck: I mis-spoke; the worst cases are different graphs, but have the same behaviour - worst case for unidirectional is a completely isolated goal-node, requiring that all nodes be visited. \$\endgroup\$ – Pieter Geerkens Jan 2 '15 at 22:26
12
\$\begingroup\$

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.

\$\endgroup\$
  • 6
    \$\begingroup\$ This is good. By grouping tiles into "regions" and first checking if the region your tile is in can be connected to the region the other tile is in, you can throw away negatives much faster. \$\endgroup\$ – Konerak Jan 2 '15 at 8:24
  • 2
    \$\begingroup\$ Correct - generally falls under HPA* \$\endgroup\$ – Steven Jan 2 '15 at 18:21
  • \$\begingroup\$ @Steven Thanks I was sure I wasn't the first person to think of such an approach but didn't know what it was called. Makes taking advantage of preexisting research much easier. \$\endgroup\$ – ClassicThunder Jan 2 '15 at 20:00
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I have reason to believe algorithms like those for Google Maps operate in a similar (though more advanced) manner. \$\endgroup\$ – Cort Ammon Jan 2 '15 at 23:35
  • \$\begingroup\$ Wrong. A* is very much aware of topology, via the choice of admissable heuristic. \$\endgroup\$ – MSalters Jan 3 '15 at 14:44
  • \$\begingroup\$ Re Google, at my previous job we analyzed the performance of Google Maps and found that it couldn't have been A*. We believe they use ArcFlags or other similar algorithms that rely on map preprocessing. \$\endgroup\$ – MSalters Jan 3 '15 at 14:46
  • \$\begingroup\$ @MSalters: That's an interesting fine line to draw. I argue A* is unaware of topology because it only concerns itself with nearest neighbors. I would argue that it is more fair to word that the algorithm generating the admissible heuristic is aware of the topology, rather than A* itself. Consider a case where there is a diamond. A* takes one path for a bit, before backing up to try the other side of the diamond. There is no way to notify A* that the only "exit" from that branch is through an already visited node (saving computation) with the heuristic. \$\endgroup\$ – Cort Ammon Jan 3 '15 at 21:34
  • 1
    \$\begingroup\$ Can't speak for Google Maps, but Bing Map uses Parallel Bidirectional A-star with Landmarks and Triangle Inequality (ALT), with pre-computed distances from (and to) a small number of landmarks and every node. \$\endgroup\$ – Pieter Geerkens Jan 4 '15 at 0:14
2
\$\begingroup\$

Some more ideas in addition to the answers above:

  1. 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.

  2. 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*.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ This is exactly what I was suggesting with an area ID in my answer. \$\endgroup\$ – Steven Jan 2 '15 at 0:47
  • \$\begingroup\$ You could also reduce the amount of CPU/time used if your map is dynamic, but doesn't change often. I.e. you could re-calculate area IDs whenever a locked door is unlocked or locked. Since that usually happens in response to a player's actions, you'd at least exclude locked areas of a dungeon. \$\endgroup\$ – uliwitness Jan 2 '15 at 14:19
1
\$\begingroup\$

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.

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

Do the path-finding backwards.

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.

\$\endgroup\$
  • \$\begingroup\$ This is even slower if the unreachable tiles outnumber the reachable tiles \$\endgroup\$ – Mooing Duck Jan 2 '15 at 19:23
  • 1
    \$\begingroup\$ @MooingDuck The connected unreachable tiles you mean. This is a solution that works with pretty much any sane map design, and it is very easy to implement. I'm not going to suggest anything fancier without better knowledge of the exact problem, like how the A* implementation can be so slow that visiting all the tiles is actually a problem. \$\endgroup\$ – aaaaaaaaaaaa Jan 2 '15 at 21:49
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ The point was to be faster than regular A*. \$\endgroup\$ – Heckel Jan 3 '15 at 21:32
0
\$\begingroup\$

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');
\$\endgroup\$
0
\$\begingroup\$

To check for the longest distance in a graph between two nodes:

(assuming all edges have the same weight)

  1. Run BFS from any vertex v.
  2. Use the results to select a vertex furthest away from v, we'll call it d.
  3. Run BFS from u.
  4. Find the vertex furthest away from u,we'll call it w.
  5. The distance between 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)
  • Lets say the distance between y and x is greater!
  • Then according to this D2 + R < D3
  • Then D2 < R + D3
  • Then the distance between v and x is greater than that of v and u?
  • Then 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.

\$\endgroup\$
  • \$\begingroup\$ I'm not sure I understand this part "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" Can you explain how did you come to the 10k number please? \$\endgroup\$ – Kromster Jan 3 '15 at 21:48
  • \$\begingroup\$ What exactly do you mean by "lazy BFS that prefers nodes closer to the target"? Do you mean Dijkstra, plain BFS, or one with a heuristic (well you've recreated A* here, or how do you select the next best node out of an open set)? That 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\$ – congusbongus Jan 5 '15 at 7:11
  • \$\begingroup\$ @congusbongus This is exactly what I mean. Do not use a vanilla implementation of A* \$\endgroup\$ – wolfdawn Jan 6 '15 at 19:38
  • \$\begingroup\$ @KromStern Assuming you use the vanilla implementation of A* for a tile based game, you get V * logV complexity, V being the number of tiles, for a grid of 32 by 32 it's 1024. logV, being well approximately the number of bits needed to represent 1024 which is 10. So you end up running for a longer time needlessly. Of course, if you specialize the implementation to take advantage of the fact you are running on a grid of tiles, you overcome this limitation which is exactly what I was referring to \$\endgroup\$ – wolfdawn Jan 6 '15 at 19:40

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.