- Home /
Need Optimization Help - Alternative to list.Contains
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[i].fCost < currentNode.fCost || openList[i].fCost == currentNode.fCost && openList[i].hCost < currentNode.hCost)
{
currentNode = openList[i];
}
}
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!
Answer by andrew-lukasik · Feb 14 at 10:33 PM
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).
Thank you, I should have included the data types, closedList is a HashSet. I've never heard of a MinHeap though, is there any more information you can give to me about it? Thank you!
Well, on the surface, you use a MinHeap
more or less like a stack ie. calling Pop()
/Push(node)
methods. But Push(item)
implementation's role/aim here is to store all the pushed items in an orderly fashion so Pop()
will always return you a node with the lowest F score (removes linear search loop).
Also, your custom MinHeap
implementation, can contain a auxiliary HashSet
to allow for fast Contains()
calls too (thus removing the last linear search i.e. open.Contains()
).
I ended up implimenting a the following heap https://github.com/SebLague/Pathfinding/blob/master/Episode%2004%20-%20heap/Assets/Scripts/Heap.cs
this reduced my max ms down to around 20ms for a 25x15x25 grid.
I will continue to try and optimize to allow for even larger grids.
Answer by Captain_Pineapple · Feb 15 at 08:18 AM
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.
Didn't help much unfortunately, thank you for the suggestion though. I ended up putting a heap in and that worked quite well.
intresting. As for the raw count of access calls adding this flag should have been the better solution. Will have to try this myself as well :)
Your answer
![](https://koobas.hobune.stream/wayback/20220613053026im_/https://answers.unity.com/themes/thub/images/avi.jpg)
Follow this Question
Related Questions
A* pathfinder - next target 1 Answer
A* or AStar Pathfinding doesnt work for me? 0 Answers
Lost in Pathfinding again 0 Answers
"Too Many Heap Sections" Building A*Pathfinding 1 Answer
How do I get my game to run faster? 4 Answers