A* algorithm very slow
- by Amaranth
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.
