Is there an algorithm for detecting if an object would block a section of a grid?

Unity Engine
,
1

I have a 2D grid represented by a multidimensional array of bools. On this grid, you can place various objects. The player cannot move through these objects. I want to prevent the user from being able to block off a section of the grid, before they even try to place the object.

I wrote a breadth-first-search algorithm to see if the grid would be different than the current grid if the current cell were to be blocked off. However, my code starts to stutter the game at grids as small as 12x12. Is there an algorithm for doing what I want to do, but faster? Is there something I could add to make this more efficient? Any advice would be helpful.

Here’s my code:

private bool CellBlocksPathway(Vector2Int coordinates)
{
    // Don't run this algorithm if we've already checked this cell.
    // This list will get cleared when the state of the grid changes.
    if (lastCheckedCells.Contains(coordinates))
    {
        return lastCheckedCells.GetResult(coordinates);
    }

    // Create fake grid of bools.
    bool[,] fakeOccupiedGrid = new bool[width, height];

    // Set everything to true.
    for (int i = 0; i < width; i++)
    {
        for (int j = 0; j < height; j++)
        {
            fakeOccupiedGrid[i, j] = true;
        }
    }

    // Create a queue of coordinates to check, add the Cell at 0,0
    Queue<Vector2Int> queuedCoordinates = new Queue<Vector2Int>();
    queuedCoordinates.Enqueue(Vector2Int.zero);
    Vector2Int currentCoordinates = queuedCoordinates.Peek();

    // Add the coordinates at 0,1 and 1,0
    queuedCoordinates.Enqueue(queuedCoordinates.Peek() + Vector2Int.up);
    queuedCoordinates.Enqueue(queuedCoordinates.Peek() + Vector2Int.right);

    // Set the 0,0 to the real bool value
    fakeOccupiedGrid[currentCoordinates.x, currentCoordinates.y] =
        occupied[currentCoordinates.x, currentCoordinates.y];

    // Make a HashSet of previously-searched coordinates, so we don't check a coordinate multiple times.
    // This improved the algorithm from 8x8 to 12x12 when changed from List to HashSet.
    HashSet<Vector2Int> searchedCoordinates = new HashSet<Vector2Int>();
    searchedCoordinates.Add(queuedCoordinates.Dequeue());

    while (queuedCoordinates.Count > 0)
    {
        currentCoordinates = queuedCoordinates.Dequeue();
        searchedCoordinates.Add(currentCoordinates);

        // If the current coordinate is occupied, don't change anything, don't check its neighbors.
        if (occupied[currentCoordinates.x, currentCoordinates.y])
        {
            continue;
        }

        fakeOccupiedGrid[currentCoordinates.x, currentCoordinates.y] = false;

        // If we're looking at the current coordinates being checked, ignore their neighbors to pretend like this cell is occupied.
        if (currentCoordinates == coordinates)
        {
            continue;
        }

        // If the adjacent coordinate is in-bounds, and we haven't checked it yet, add it to the queue.
        // Check the up neighbor.
        if (currentCoordinates.y + 1 < height &&
            !searchedCoordinates.Contains(currentCoordinates + Vector2Int.up))
        {
            queuedCoordinates.Enqueue(currentCoordinates + Vector2Int.up);
        }

        // Check the right neighbor.
        if (currentCoordinates.x + 1 < width &&
            !searchedCoordinates.Contains(currentCoordinates + Vector2Int.right))
        {
            queuedCoordinates.Enqueue(currentCoordinates + Vector2Int.right);
        }

        // Check the down neighbor.
        if (currentCoordinates.y - 1 >= 0 &&
            !searchedCoordinates.Contains(currentCoordinates + Vector2Int.down))
        {
            queuedCoordinates.Enqueue(currentCoordinates + Vector2Int.down);
        }

        // Check the left neighbor.
        if (currentCoordinates.x - 1 >= 0 &&
            !searchedCoordinates.Contains(currentCoordinates + Vector2Int.left))
        {
            queuedCoordinates.Enqueue(currentCoordinates + Vector2Int.left);
        }
    }

    lastCheckedCells.Add(coordinates, GridsAreNotEqual(fakeOccupiedGrid));

    return lastCheckedCells.GetLatestResult();
}
2

Run a flood fill on any empty cell, after you’re done, search for an unfilled cell. If there is one, your grid is disjointed.
You might be doing that already (in which case, something else is wrong, this should be more than fast enough for this), I’m not sure