我自己实现的C#迷宫算法Bug
首先，让我为我的尺寸道歉，我会尽量使它尽可能小。
在尝试按照维基百科上的原样构建prim的算法后，我发现它不会像我的迷宫那样工作。所以我试着做同样的想法来适应我的迷宫，但我发现了一个奇怪的bug，
当我的游戏开始时，它只是不能正确地构建我的迷宫，我不能理解为什么这是偶尔发生的事情
其他时候，它工作得很好，所以我有一个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在这一点上只能是2个选项之一，路径或对冲和reorderList将重新索引任何类型的列表迷宫大小是根据屏幕分辨率计算的，每个单元格是64x64像素，
GraphicsDevice.Viewport.Width * 5 / 64,
GraphicsDevice.Viewport.Height * 5 / 64回答 1
Stack Overflow用户
发布于 2014-03-22 15:29:03
当你的字段是一个网格时，这真的是一个很难实现的算法。Prim的网格算法可以更容易地表达出来。与其研究你在代码中做错了什么，不如让我来告诉你最简单的方法。
创建网格，并使用从零开始的连续数字对所有单元格进行编号。每个单元格有两个它可以打破的边界墙；向上和向左，或者向下和向右，或者其他一些组合，只要你选择(左/右)和(上/下)中的一个，这并不重要。
现在选择任何单元格，并选择它的一面墙。如果那面墙另一边的细胞有一个不同的数字(一个高一个低)，打破那个墙，然后在整个迷宫中，将所有出现较高数字的地方重新编号为较低的数字。如果你选择了一个单元格和另一面墙已经有相同的数字，不要尝试另一面墙，而是按顺序移动到下一个单元格，重复每一行和下一行(可能循环几乎所有的方式)，直到你找到一个可以打破的墙的单元格。
如果你有N个细胞，你必须重复这个破壁练习正好N-1次，直到最后一次所有细胞都被编号为零(因为每次你打破时，你从字段中删除了较高的数字)，你就有了一个完整的迷宫。
如果你想要一个迷宫，它的路径通常是左-右而不是上-下，那么你可以随意选择在那个方向上打破哪面墙。这也适用于3D迷宫，在那里你可能不想要很多梯子；只是不要选择打破这么多的天花板/地板。
在我描述了这个算法之后，我14岁的儿子用Turbo-Pascal在3D中实现了它，所以我知道这个算法和这个描述实际上是有效的。这实际上是Prim算法的一个版本，除非所有的弧都有相同的代价(或者所有左右的弧都有，所有上下的弧都有，等等)。它的巧妙之处在于编号的工作方式，以找出哪些单元已经可以从其他单元到达。
https://stackoverflow.com/questions/15787800
复制相似问题
腾讯云开发者
