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.