Anyone help with an infinite loop problem on a while list.count >0 condition

Questions & Answers
1

Ok, this is a slightly messy, massively unoptimized bit of code. My problem is that whenever I run it, it goes infinite and I get nothing output in the console log at all. Have to quit unity to get back in… The code is part of a pathfinding testing process based on grid movement.

The core loop is an empty list with a single start location added to process from. The loop is a while loop (while list.count>0), and if movement is possible (up,down,left,right only) then those cells are added to the open list for further processing. Except it doesn’t work and I just can’t figure out why. The codes not finished yet, but I need to figure out why this isn’t working, so this isn’t the endgoal (need a closed list and a bunch of other stuff, but this ought to be working in its current state)

Gamemanager is a separate gameobject and script with an array called GridContents which is how in this test project I’m tracking the state of the grid and whether each square is empty or not (non walkable).

WorldTile is a custom class representing each game square, which I’ll be using later on, if I can get this infinite loop thing sorted. Ok here’s the code…

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.UI;

public class PathFinding : MonoBehaviour
{
    public GameObject GameController;

    public void Start()
    {
        GameController gm = GameController.GetComponent<GameController>();
    }
    public void PathfindingTest()

    {
        Debug.Log("This is the START of the pathfinding test PATHFINDING function");
        GameController gm = GameController.GetComponent<GameController>();
        
        List<WorldTile> openSet = new List<WorldTile>();
        HashSet<WorldTile> closedSet = new HashSet<WorldTile>();
        
        // TESTING ONLY Add the 0,0 location to the open set
        WorldTile StartingSearchTile = new WorldTile(0, 0);
        openSet.Add(StartingSearchTile);
        Debug.Log("The starting search Tile is " + openSet[0].gridX + "," + openSet[0].gridY);
  
       while (openSet.Count>0)
       {
            WorldTile currentnode = openSet[0];
            int tempx = currentnode.gridX;
            int tempy = currentnode.gridY;
            Debug.Log("The current active node is " +tempx + "," + tempy);
            Debug.Log("New open set count:"+openSet.Count);

            // TESTING ONLY - just manual checks based on a 20x7 grid (0,0 BottomLeft > 19,6 UpperRight)

            // Check to the left
            if (tempx > 0)
            {
                if (gm.GridContents[(tempx - 1), tempy] == "empty")
                {
                  WorldTile wtleft = new WorldTile(tempx - 1, tempy);
               openSet.Add(wtleft);
                }
            }

            // Check to the right, invalid if x>=19 (last column in grid)
            if (tempx < 19)
            {
                if (gm.GridContents[(tempx + 1), tempy] == "empty")
                {
                  WorldTile wtright = new WorldTile(tempx + 1, tempy);
                openSet.Add(wtright);
                }
            }

            // Check above, invalid if y=6 (top row)
            if (tempy < 6)
            {
                if (gm.GridContents[tempx, (tempy + 1)] == "empty")
                {
                 WorldTile wtup = new WorldTile(tempx, tempy + 1);
                openSet.Add(wtup);
                }
            }

            // Check below, invalid if y=0 (bottom row)
            if (tempy>0)
            {
                if (gm.GridContents[tempx, (tempy - 1)] == "empty")
                {
                  WorldTile wtdown = new WorldTile(tempx, tempy - 1);
                 openSet.Add(wtdown);
                }
            }

            // We should now have checked all four possible directions, including checking for invalid values, and new items have been added to the open set.
            Debug.Log("All routes checked from: " + tempx + "," + tempy);
            Debug.Log("Removing current item from open list");
                
            openSet.Remove(currentnode);
            Debug.Log("The open list now has " + openSet.Count + " items");
      }
        Debug.Log("The While loop has exited");
    }
}
2

Ok, possibly I’m an idiot. After three hours staring at it (and of course five minutes after posting) I’m wondering if this is because I’m probably creating an infinite list, as squares are probably being referenced multiple times. I’ll add code to add checked nodes to a list and check that list before adding anything more items. I’ll report back if that fixes it, but it seems likely…

3

It doesn’t look like you have a closed set. At least it’s not clear if you somehow magically change the state of your “gm.GridContents” array. If you don’t you will always add the same tiles to your open list over and over again. Since you always go left, right, up and down from your current position, it means when you are at position x and you add a node at pos x+1 to the open list, when you finally process that node you will also add node x - 1 to the open list which is the same you started with.

So unless your “WorldTile” constructor does directly modify your GridContents, you’ll end up with an endless growing openlist. The processing of that list takes a long time since you’re constantly allocating new memory. However sooner or later you would probably run out of memory and your application and Unity would actually crash (getting terminated by the OS).