Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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);

openedNodes.Add(start);

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

    openedNodes.Remove(currentNode);
    closedNodes.Add(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);

                openedNodes.Add(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.

share|improve this question
1  
possible duplicate of Wikipedia A* pathfinding algorithm takes a lot of time –  user744 Jun 8 '12 at 14:31
add comment

4 Answers 4

up vote 6 down vote accepted

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.
share|improve this answer
2  
"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
1  
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
add comment

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:

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:

sparse graph

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

share|improve this answer
    
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
2  
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
add comment

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.

share|improve this answer
    
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
add comment

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

Here's an excellent writeup for the RTS game 0ad: http://www.moddb.com/games/0-ad/news/more-fun-with-pathfinding

Here's how 0ad did it:

enter image description here

They split the map into smaller tiles, and then flood-fill in each tile to discover navigable zones.

You likely only need to do this once, obviously. You may then need to recompute tiles when users build walls and such on them, but that's very rare.

You can then build a lookup that tells you if any zone is reachable from any other; you might build a graph to do so, and you might collapse that graph when build into a simple hashmap keyed by concatenated start and destination zones. Or you might keep the graph around and use it to direct your A*.

As you are concerned about A* performance, also consider - when you have the navigability problem solved - adding the excellent Jump-Point-Search to optimise the A* runtime itself when it does have to find a path.

share|improve this answer
    
Actually, all zones of the map were accessible (except for tiles blocking passage, like mountains). The case I had was blocked by a building. However, I can expand on this to cover future cases. –  Amaranth Jun 8 '12 at 22:59
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.