Recently, I have started reading the book Mazes For Programmers, by Jamis Buck.
All the examples in the book are given in Ruby. So I have worked through these, to the point where I made myself some coloured mazes using the example code. See the example picture below. The darker the colour, the further the location is from the centre:
However, I think better in C# so I thought I would try re-writing the code. Plus, this makes sure that I really understand the examples. Why not then, do this in Unity, then I could build the maze in 3D and have a walk around?
Therefore, to start I created a Grid and Cell Class that do similar things to the examples in the book, except this is in C#.
First the Cell:
[csharp]
// Cell.cs
using System;
using System.Collections.Generic;
namespace Mazes
{
public class Cell
{
public Cell North { get; set; }
public Cell South { get; set; }
public Cell East { get; set; }
public Cell West { get; set; }
public int Row { get; set; }
public int Column { get; set; }
public List Links = new List();
public Cell(int row, int column)
{
Row = row;
Column = column;
}
public Cell LinkCells(Cell cell, bool biDirectional)
{
Links.Add(cell);
if (biDirectional)
{
cell.LinkCells(this, false);
}
return this;
}
public Cell UnlinkCell(Cell cell, bool biDirectional)
{
if (Links.Contains(cell))
{
Links.Remove(cell);
if (biDirectional)
{
cell.UnlinkCell(this, false);
}
}
return this;
}
public bool IsLinked(Cell cell)
{
if (Links.Contains(cell))
return true;
return false;
}
public List Neighbours()
{
List neighbours = new List();
if (North != null)
neighbours.Add(North);
if (South != null)
neighbours.Add(South);
if (East != null)
neighbours.Add(East);
if (West != null)
neighbours.Add(West);
return neighbours;
}
}
}
[/csharp]
Now the Grid:
[csharp]
// Grid.cs
using System;
using System.Collections.Generic;
using System.Linq;
namespace Mazes
{
public class Grid
{
public int Rows { get; set; }
public int Columns { get; set; }
private Cell[,] cells;
Random rand = new Random((int)DateTime.Now.Ticks);
public Grid(int rows, int columns)
{
Rows = rows;
Columns = columns;
PrepareGrid();
ConfigureCells();
}
private void PrepareGrid()
{
cells = new Cell[Rows, Columns];
for (int row = 0; row < Rows; row++)
{
for (int col = 0; col < Columns; col++)
{
cells[row, col] = new Cell(row, col);
}
}
}
public Cell GetRandomCell()
{
int row = rand.Next(Rows – 1);
int col = rand.Next(Columns – 1);
return cells[row, col];
}
public int Size()
{
return Columns * Rows;
}
private void ConfigureCells()
{
for (int row = 0; row < Rows; row++)
{
for (int col = 0; col < Columns; col++) { if (row > 0)
cells[row, col].North = cells[row – 1, col];
if (row < (Rows – 1))
cells[row, col].South = cells[row + 1, col];
if (col < (Columns – 1)) cells[row, col].East = cells[row, col + 1]; if (col > 0)
cells[row, col].West = cells[row, col – 1];
}
}
}
public Cell GetCell(int row, int col)
{
if (row >= 0 && row <= Rows) { if (col >= 0 && col <= Columns)
{
return cells[row, col];
}
}
return null;
}
public override string ToString()
{
StringBuilder builder = new StringBuilder();
builder.AppendLine("+" + new string(‘£’, Columns).Replace("£", "—+"));
for (int row = 0; row < Rows; row++)
{
string top = "|";
string bottom = "+";
for (int col = 0; col < Columns; col++)
{
var currentCell = GetCell(row, col);
string body = " ";
var east_boundary = currentCell.IsLinked(currentCell.East) ? " " : "|";
top = top + body + east_boundary;
var south_boundary = currentCell.IsLinked(currentCell.South) ? " " : "—";
bottom = bottom + south_boundary + "+";
}
builder.AppendLine(top);
builder.AppendLine(bottom);
}
return builder.ToString();
}
}
}
[/csharp]
Then, an Aldous Broder implementation:
[csharp]
//AldousBroder.cs
using System;
using System.Collections.Generic;
using System.Linq;
namespace Mazes
{
public class AldousBroder
{
public static void CreateMaze(Grid grid)
{
Random rand = new Random((int)DateTime.Now.Ticks);
Cell currentCell = grid.GetRandomCell();
int unvisited = grid.Size() – 1;
while (unvisited > 0)
{
List neighbours = currentCell.Neighbours();
int randomSample = rand.Next(neighbours.Count);
Cell neighbour = neighbours[randomSample];
if (!neighbour.Links.Any())
{
currentCell.LinkCells(neighbour, true);
unvisited–;
}
currentCell = neighbour;
}
}
}
}
[/csharp]
Finally, then to instantiate the maze in unity, a Builder script, that can be attached to an empty GameObject. Its ‘Awake’ function will build the Maze when the scene loads:
[csharp]
// Builder.cs
using UnityEngine;
using Mazes;
public class Builder : MonoBehaviour
{
public Material Floor;
public Material Walls;
private void Awake()
{
Grid grid = new Grid(30,30);
AldousBroder.CreateMaze(grid);
// Debug.Log(grid);
BuildGrid(grid);
}
private void BuildGrid(Grid grid)
{
float startX = 1, startZ = 1;
float cellSize = 2f;
float wallHeight = 2.5f;
float floorHeight = 0.1f;
// Create the floor and interior walls
for (int row = 0; row < grid.Rows; row++)
{
for (int col = 0; col < grid.Columns; col++)
{
GameObject floor = GameObject.CreatePrimitive(PrimitiveType.Cube);
floor.name = string.Format("Row {0} Col {1}", row, col);
floor.transform.position = new Vector3((startX * row * cellSize), floorHeight, (startZ * col * cellSize));
floor.transform.localScale = new Vector3(cellSize, floorHeight, cellSize);
floor.transform.GetComponent().material = Floor;
Cell currentCell = grid.GetCell(row, col);
// If the cell is not linked to the north, draw the wall
if (!currentCell.IsLinked(currentCell.North))
{
GameObject northWall = GameObject.CreatePrimitive(PrimitiveType.Cube);
northWall.name = string.Format("North Wall – Row {0} Col {1}", row, col);
northWall.transform.position = new Vector3((row * cellSize) – (cellSize / 2), wallHeight / 2, col * cellSize);
northWall.transform.localScale = new Vector3(floorHeight, wallHeight, cellSize);
northWall.transform.GetComponent().material = Walls;
}
// If the cell is not linked to the east, draw the wall
if (!currentCell.IsLinked(currentCell.East))
{
GameObject eastWall = GameObject.CreatePrimitive(PrimitiveType.Cube);
eastWall.name = string.Format("East Wall – Row {0} Col {1}", row, col);
eastWall.transform.position = new Vector3(row * cellSize, wallHeight / 2, (col * cellSize) – (cellSize / 2) + cellSize);
eastWall.transform.localScale = new Vector3(cellSize, wallHeight, floorHeight);
eastWall.transform.GetComponent().material = Walls;
}
}
}
// Create the rear wall
GameObject westWall = GameObject.CreatePrimitive(PrimitiveType.Cube);
float totalLength = cellSize * grid.Rows;
westWall.name = "Rear Wall";
westWall.transform.position = new Vector3((totalLength / 2) – (cellSize / 2), (wallHeight / 2), -(cellSize / 2));
westWall.transform.localScale = new Vector3(totalLength, wallHeight, floorHeight);
westWall.transform.GetComponent().material = Walls;
// Create South Wall
GameObject southWall = GameObject.CreatePrimitive(PrimitiveType.Cube);
southWall.name = "South Wall";
southWall.transform.position = new Vector3(totalLength – (cellSize / 2), (wallHeight / 2), (totalLength / 2) – (cellSize / 2));
southWall.transform.localScale = new Vector3(floorHeight, wallHeight, totalLength);
southWall.transform.GetComponent().material = Walls;
}
}
[/csharp]
Finally, all that is needed is to assign some materials in the unity editor for the grid and the floor, set up the first person controller and you’re away.
And then let’s have a look inside:
