prim 的算法生成迷宫缺墙

Question

所以我正在使用 prim 算法实现迷宫生成器。迷宫本身生成的很好，但是总是会缺少两个（接触的）墙。

我正在生成的迷宫（缺少右墙和底墙）：

Maze 1

此处缺少左墙和顶墙：

Maze 2

我用来生成迷宫的代码：

int _height = 50;
int _width = 50;
private bool[,] maze = new bool[_height, _width];


private void generateMaze()
{
    //_height = 50
    //_width = 50
    List<MazeCell> walls = new List<MazeCell>();
    int randX = genRand(1, _height-1);
    int randY = genRand(1, _width-1);
    maze[randX, randY] = true;
    MazeCell start = new MazeCell(randX, randY, null);

    for (int i = -1; i <= 1; i++)
    {
        for(int j = -1; j <= 1; j++)
        {
            if ((i == 0 && j == 0) || (i != 0 && j != 0))
                continue;
            try
            {
                if (maze[randX + i, randY + j])
                    continue;
            }
            catch(Exception e)
            {
                continue;
            }
            walls.Add(new MazeCell(randX + i, randY + j, start));
        }
    }

    while (walls.Count > 0)
    {
        int index = genRand(0, walls.Count - 1);
        MazeCell cur = walls[index];
        MazeCell op = cur.opposite();
        walls.RemoveAt(index);
        try
        {
            if(!maze[cur.x, cur.y])
            {
                if(!maze[op.x, op.y])
                {
                    maze[cur.x, cur.y] = true;
                    maze[op.x, op.y] = true;

                    for (int i = -1; i <= 1; i++)
                    {
                        for (int j = -1; j <= 1; j++)
                        {
                            if (i == 0 && j == 0 || i != 0 && j != 0)
                                continue;
                            try
                            {
                                if (maze[op.x + i, op.y + j])
                                    continue;
                            }
                            catch (Exception e)
                            {
                                continue;
                            }
                            walls.Add(new MazeCell(op.x + i, op.y + j, op));
                        }
                    }
                }
            }
        }
        catch (Exception e) { }
    }
}

private int genRand(int min, int max)
{
    Random rnd = new Random();
    return rnd.Next(min, max);
}

还有 mazeCell class:

public class MazeCell
{
    public int x;
    public int y;
    public bool passage = false;
    MazeCell parent;

    public MazeCell(int x, int y, MazeCell parent)
    {
        this.x = x;
        this.y = y;
        this.parent = parent;
    }

    public MazeCell opposite()
    {
        if (x.CompareTo(parent.x) != 0)
            return new MazeCell(x + x.CompareTo(parent.x), y, this);
        if (y.CompareTo(parent.y) != 0)
            return new MazeCell(x, y + y.CompareTo(parent.y), this);
        return null;
    }
}

该代码改编自 java 我在此处找到的代码：http://jonathanzong.com/blog/2012/11/06/maze-generation-with-prims-algorithm

我找不到它突然决定拆墙的地方。非常感谢任何帮助！

Answer 1

我试过你的代码，如果你把方法外的 new Random 移动到一个成员变量（所以它只创建了一次），那么它似乎工作得很好。

没有代码可以确保整个迷宫的边缘周围有边界：迷宫会愉快地徘徊到任何边缘。您看到的是每次重置 Random 造成的非随机性伪像。

如果在该方法中一遍又一遍地将随机设置为相同的种子，我也会看到长跑到两侧。

这是具有适当随机值的 15x15 的样本输出：

XXXXXXXXX X X X
X         X X X
X X XXXXXXXXXXX
X X X     X   X
XXXXXXXXX X X X
X X         X X
X XXX XXXXXXX X
  X   X   X   X
XXXXX X X XXX X
X     X X      
XXXXXXX X XXXXX
X X   X X X   X
X XXX XXXXXXX X
  X X X X      
XXX X X XXXXXXX

Answer 2

我建议更多地从基于图形的角度来解决这个问题，而不是从 "maze" 的某些特定表示。

另请参阅我对 this question 的回答。

prim 的算法生成迷宫缺墙

prim's algorithm generated maze missing walls

c#

wpf

algorithm

maze

Maze 1

Maze 2