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