Rendering a random generated maze in WinForms.NET

Question

Hi

I'm trying to create a maze-generator, and for this I have implemented the Randomized Prim's Algorithm in C#.

However, the result of the generation is invalid. I can't figure out if it's my rendering, or the implementation that's invalid. So for starters, I'd like to have someone take a look at the implementation:

maze is a matrix of cells.

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);
}

Here's a example on the rendered result:

Edit Ok, lets have a look at the rendering part then:

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
                );
            }
        }
    }
}

And I guess, to understand this we need to see the MazeCell and MazeWall class:

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
    }
}

Answer 1

This is just a thought:

Even though you have not posted the code where you add walls to a cell, I believe that is the logical error. A single cell has 4 walls but two adjoining cells have only 7 walls. Not 8.

You need to remove the corresponding wall from the other cell aswell when removing the randomWall.

To elaborate in a bit more detail: If your AddWallsToMaze algorithm adds 4 walls to each cell then there are duplicate walls.

Ex:
CellA has a wall with CellB. Let's call it Wall1.
CellB has a wall with CellA. This is Wall2 NOT Wall1.
It should be Wall1.

Answer 2

The solution was to correct the rendering mistake in how the cells were drawn. I were doing right&bottom walls, and rendering left&top walls.

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
        );
    }
}

I'm not perfectly happy with the result. I think I'll try another algorihm, this doesn't seem as wellformed as I'd hoped.