Need Optimization Help - Alternative to list.Contains

Question

alt text

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 1

Best Answer

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

Add comment · Show 5 · Share

Razputin · Feb 15 at 02:27 AM 0

Share

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!

andrew-lukasik Razputin · Feb 15 at 08:26 AM 0

Share

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

Razputin andrew-lukasik · Feb 16 at 09:42 PM 0

Share

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.

Show more comments

Answer 2

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.

Add comment · Show 3 · Share

Razputin · Feb 15 at 09:49 PM 0

Share

I'm going to try this tonight and report back

Razputin Razputin · Feb 16 at 09:50 PM 0

Share

Didn't help much unfortunately, thank you for the suggestion though. I ended up putting a heap in and that worked quite well.

Captain_Pineapple Razputin · Feb 17 at 08:55 AM 0

Share

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

Need Optimization Help - Alternative to list.Contains

2 Replies

Your answer

Follow this Question

Related Questions