C# 迷宫生成：基于 Prim 算法的自己实现存在问题

Question

C# 迷宫生成：基于 Prim 算法的自己实现存在问题

c#windowsxnaprims-algorithm

3

首先，让我为篇幅道歉，我会尽量保持简短。

在尝试按照维基百科上的指示构建普里姆算法后，我发现它无法适应我的迷宫构建方式。因此，我尝试了同样的思路来适应我的迷宫，但是我遇到了一个奇怪的错误。

当游戏开始时，迷宫构建不正确，我无法找出原因。以下是偶尔发生的情况：

Maze Error picture

有时它可以完美地工作，所以我有一个 public Dictionary<int, Dictionary<int, MazeCellState>> maze，它保存了迷宫。当迷宫开始时，所有的墙都已经搭好了，然后我按以下方式构建路径。

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此时只能是路径或栅栏两个选项，并且reorderList将重新索引任何类型的列表，迷宫大小是根据屏幕分辨率计算的，每个单元格为64x64像素。

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

- Barkermn01

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- cliffordheath · Accepted Answer

那是一种在网格场中实现算法的艰难方式。网格的Prim算法可以更容易地表达。不用研究你的代码哪里出了错，我会告诉你简单的方法。

创建网格，并使用连续数字从零开始为每个单元格编号。每个单元格有两堵边界墙可打破；上和左，或下和右，或其他组合，只要选择(左/右)和(上/下)之一即可。

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

如果您有N个单元格，则必须重复此打破墙壁的练习N-1次，直到最后一次所有单元格都被编号为零（因为每次打破时，您都会从领域中删除更高的编号），并且您有一个完整的迷宫。

如果您想要路径更多地从左到右而不是从上到下的迷宫，则在该方向上偏向于随机选择要打破的墙壁。这也适用于三维迷宫，其中您可能不希望有许多梯子；只需不要选择打破太多天花板/地板即可。

在我描述了这个算法之后，我的14岁儿子在3D Turbo-Pascal中实现了它，所以我知道该算法和此描述实际有效。这实际上是Prim算法的一个版本，除了所有弧的成本相同（或所有左-右弧和所有上-下弧都是如此等）。它的好处在于编号方式可以确定哪些单元格已经可以从其他单元格到达。