Prim 的迷宫算法：为什么我必须仔细检查我的迷宫中是否包含节点？

Question

我正在尝试按照 here 所述在我的迷宫生成器中实施 Prim 算法。我已经让它按预期工作，但我的代码中有一个额外的问题，我不确定为什么需要它。

在我的算法中，我跟踪构成 maze 中迷宫的单元格列表。然后我查看潜在的边界单元（构成迷宫的单元的相邻单元），并随机选择一个。我们称其为 frontier。然后我确定 frontier 的邻居，并检查哪些邻居连接到已经存在的 maze。我连接 frontier 节点和相邻的已经在迷宫中的节点，从可能的 frontiers 列表中删除 frontier 节点，将其添加到 maze，最后添加frontier 列表中新发现的迷宫节点的邻居。

在此过程中，我确保只将 frontiers 列表中尚未包含在 maze 中的节点添加到列表中。（参见 if (neighbour.Cell != null && !maze.Contains(neighbour.Cell)) 语句。

但是，如果我不最终仔细检查每个 chosenFrontier 以查看它们是否尚未包含在迷宫中，我的算法似乎就会出错。如果我不这样做，算法最终会认为即使在每个相邻的方块都已经是迷宫的一部分的地方仍然存在边界单元。

这是为什么？为什么我需要 if { ... } else { ...} 语句才能让我的算法成功？我很困惑为什么它是必要的，因为在我向 frontier 列表添加单元格的任何地方，我已经检查它们是否已经包含在 maze 中。如果是，则不会将它们添加到我的 frontier 列表中。然而不知何故，如果我必须仔细检查我的 frontier 列表中已经包含在迷宫中的单元格（并删除它们）。我哪里错了？

这是我的代码：

private IEnumerator PrimsAlgorithm(Cell startingCell)
{
    List<Cell> maze = new List<Cell>();
    maze.Add(startingCell);
    startingCell.Visit();
        
    // Determine starting cell's frontier cells
    List<Neighbour> frontiers = new List<Neighbour>();
    foreach(Neighbour neighbour in startingCell.GetNeighbours())
    {
        if (neighbour.Cell != null && !maze.Contains(neighbour.Cell))
        {
            frontiers.Add(neighbour);
        }
    }

    yield return new WaitForSeconds(stepSize);
    startingCell.Leave();

    // While there are frontier cells,
    while (frontiers.Count > 0)
    {
        // Choose a random frontier from the list
        Neighbour chosenFrontier = frontiers[random.Next(frontiers.Count)];

        if (maze.Contains(chosenFrontier.Cell))
        {
            // ----- Why is this neccessary??? -----
            frontiers.Remove(chosenFrontier);
        }
        else
        {
            // Determine the frontier cells's possible neighbours
            // Possible neighbours are only cells that are already part of the maze.
            Neighbour[] chosenFrontierNeighbours = chosenFrontier.Cell.GetNeighbours();
            List<Neighbour> adjacentInMazeNeighbours = new List<Neighbour>();
            foreach (Neighbour chosenFrontierNeighbour in chosenFrontierNeighbours)
            {
                if (chosenFrontierNeighbour.Cell != null && maze.Contains(chosenFrontierNeighbour.Cell))
                {
                    adjacentInMazeNeighbours.Add(chosenFrontierNeighbour);
                }
            }

            // Choose a random neighbour from the possible neighbours
            if (adjacentInMazeNeighbours.Count > 0)
            {
                Neighbour chosenInMazeNeighbour = adjacentInMazeNeighbours[random.Next(adjacentInMazeNeighbours.Count)];

                // Connect the frontier cell to their new neighbour (and the other way around)
                maze.Add(chosenFrontier.Cell);
                chosenFrontier.Cell.Visit();
                chosenFrontier.Cell.AddConnection(chosenInMazeNeighbour.Dir);
                chosenInMazeNeighbour.Cell.AddConnection(GetOppositeDir(chosenInMazeNeighbour.Dir));
                // Remove the frontier from the set
                frontiers.Remove(chosenFrontier);

                // Determine the chosenFrontiers' possible neighbours and add them to the list of frontiers.
                // Possible neighbours are cells that exist and aren't yet contained in the maze.
                // These become the new frontier nodes.
                foreach (Neighbour neighbour in chosenFrontier.Cell.GetNeighbours())
                {
                    if (neighbour.Cell != null && !maze.Contains(neighbour.Cell))
                    {
                        frontiers.Add(neighbour);
                    }
                }
            }
            // Wait to show this iteration
            yield return new WaitForSeconds(stepSize);
            // Leave current cell
            chosenFrontier.Cell.Leave();
        }
    }
    yield return new WaitForSeconds(stepSize);
}

这是我的算法使用上述代码的 gif

下面是我删除 if 语句后的结果的 gif 动图

Answer 1

您确保只将不在迷宫中的项目添加到边界列表中，但它们可能已经在边界列表中。

由于边界列表可以包含单个单元格的多个副本，因此您需要进行额外检查以确保不会多次将其添加到迷宫中。

Prim 的迷宫算法：为什么我必须仔细检查我的迷宫中是否包含节点？

Prim's Algorithm for mazes: Why do I have to double check if nodes are contained in my maze?

c#

algorithm

maze

prims-algorithm