Skip to content

Instantly share code, notes, and snippets.

@dowlingw
Created August 26, 2013 14:35
Show Gist options
  • Save dowlingw/6342082 to your computer and use it in GitHub Desktop.
Save dowlingw/6342082 to your computer and use it in GitHub Desktop.
A stupid attempt at writing a depth-first maze generator in C#
internal class Maze
{
public uint DimX { get; private set; }
public uint DimY { get; private set; }
public int ExitIdx { get; private set; }
private MazeCell[,] _cells;
public bool[,] Grid { get; private set; } // true denotes there is no wall in this block
public Maze(uint dimX, uint dimY)
{
DimY = dimY;
DimX = dimX;
_cells = new MazeCell[DimX, DimY];
Grid = new bool[2*DimX,2*dimY];
}
public void Generate()
{
// Generate completely barren maze
for (uint i = 0; i < 2*DimX; i++)
{
for (uint j = 0; j < 2 * DimY; j++)
{
Grid[i, j] = true;
}
}
// Generate an unvisisted maze
for (uint i = 0; i < DimX; i++)
{
for (uint j = 0; j < DimY; j++)
{
_cells[i, j] = new MazeCell(this,i,j);
}
}
// Okay we'll need a RNG for this
var rng = new Random();
// Pick a random cell on the bottom to start with
ExitIdx = rng.Next(0, (int) (DimY - 1));
var exitCell = Get(DimX - 1, ExitIdx);
// Start traversing the maze
exitCell.Visit(rng,Direction.Nowhere);
}
public MazeCell Get(long x, long y)
{
// Return if this is an invalid coordinate
if (x < 0 || y < 0) return null;
if (x >= DimX || y >= DimY) return null;
return _cells[x, y];
}
public void RemoveWallBetween(MazeCell from, Direction fromDirection)
{
var gridX = 2*from.X;
var gridY = 2*from.Y;
switch (fromDirection)
{
case Direction.Down:
Grid[gridX-1, gridY] = false;
break;
case Direction.Right:
Grid[gridX, gridY-1] = false;
break;
case Direction.Left:
Grid[gridX, gridY+1] = false;
break;
case Direction.Up:
Grid[gridX+1, gridY] = false;
break;
}
}
}
internal enum Direction
{
Nowhere,
Up,
Down,
Left,
Right
}
internal struct Neighbour
{
public Direction Direction;
public MazeCell Cell;
}
internal class MazeCell
{
private readonly Maze _owner;
private List<Neighbour> _cachedNeighbors;
public bool Visited { get; protected set; }
public uint X { get; private set; }
public uint Y { get; private set; }
public List<Neighbour> Neighbours()
{
// Generate the cache of neighbours if we don't have it already
if (_cachedNeighbors == null)
{
_cachedNeighbors = new List<Neighbour>(4);
AddNeighborToCache(0, -1, Direction.Left);
AddNeighborToCache(0, 1, Direction.Right);
AddNeighborToCache(-1, 0, Direction.Up);
AddNeighborToCache(1, 0, Direction.Down);
}
return _cachedNeighbors;
}
private void AddNeighborToCache(int deltaX, int deltaY, Direction direction)
{
var newFriend = _owner.Get(X + deltaX, Y + deltaY);
if (newFriend != null)
{
_cachedNeighbors.Add(new Neighbour(){Cell = newFriend, Direction = direction});
}
}
public MazeCell(Maze owner, uint pX, uint pY)
{
_owner = owner;
X = pX;
Y = pY;
}
public void Visit(Random rng, Direction direction)
{
Visited = true;
// Contrary to the popular saying, good neighbours have NO fences!
if (direction != Direction.Nowhere)
{
_owner.RemoveWallBetween(this,direction);
}
Neighbours().OrderBy( x => rng.Next() ).ToList().ForEach(delegate(Neighbour neighbour) { if(!neighbour.Cell.Visited) neighbour.Cell.Visit(rng,neighbour.Direction); });
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment