C# Maze Generation 我自己实现的Prim的算法Bug

Question

首先让我为尺寸道歉我会尽量保持它尽可能小

在尝试完全按照维基百科上所说的那样构建 prim 的算法后，我发现它无法按照我构建的迷宫方式运行。 所以我尝试做同样的想法来适应我的迷宫，但我看到了一个奇怪的错误，

当我的游戏开始时，它只是没有正确地 build 我的迷宫，我不知道为什么 这是偶尔发生的事情

其他时候它工作得很好， 所以我有一个public Dictionary<int, Dictionary<int, MazeCellState>> maze当它开始时，它占据了迷宫，迷宫是所有的树篱，然后我继续像这样 build 路径

private static void buildPath()
       {
           List<KeyValuePair<Misc.Cord, Misc.Cord>> ends = new List<KeyValuePair<Misc.Cord, Misc.Cord>>();
           ends.Add(new KeyValuePair<Misc.Cord, Misc.Cord>(new Misc.Cord() { X = 0, Y = 0 }, new Misc.Cord() { X = 0, Y = 0 }));
           Misc.Cord currentPos = null;

           while (ends.Count > 0)
           {
               int posKey = rand.Next(0, ends.Count);
               Misc.Cord lastPos = ends[posKey].Key;
               currentPos = ends[posKey].Value;
               maze[currentPos.X][currentPos.Y] = MazeCellState.Path;
               int currentCount = 0;

               MovingState moveTo1 = (MovingState)rand.Next(0, 4);
               MovingState moveTo2 = (MovingState)rand.Next(0, 4);
               while (moveTo1.Equals(moveTo2))
               {
                   moveTo1 = (MovingState)rand.Next(0, 4);
                   moveTo2 = (MovingState)rand.Next(0, 4);
               }

               // check left
               if (currentPos.X - 2 > 0 && maze[currentPos.X - 2][currentPos.Y] != MazeCellState.Path && currentCount < 2 && (moveTo1 == MovingState.Left || moveTo2 == MovingState.Left))
               {
                   if(!lastPos.Equals(new Misc.Cord() { X = currentPos.X - 2, Y = currentPos.Y }))
                   {
                       ends.Add(new KeyValuePair<Misc.Cord, Misc.Cord>(currentPos, new Misc.Cord() { X = currentPos.X - 2, Y = currentPos.Y }));
                       maze[currentPos.X - 1][currentPos.Y] = MazeCellState.Path;
                       currentCount++;
                   }
               }

               // check right
               if (currentPos.X + 2 < maze.Count && maze[currentPos.X + 2][currentPos.Y] != MazeCellState.Path && currentCount < 2 && (moveTo1 == MovingState.Right || moveTo2 == MovingState.Right))
               {
                   if (!lastPos.Equals(new Misc.Cord() { X = currentPos.X + 2, Y = currentPos.Y }))
                   {
                       ends.Add(new KeyValuePair<Misc.Cord, Misc.Cord>(currentPos, new Misc.Cord() { X = currentPos.X + 2, Y = currentPos.Y }));
                       maze[currentPos.X + 1][currentPos.Y] = MazeCellState.Path;
                       currentCount++;
                   }
               }

               // check Up
               if (currentPos.Y - 2 > 0 && maze[currentPos.X][currentPos.Y - 2] != MazeCellState.Path && currentCount < 2 && (moveTo1 == MovingState.Up || moveTo2 == MovingState.Up))
               {
                   if(!lastPos.Equals(new Misc.Cord() { X = currentPos.X, Y = currentPos.Y - 2}))
                   {
                       ends.Add(new KeyValuePair<Misc.Cord, Misc.Cord>(currentPos, new Misc.Cord() { X = currentPos.X, Y = currentPos.Y - 2 }));
                       maze[currentPos.X][currentPos.Y - 1] = MazeCellState.Path;
                       currentCount++;
                   }
               }

               // check Down
               if (currentPos.Y + 2 < maze[0].Count && maze[currentPos.X][currentPos.Y + 2] != MazeCellState.Path && currentCount < 2 && (moveTo1 == MovingState.Down || moveTo2 == MovingState.Down))
               {
                   if(!lastPos.Equals(new Misc.Cord() { X = currentPos.X, Y = currentPos.Y + 2}))
                   {
                       ends.Add(new KeyValuePair<Misc.Cord, Misc.Cord>(currentPos, new Misc.Cord() { X = currentPos.X, Y = currentPos.Y + 2 }));
                       maze[currentPos.X][currentPos.Y + 1] = MazeCellState.Path;
                       currentCount++;
                   }
               }
                ends.RemoveAt(posKey);
                ends = reorderList(ends);
           }

           maze[0][1] = MazeCellState.Path;
       }

我不确定为什么我偶尔会看到上面的图片，我的理论是它最终会自行恢复

一些快速说明，此时 MazeCellState 只能是 2 个选项之一，path 或 hedge 和 reorderList 将重新索引任何类型的列表迷宫大小根据屏幕分辨率计算，每个单元格为 64x64 PX，

            GraphicsDevice.Viewport.Width * 5 / 64,
            GraphicsDevice.Viewport.Height * 5 / 64

Answer 1

当您的字段是网格时，这确实是一种实现算法的困难方法。 Prim 的网格算法可以更容易地表达。我不会研究您的代码做错了什么，而是告诉您一个简单的方法。

创建您的网格，并使用从零开始的连续数字对所有单元格进行编号。每个细胞都有两个可以打破的边界墙；上和左，或下和右，或其他一些组合，只要您选择(左/右)之一和(上/下)之一就没关系。

现在选择任何单元格，然后选择它的一面墙。如果那堵墙另一侧的单元格有不同的数字(一个高一个低)，打破那堵墙，然后在整个迷宫中，将所有出现的较高数字重新编号为较低的数字。如果您选择的单元格和另一侧已经具有相同编号的墙，请不要尝试另一面墙，而是按顺序移动到下一个单元格，重复每一行并向下(可能几乎一直循环) 直到你找到一个有你可以打破的墙的单元格。

如果你有 N 个单元格，你必须精确地重复这个破墙练习 N-1 次，直到最后一次所有单元格的编号都为零(因为每次你打破时，你都会从字段中删除较高的数字)，并且你有一个完整的迷宫。

如果您想要一个迷宫，其路径通常是左右而不是上下，那么请将您随机选择的墙壁偏向该方向。这也适用于 3D 迷宫，您可能不需要很多梯子；只是不要选择打破那么多天花板/地板。

在我描述了这个算法之后，我 14 岁的儿子在 3D Turbo-Pascal 中实现了它，所以我知道这个算法和这个描述确实有效。这实际上是 Prim 算法的一个版本，除了所有弧具有相同成本的情况(或者所有左右弧都一样，所有上下弧都一样，等等)。它的巧妙之处在于编号的工作方式可以确定哪些单元格已经可以从其他单元格访问。