C# 队列 - 内存不足

Question

我正在尝试制作一个扫雷游戏，我在其中制作了使用队列集合迭代淹没未知图块的方法

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));
        }
    }
}

此方法效果很好，但仅适用于数量有限的未探索图块。如果图块编号太大，我的统一引擎输出：

OutOfMemoryException: 内存不足

System.Collections.Generic.Queue 1[T].SetCapacity（System.Int32 容量）（位于 <5a2009c85b134970925993880e2ecb2e>:0） System.Collections.Generic.Queue 1[T].Enqueue (T item) (at <5a2009c85b134970925993880e2ecb2e>:0)

有什么解决办法吗？我可能需要手动释放内存吗？非常感谢您。

Answer 1

您似乎为每个取出的物品排队了 8 件物品，并且您排队了重复的物品。在将项目放入队列之前检查它是否已经存在。

Answer 2

这是我不久前制作的扫雷游戏的片段。

了解给定方块周围有多少地雷会有所帮助。这可以在网格的初始构造期间设置。

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);
        }
    }
}

我们只关注尚未揭晓的板块。当检查那些未暴露的相邻图块时，我们会显示该图块（除非它是地雷），随后这些图块将永远不需要再次检查。

Answer 3

你提到的数字（0.5GB 和 5GB）让我担心除了 @joshua-robinson 指出的之外还有其他一些问题。如果我们假设您有一个 100x100 的网格，并且您当前的方法可能会将每 Tile 次添加到队列中 8 次，这意味着每个图块 5GB / (100 * 100 * 8) == 65kB。对于单个 Tile，这是很多的内存 - 这是假设 GetBunka 实例化一个新的 Tile 对象而不是重复使用相同的 Tile 给定位置上的对象。如果您测试的网格较小，则每个 Tile 的内存量甚至更高。

在不知道 Tile 的内容的情况下，我认为它占用的空间应该远小于 1kB。

但为了解决手头的问题，我们可以使用 HashSet 来跟踪我们已经看过的图块，以避免将它们多次添加到队列中。

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)
    };
}

这应该会将放入队列的图块数量最多减少 8 倍。

C# 队列 - 内存不足

C# Queue - out of memory

c#

memory

queue

unity3d