# A* algorithm very slow

I have an programming a RTS game (I use XNA with C#). The pathfinding is working fine, except that when it has a lot of node to search in, there is a lag period of one or two seconds, it happens mainly when there is no path to the target destination, since it that situation there is more nodes to explore. I have the same problem when the path is shorter but selected more than 3 units (can't take the same path since the selected units can be in different part of the map).

private List<NodeInfo> FindPath(Unit u, NodeInfo start, NodeInfo end)
{
Map map = GameInfo.GetInstance().GameMap;

_nearestToTarget = start;
start.MoveCost = 0;
Vector2 endPosition = map.getTileByPos(end.X, end.Y).Position;
//getTileByPos simply gets the tile in a 2D array with the X and Y indexes
start.EstimatedRemainingCost = (int)(endPosition - map.getTileByPos(start.X, start.Y).Position).Length();
start.Parent = null;

List<NodeInfo> openedNodes = new List<NodeInfo>(); ;
List<NodeInfo> closedNodes = new List<NodeInfo>();

Point[] movements = GetMovements(u.UnitType);

while (!closedNodes.Contains(end) && openedNodes.Count > 0)
{
//Loop in nodes to find lowest cost
NodeInfo currentNode = FindLowestCostOpenedNode(openedNodes);

openedNodes.Remove(currentNode);

Vector2 previousMouvement;

if (currentNode.Parent == null)
{
previousMouvement = ConvertRotationToDirectionVector(u.Rotation);
}
else
{
previousMouvement = map.getTileByPos(currentNode.X, currentNode.Y).Position -
map.getTileByPos(currentNode.Parent.X, currentNode.Parent.Y).Position;
previousMouvement.Normalize();
}

//For each neighbor
foreach (Point movement in movements)
{
Point exploredGridPos = new Point(currentNode.X + movement.X, currentNode.Y + movement.Y);

//Checks if valid move and checks if not if closed nodes list
if (ValidNavigableNode(u.UnitType, new Point(currentNode.X, currentNode.Y), exploredGridPos) &&
!closedNodes.Contains(_gridMap[exploredGridPos.Y, exploredGridPos.X]))
{
NodeInfo exploredNode = _gridMap[exploredGridPos.Y, exploredGridPos.X];
Tile.TileType exploredTerrain = map.getTileByPos(exploredGridPos.X, exploredGridPos.Y).TerrainType;

if(openedNodes.Contains(exploredNode))
{
int newCost = currentNode.MoveCost + GetMoveCost(previousMouvement, movement, exploredTerrain);
if (newCost < exploredNode.MoveCost)
{
exploredNode.Parent = currentNode;
exploredNode.MoveCost = newCost;

//Find nearest tile to the target (in case doesn't find path to target)
//Only compares the node to the current nearest
FindNearest(exploredNode);
}
}
else
{
exploredNode.Parent = currentNode;
exploredNode.MoveCost = currentNode.MoveCost + GetMoveCost(previousMouvement, movement, exploredTerrain);

Vector2 exploredNodeWorldPos = map.getTileByPos(exploredGridPos.X, exploredGridPos.Y).Position;

exploredNode.EstimatedRemainingCost = (int)(endPosition - exploredNodeWorldPos).Length();

//Find nearest tile to the target (in case doesn't find path to target)
//Only compares the node to the current nearest
FindNearest(exploredNode);

}
}
}
}

return closedNodes;
}


After that, I simply check if the end node is contained in the returned nodes. If so, I add the end node and each parent until I reach the start. If not, I add the nearestToTarget and each parent until I reach the start.

I added a condition before calling FindPath so that only one unit can call a find path each frame (60 frame per second), but it makes no difference.

I thought maybe I could solve this by allowing the find path to run in background while the game continues to run correctly, even if it takes a few frame (it is currently sequential sonce it is called in the update() of the unit if there's a target location but no path), but I don't really know how...

I also though about sorting my opened nodes list by cost so I don't have to loop them, but I don't know if that would have an effect on the performance...

Would there be other solutions?

P.S. In the code, when I get the Move Cost, I check if the unit has to turn to perform the move, and the terrain type, nothing hard to do.

When there is no path from the start to the end, the algorithm must search every possible location. This means that A* becomes as least as slow as a naive flood-fill algorithm (as it is covering the whole graph) and probably slower (as it is performing extra work to manage the queue and calculate heuristics). Optimising your algorithm is unlikely to help much as this is the worst-case scenario and the issue is the number of nodes you will evaluate.

Sorting your open list by cost may or may not help matters in the usual case, because you end up making FindLowestCostOpenedNode a lot cheaper but it makes adding nodes to the open list more expensive, so the benefit depends somewhat on how straight your paths typically are. But in this case, you're exploring the whole map, which means every single node is added to the list at least once and taken off the list at least once, meaning no real benefit - sorting a list gains you nothing if you're going to be looking at every element anyway.

So, all you can do here is try and find some short-cuts to avoid examining the whole map in these situations or to reduce the cost of doing so. Ideas include:

• Doing a cheap hierarchical search first, and only performing the detailed search if the top level search succeeds. bobobobo's answer describes this approach.
• Annotate your map with regions that can't be reached from other regions. You may be able to pre-process your map and use a flood-fill technique to determine all the contiguous areas that can be reached (and by extension, also find all the areas that cannot ever be reached). By marking these you can cancel the A* algorithm as soon as it begins, by spotting that the start node and end node are not in the same contiguous region.
• You can run the A* search concurrently with your game updates, so that although it will take a long time, it won't hold up the game. The safest way to do this is to wrap the FindPath data and function into a class, change it so that instead of just returning a path, it can return a Finished or Not Finished value, make it return Not Finished after processing 50 nodes (or some other arbitrary amount), and call FindPath every frame until the algorithm completes. Another way is to push the processing into a background thread, but that is generally not safe and is quite error-prone unless you are familiar with threads.
• "because you end up making FindLowestCostOpenedNode a lot cheaper but it makes adding nodes to the open list more expensive" - FindLowestCostOpenedNode improves from O(n) to O(1). Removing the lowest cost node improves from O(n) to O(lg n). Checking presence in the closed set can go from O(n) to O(1) if you use a real set. Adding nodes degrades from amortized O(1) to amortized O(lg n). These are massive improvements. The extra you pay for addition is more than compensated for just by the less you pay for removal. – user744 Jun 8 '12 at 8:23
• In profiling I have seen no gains from changing to a sorted open list. I think this is for 2 reasons - first, because you usually end up adding many more nodes than you remove, so the extra addition cost can be quite significant, and second, because the O(N) for removal from an unsorted sequence is usually very efficient due to cache-coherence and block copy operations, when compared to the O(log N) removal which typically has to examine the object (often involving an indirection) and perform comparisons (involving missed branch predictions). So it's worth testing in any specific case. – Kylotan Jun 8 '12 at 12:47
• Thanks a lot. I fixed my problem by implementing something like your third idea. I limited the number of nodes processed and resumed to the next frame, but there still seemed to have issues. So I limited the number of nodes processed to 100 and made the unit move along the path found processing those 100 nodes. I found that the unit was moving in the right direction by the right path.When the unit reached the last waypoint found, it lauches a new request, until it reaches the destination or that the request returns a path having no waypoints. – Amaranth Jun 8 '12 at 23:05
• It sounds like you still have performance problems, if the pathfinding is very slow even with a reachable destination. Also, there's no guarantee in general that the best path limited to 100 nodes will actually reach your destination, even if it usually does. Consider profiling your code to find out where the slow code is. – Kylotan Jun 8 '12 at 23:18
• Oh, no, I did my tests only with the unreachable destination. I never had problem with reachable destination, even from one extremity to the other. Also, after writing my message, I increased the limit to 300 and it still works great (my map has 1600 nodes total) – Amaranth Jun 8 '12 at 23:42

Without looking at your code, the only thing I can suggest is to make your graph coarser. So I would plan the route in 2 steps:

given desired route:

If you find the route (from the o to the x) using the full graph (with 1 graph node per tile in this case) it would be more expensive than it needs to be.

Consider the following (more sparse) set of graph nodes:

You would use this to determine initial path direction, but you would need to have a per-frame collision management system (if you run into another unit on the way, you need to find a way around that unit and not get stuck).

• Good idea. This, combined with some sort of simple heuristic to eliminate terrible paths would greatly decrease the cost of each call to the AI. – SomeGuy Jun 8 '12 at 1:47
• Run the pathfinding from both ends of the path. If either dead-ends you know there is no path. And the first time they cross, you have a path. It will check less nodes in general. Also. Put a limit on it. It is ok to not always find a path. If you create a level big or convoluted enough, you'll create giant crazy pathfinding no matter how you break it up. Having a limit and rules to follow when you reach that limit will eliminate waiting entirely and permanently. – DampeS8N Jun 8 '12 at 15:55
• This is a good idea, but since in my case there are roads and costs are reduced when traveling by road, I need something a little more precise than this. The current pathfinding is already ignoring units and another system is managing collisions. – Amaranth Jun 8 '12 at 22:55
• @Amaranth: Do the A* on the "major nodes" first as shown here, and then do your current A* from the unit position to the first major node, when you get "vaguely close-ish", remove that major node from the to-do list and do your current A* to the next major node. Much faster since you're only considering small chunks of the map at once, and you know there's a path. (And if the path to the next node becomes too long, you know it became blocked, so simply jump back to the major nodes, and restart) – Mooing Duck Jan 2 '15 at 22:37

This is using two lists (and both unsorted!), not priority queues and sets. Unless you are using data structures with complexity guarantees similar to those, the algorithm is not A* but just a slow pile of crap.

Please read something, anything about the A* algorithm's implementation and rewrite it to use proper data structures.

• Thanks for the input. I used standard lists for the prototype, not thinking it would have a great impact, but I'll keep this in mind for the next iteration, maybe I'll use chained lists. – Amaranth Jun 8 '12 at 22:57

As your problem is unreachable locations, you really need some kind of hierarchy.