Floodfill algorithm freezing?

Unity Engine
1

Hey all, I’ve been writing this floodfill algorithm and for some reason it keeps freezing. I’m not too sure what could be happening, as i’ve made sure it isn’t looping over itself or whatnot. What could be happening?

List<Vector2Int> completed = new List<Vector2Int>();
            //Floodfill to find neighbours
            Queue<Vector2Int> queue = new Queue<Vector2Int>();
            queue.Enqueue(r.originPoint);

            while (queue.Count > 0)
            {
                Vector2Int point = queue.Dequeue();
                completed.Add(point);

                Vector2Int up = new Vector2Int(point.x, point.y + 1);
                //Up
                if (coordinateInRange(up.x, up.y) && !completed.Contains(new Vector2Int(up.x, up.y)))
                {
                    if (levelTiles[up.x, up.y] == r.ID)
                        queue.Enqueue(new Vector2Int(up.x, up.y));
                    else if (levelTiles[up.x, up.y] != -1) //-1 is a wall cell. These only exist at the edges of the map at this point.
                        r.AddNeighbour(rooms[levelTiles[up.x, up.y]]);
                }

                Vector2Int down = new Vector2Int(point.x, point.y - 1);
                //Up
                if (coordinateInRange(down.x, down.y) && !completed.Contains(new Vector2Int(down.x, down.y)))
                {
                    if (levelTiles[down.x, down.y] == r.ID)
                        queue.Enqueue(new Vector2Int(down.x, down.y));
                    else if (levelTiles[down.x, down.y] != -1) //-1 is a wall cell. These only exist at the edges of the map at this point.
                        r.AddNeighbour(rooms[levelTiles[down.x, down.y]]);
                }

                Vector2Int left = new Vector2Int(point.x - 1, point.y);
                //Up
                if (coordinateInRange(left.x, left.y) && !completed.Contains(new Vector2Int(left.x, left.y)))
                {
                    if (levelTiles[left.x, left.y] == r.ID)
                        queue.Enqueue(new Vector2Int(left.x, left.y));
                    else if (levelTiles[left.x, left.y] != -1) //-1 is a wall cell. These only exist at the edges of the map at this point.
                        r.AddNeighbour(rooms[levelTiles[left.x, left.y]]);
                }

                Vector2Int right = new Vector2Int(point.x + 1, point.y);
                //Right
                if (coordinateInRange(right.x, right.y) && !completed.Contains(new Vector2Int(right.x, right.y)))
                {
                    if (levelTiles[right.x, right.y] == r.ID)
                        queue.Enqueue(new Vector2Int(right.x, right.y));
                    else if (levelTiles[right.x, right.y] != -1) //-1 is a wall cell. These only exist at the edges of the map at this point.
                        r.AddNeighbour(rooms[levelTiles[right.x, right.y]]);
                }
            }
2

You aren’t checking if you’ve already processed a particular location. I suggest this:

Vector2Int point = queue.Dequeue();
if (completed.Contains(point)) {
  // If we've already processed this location, move on.
  continue;
}
completed.Add(point);

I also highly suggest changing completed from a List<Vector2Int> to a HashSet<Vector2Int>. No other code will have to change, and the performance will be significantly better.

1 Like
3

On line 13 there’s a check to make sure it’s not already done. Also I’ll do the hashset change rn, why not.

4

Another optimization: You can replace completed.Contains(Vector2Int(up.x, up.y) with completed.Contains(up) and all the similar calls similarly.

Same for e.g. queue.Enqueue(new Vector2Int(left.x, left.y)); → queue.Enqueue(left);

1 Like
5

Good idea, although I assume I won’t need the “completed.contains” bit if i wrote the continue block, right?

6

yeah correct.

7

Btw how big is your grid?