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类：

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

我建议从基于图形的角度而不是从“迷宫”的某些特定表示来解决这个问题。

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