时间戳

首页 > 解决方案 > prim 算法生成迷宫缺失的墙壁

c# - prim 算法生成迷宫缺失的墙壁

问题描述

所以我正在使用 prim 算法实现一个迷宫生成器。迷宫本身生成得非常好，但是总是会丢失两堵（接触的）墙。

我正在生成的迷宫（右墙和底墙不见了）：

迷宫 1

这里缺少左墙和顶墙：

迷宫 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

我找不到它突然决定拆除墙壁的地方。任何帮助是极大的赞赏！

标签： c#wpfalgorithmmaze

解决方案

我尝试了您的代码，如果您将new Random方法外部移动到成员变量（因此它只创建一次），那么它似乎工作得很好。

没有代码可以确保整个迷宫的边缘有边界：迷宫会愉快地一直游到任何边缘。您所看到的是每次重置 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

推荐阅读