2

我正在尝试创建一个迷宫生成器，为此我在 C# 中实现了随机化 Prim 算法。

但是，生成的结果是无效的。我不知道这是我的渲染，还是无效的实现。因此，对于初学者来说，我想让某人看一下实现：

迷宫是细胞的矩阵。

var cell = maze[0, 0];
cell.Connected = true;

var walls = new HashSet<MazeWall>(cell.Walls);

while (walls.Count > 0)
{
    var randomWall = walls.GetRandom();
    var randomCell = randomWall.A.Connected ? randomWall.B : randomWall.A;

    if (!randomCell.Connected)
    {
        randomWall.IsPassage = true;
        randomCell.Connected = true;

        foreach (var wall in randomCell.Walls)
            walls.Add(wall);
    }

    walls.Remove(randomWall);
}

这是渲染结果的示例：

渲染迷宫 http://dl.dropbox.com/u/1744224/Upload/primrecur.png

编辑好的，让我们看看渲染部分：

private void MazePanel_Paint(object sender, PaintEventArgs e)
{
    int size = 20;
    int cellSize = 10;

    MazeCell[,] maze = RandomizedPrimsGenerator.Generate(size);

    mazePanel.Size = new Size(
        size * cellSize + 1, 
        size * cellSize + 1
    );

    e.Graphics.DrawRectangle(Pens.Blue, 0, 0, 
        size * cellSize, 
        size * cellSize
    );

    for (int y = 0; y < size; y++)
    for (int x = 0; x < size; x++)
    {
        foreach(var wall in maze[x, y].Walls.Where(w => !w.IsPassage))
        {
            if (wall.Direction == MazeWallOrientation.Horisontal)
            {
                e.Graphics.DrawLine(Pens.Blue, 
                    x * cellSize, y * cellSize, 
                    x * cellSize + cellSize, 
                    y * cellSize
                );
            }    
            else
            {
                e.Graphics.DrawLine(Pens.Blue,
                    x * cellSize,
                    y * cellSize, x * cellSize,
                    y * cellSize + cellSize
                );
            }
        }
    }
}

我想，要理解这一点，我们需要查看 MazeCell 和 MazeWall 类：

namespace MazeGenerator.Maze
{
    class MazeCell
    {
        public int Column 
        {
            get;
            set; 
        }

        public int Row 
        { 
            get; 
            set; 
        }

        public bool Connected 
        { 
            get; 
            set; 
        }

        private List<MazeWall> walls = new List<MazeWall>();

        public List<MazeWall> Walls
        {
            get { return walls;  }
            set { walls = value; }
        }

        public MazeCell()
        {
            this.Connected = false;
        }

        public void AddWall(MazeCell b)
        {
            walls.Add(new MazeWall(this, b));
        }
    }

    enum MazeWallOrientation
    {
        Horisontal,
        Vertical,
        Undefined
    }

    class MazeWall : IEquatable<MazeWall>
    {
        public IEnumerable<MazeCell> Cells 
        { 
            get
            {
                yield return CellA;
                yield return CellB;
            }            
        }

        public MazeCell CellA
        {
            get; 
            set;
        }

        public MazeCell CellB
        {
            get;
            set;
        }

        public bool IsPassage 
        { 
            get; 
            set; 
        }

        public MazeWallOrientation Direction
        {
            get
            {
                if (CellA.Column == CellB.Column)
                {
                    return MazeWallOrientation.Horisontal;
                }
                else if (CellA.Row == CellB.Row) 
                {
                    return MazeWallOrientation.Vertical;
                }
                else
                {
                    return MazeWallOrientation.Undefined;
                }
            }
        }

        public MazeWall(MazeCell a, MazeCell b)
        {
            this.CellA = a;
            this.CellB = b;

            a.Walls.Add(this);
            b.Walls.Add(this);

            IsPassage = false;
        }

        #region IEquatable<MazeWall> Members

        public bool Equals(MazeWall other)
        {
            return (this.CellA == other.CellA) && (this.CellB == other.CellB);
        }

        #endregion
    }
}
4

2 回答 2

2

这只是一个想法：

即使您没有发布将墙添加到单元格的代码，我相信这是逻辑错误。一个单元格有 4 面墙，但两个相邻的单元格只有 7 面墙。不是8。

移除 randomWall 时，您还需要从另一个单元格中移除相应的墙。

更详细地说：如果您的AddWallsToMaze算法为每个单元格添加 4 面墙，则存在重复的墙。

例如：
CellA 与 CellB 有一面墙。我们称它为 Wall1。
CellB 与 CellA 有一堵墙。这是 Wall2 而不是 Wall1。
应该是 Wall1。

于 2010-04-07T09:13:07.770 回答
0

解决方案是纠正单元格绘制方式的渲染错误。我正在做右和下墙，并渲染左和上墙。

private static void RenderCell(PaintEventArgs e, int cellSize, int y, int x, MazeWall wall, Pen pen)
{
    if (wall.Direction == MazeWallOrientation.Horisontal)
    {
        e.Graphics.DrawLine(pen,
            x * cellSize,
            y * cellSize + cellSize,
            x * cellSize + cellSize,
            y * cellSize + cellSize
        );
    }
    else
    {
        e.Graphics.DrawLine(pen,
            x * cellSize + cellSize,
            y * cellSize,
            x * cellSize + cellSize,
            y * cellSize + cellSize
        );
    }
}

我对结果并不完全满意。我想我会尝试另一种算法，这似乎不像我希望的那样格式良好。

于 2010-04-07T23:38:15.220 回答