I'm trying to make a minesweeper game in which I have made this method for flooding unknown tiles iteratively using Queue collection

private void FloodIterative(Tile tile)
{
    Queue<Tile> queue = new Queue<Tile>();
    queue.Enqueue(tile);

    while (queue.Count != 0)
    {
        Tile b = queue.Dequeue();

        if (b.isDiscovered) continue;
        if (b.type == Tile.Type.Mine || b.type == Bunka.Type.Invalid) continue;

        b.isDiscovered = true;
        state[b.position.x, b.position.y] = b;

        if (b.type == Bunka.Type.Empty)
        {
            queue.Enqueue(GetBunka(b.position.x - 1, b.position.y));
            queue.Enqueue(GetBunka(b.position.x   1, b.position.y));
            queue.Enqueue(GetBunka(b.position.x, b.position.y - 1));
            queue.Enqueue(GetBunka(b.position.x, b.position.y   1));
            queue.Enqueue(GetBunka(b.position.x - 1, b.position.y - 1));
            queue.Enqueue(GetBunka(b.position.x   1, b.position.y   1));
            queue.Enqueue(GetBunka(b.position.x   1, b.position.y - 1));
            queue.Enqueue(GetBunka(b.position.x - 1, b.position.y   1));
        }
    }
}

This method works well but only for a limited amount of unexplored tiles. If the tile number gets too big my unity engine outputs:

OutOfMemoryException: Out of memory

System.Collections.Generic.Queue 1[T].SetCapacity (System.Int32 capacity) (at <5a2009c85b134970925993880e2ecb2e>:0) System.Collections.Generic.Queue 1[T].Enqueue (T item) (at <5a2009c85b134970925993880e2ecb2e>:0)

Is there any solution to this? Is it possible that I need to deallocate memory manually? Thank you so much in advance.

CodePudding user response：

The numbers (0.5GB and 5GB) you mention makes me worried there's some other issue hiding around than what @joshua-robinson pointed out. If we pretend you have a grid of 100x100 and your current approach potentially adds every Tile 8 times to the queue it means 5GB / (100 * 100 * 8) == 65kB per tile. That is a lot of memory for a single Tile - and this is assuming GetBunka instantiates a new Tile object instead of reusing the same Tile object on a given position. If the grid you have tested with is smaller, the amount of memory per Tile is even higher.

Without knowing the contents of Tile I would assume it should take up far less than 1kB.

But to address the matter at hand, we can use a HashSet to keep track of the tiles we've already looked at to avoid adding those to the queue more than once.

private void FloodIterative(Tile tile)
{
    Queue<Tile> queue = new Queue<Tile>();
    queue.Enqueue(tile);

    // Tiles we have had a peak at
    // I.e. they were added to the queue at some point
    var tilesPeakedAt = new HashSet<Tile>(queue);

    while (queue.Count != 0)
    {
        Tile b = queue.Dequeue();

        if (b.isDiscovered) continue;
        if (b.type == Tile.Type.Mine || b.type == Bunka.Type.Invalid) continue;

        b.isDiscovered = true;
        state[b.position.x, b.position.y] = b;

        if (b.type == Bunka.Type.Empty)
        {
            var tilesToCheck = GetAllNeighbors(b)
                .Where(t => !tilesPeakedAt.Contains(t));
            foreach (var t in tilesToCheck)
            {
                queue.Enqueue(t);
                tilesPeakedAt.Add(t);
            }
        }
    }
}

private Tile[] GetAllNeighbors(Tile b) // Position as input would be enough
{
    return new []
    {
        GetBunka(b.position.x - 1, b.position.y)
        GetBunka(b.position.x   1, b.position.y)
        GetBunka(b.position.x, b.position.y - 1)
        GetBunka(b.position.x, b.position.y   1)
        GetBunka(b.position.x - 1, b.position.y - 1)
        GetBunka(b.position.x   1, b.position.y   1)
        GetBunka(b.position.x   1, b.position.y - 1)
        GetBunka(b.position.x - 1, b.position.y   1)
    };
}

This should lower the number of tiles put into the queue by up to a factor of 8.

CodePudding user response：

Here is a snippit from my minesweeper game I made a while back.

It helps to know how many mines surround a given tile. This can be set during initial construction of the grid.

private void RevealEmptyAdjacentTiles(Point point)
{
    // Create a list to store the next tiles we need to check 
    //
    var nextTilesToCheck = new List<Tile>();

    // Loop through the adjacent tiles that are not yet revealed
    //
    foreach (var tile in GetAdjacentUnrevealedTiles(point))
    {
        // Make sure this tile is not a mine
        //
        if (!tile.IsMine)
        {
            // Reveal the tile
            //
            tile.Reveal();

            // We also want to check this tiles adjacent unrevealed tiles, add it to our list for checking after this loop completes
            //
            nextTilesToCheck.Add(tile);
        }
    }

    // Loop through all the new tiles we need to check
    //
    foreach (var adjacentTile in nextTilesToCheck)
    {
        // If there are no surrounding mines, lets run this function again for this coordinate
        //
        if (adjacentTile.SurroundingMinesCount == 0)
        {
            // Recursion
            //
            RevealEmptyAdjacentTiles(adjacentTile.Coordinate);
        }
    }
}

We are only concerned with tiles that have not yet been revealed. When checking those unrevealed neighbor tiles, we reveal the tile (unless it is a mine), and subsequently those tiles will never need to be checked again.

CodePudding user response：

It seems that you queue 8 items for each one taken out AND you queue duplicates. Before placing item on queue check if it is not already there.