Need Optimization Help - Alternative to list.Contains

Questions & Answers
1

192614-aaaaab.png
192614-aaaaab.png1129×559 152 KB

The primary thing lagging my game at the moment is list.Contains, are there any alternatives I can use to reduce the ms spike it’s causing? As you can see, each List.Contains here is generating about .25ms. There are 7047 list.Contains being called which leads us to over 1000 ms.

This is the script causing the issue, it’s part of my A* Pathfinding and you can see the three list.Contains towards the bottom.

public List<Node> FindPath(Vector3 a_StartPos, Vector3 a_TargetPosition)
{
    Node startNode = grid.NodeFromWorldPosition(a_StartPos);
    Node targetNode = grid.NodeFromWorldPosition(a_TargetPosition);
    startNode.gCost = 0;

    openList.Clear();
    closedList.Clear();

    openList.Add(startNode);

    int x = 0;
    while (openList.Count > 0)
    {
        x++;
        Node currentNode = openList[0];
        for (int i = 1; i < openList.Count; i++)
        {
            if (openList.fCost < currentNode.fCost || openList_.fCost == currentNode.fCost && openList*.hCost < currentNode.hCost)
            {
            _currentNode = openList*;
            }
        }
        openList.Remove(currentNode);
        closedList.Add(currentNode);
        
        if (currentNode == targetNode)
        {
            finalPath.Clear();
            Node curNode = targetNode;
            
            while (curNode != startNode)
            {
            finalPath.Add(curNode);
            curNode = curNode.parent;
            }
            
            finalPath.Reverse();
            
            GetFinalPath(startNode, targetNode);
            return finalPath;
        }
        
        neighboringNodes.Clear();
        foreach (Node neighborNodes in grid.GetNeightboringNodes(currentNode, neighboringNodes))
        {
            if ((!neighborNodes.isWall && !neighborNodes.isOccupied) || closedList.Contains(neighborNodes))
            {
                continue;
            }
            
            int moveCost = currentNode.gCost + GetGetManhattenDistance(currentNode, targetNode);
            
            if (moveCost < neighborNodes.fCost || !openList.Contains(neighborNodes))
            {
                neighborNodes.gCost = moveCost;
                neighborNodes.hCost = GetGetManhattenDistance(neighborNodes, targetNode);
                neighborNodes.parent = currentNode;
                
                if (!openList.Contains(neighborNodes))
                {
                    openList.Add(neighborNodes);
                }
            }
        }
    }
    return null;
}

Thank you for any help!

2

If you ever need need fast Contains() think HashSet or HashMap/Dictionary. This closedList can be a HashSet here.

openList needs something different though - a MinHeap. It’s self-ordering list (kind of) and it will fit this role well (no more slow/linear openList.Contains calls).

3

I had a similar problem in my project which i solved by giving my equivalent of your neighborNodes variable a variable:

 public bool isInOpenList;

The only drawback is: you have to set those manually and must never forget to reset them once you remove them from the openlist.
Apart from that this should enable you to get rid of the Contains calls in line 54 and 60.

The same can ofc also be done for the closed list.

Let me know if that helped.