This tutorial will show how to implement mazes in Unity2D by applying the backtracking algorithm with an explicit stack.
Contact me
Find the GitHub repository of this tutorial at https://github.com/shamim-akhtar/tutorial-maze.
Introduction to Mazes
Not too far ago, mazes were somewhat central to video games. Arguably, the original first-person shooter game, literally named Maze, was created by students on Imlac computers at a NASA laboratory in 1974 – source Wikipedia.
A maze is a kind of game where a player moves in pathways with many branches to find a way
out or reach a specific target.
The maze-generation process is the process of designing the position of paths and walls in the Maze.
There are many methods/algorithms to generate a maze
We can create a maze by starting with a predetermined arrangement of cells (a rectangular grid in our case) with walls between them. The maze generator will traverse these cells iteratively and remove walls in four possible directions, thus forming a maze.
The Unity Project
Download the starter package for this tutorial. Create a new Unity2D project and import the starter-package.package file.
The starter package comprises two prefabs.
- The 2d camera manipulation, and (Read Implement Camera Pan and Zoom Controls in Unity2D to understand and implement a 2d camera manipulation for pan an zoom controls)
- A maze cell that comprises 4 walls for a cell. For simplicity the walls form a square grid.
Drag and drop the Canvas_CameraManipulation2D prefab from Resources/Prefabs folder. Set the Main Camera game object to the M Camera field of the CameraManipulator2D component of Canvas_CameraManipulation2D prefab.
Maze Generation
We will apply the backtracking algorithm with an explicit stack to implement our Maze. There are many other ways of implementation. For an exhaustive list of implementations, do check out the Wikipedia page.
The Pseudo Code
Choose the initial cell, mark it as visited and push it to the stack
While the stack is not empty
Pop a cell from the stack and make it a current cell
If the current cell has any neighbours which have not been visited
Push the current cell to the stack
Choose one of the unvisited neighbours
Remove the wall between the current cell and the chosen cell
Mark the chosen cell as visited and push it to the stackCode language: PHP (php)The Cell Class
We will put our Maze related pure C# classes in the Procedural namespace. Go ahead and create a new C# file and name it Cell. A cell represents one square unit in the grid.
First, we will need to define the four possible directions that we will need to traverse. Create an enum type as shown below.
namespace Procedural
{
// The directions types for maze
// propagation.
public enum Directions
{
UP,
RIGHT,
DOWN,
LEFT,
NONE,
}
Code language: C# (cs)Create a class and call it Cell. A cell comprises the x and y index of the grid.
// A cell in the maze.
public class Cell
{
public int x;
public int y;
Code language: C# (cs)Add a constructor that takes in the indices as input parameters.
// constructor
public Cell(int c, int r)
{
x = c;
y = r;
}
Code language: C# (cs)Now, add two variables. The first one named visited is of boolean type. It indicates if the algorithm has already visited the cell. We will require this variable while forming the Maze.
The second variable is an array of size 4 with boolean type. It stores the direction that this specific cell connects with its neighbour cell.
// visited flag.
// it is used while creating the maze.
public bool visited = false;
public bool[] flag =
{
true,
true,
true,
true
};
Code language: C# (cs)For convenience, we have added a delegate onSetDirFlag. Go ahead add this delegate to the Cell class.
// a delegate that is called
// when we set a direction flag
// to the cell.
public delegate void
DelegateSetDirFlag(
int x,
int y,
Directions dir,
bool f);
public DelegateSetDirFlag onSetDirFlag;
Code language: C# (cs)Create a function that allows the setting of the direction flag.
// set direction flag for the cell.
// a direction flag shows which
// dircetion the cell opens up to.
public void SetDirFlag(
Directions dir,
bool f)
{
flag[(int)dir] = f;
onSetDirFlag?.Invoke(x, y, dir, f);
}
}
Code language: JavaScript (javascript)The Maze Class
Create a new C# file, name it Maze and add a new class called Maze. This class holds a two-dimensional array of cells, the number of rows and the number of columns.
namespace Procedural
{
public class Maze
{
// the number of rows and columns
private int mRows;
private int mCols;
// the 2d array of cells
private Cell[,] mCells;
Code language: C# (cs)Add the constructor.
// constructor
public Maze(int rows, int cols)
{
mRows = rows;
mCols = cols;
// initiaze all the cells.
mCells = new Cell[mCols, mRows];
for (var i = 0; i < mCols; i++)
{
for (var j = 0; j < mRows; j++)
{
mCells[i, j] = new Cell(i, j);
}
}
}
Code language: C# (cs)Add a couple of utility functions.
public Cell GetCell(int i, int j)
{
return mCells[i, j];
}
public int GetCellCount()
{
return mRows * mCols;
}Code language: C# (cs)The constructor initializes the two-dimensional array of cells.
Add a function that returns the neighbours of a specific cell that have not been visited. This function returns a list of tuples of direction and the cell.
public List<Tuple<Directions, Cell>>
GetNeighboursNotVisited(
int cx,
int cy)
{
List<Tuple<Directions, Cell>> neighbours =
new List<Tuple<Directions, Cell>>();
foreach (Directions dir in Enum.GetValues(
typeof(Directions)))
{
int x = cx;
int y = cy;
switch (dir)
{
case Directions.UP:
if (y < mRows - 1)
{
++y;
if (!mCells[x, y].visited)
{
neighbours.Add(new Tuple<Directions, Cell>(
Directions.UP,
mCells[x, y])
);
}
}
break;
case Directions.RIGHT:
if (x < mCols - 1)
{
++x;
if (!mCells[x, y].visited)
{
neighbours.Add(new Tuple<Directions, Cell>(
Directions.RIGHT,
mCells[x, y])
);
}
}
break;
case Directions.DOWN:
if (y > 0)
{
--y;
if (!mCells[x, y].visited)
{
neighbours.Add(new Tuple<Directions, Cell>(
Directions.DOWN,
mCells[x, y])
);
}
}
break;
case Directions.LEFT:
if (x > 0)
{
--x;
if (!mCells[x, y].visited)
{
neighbours.Add(new Tuple<Directions, Cell>(
Directions.LEFT,
mCells[x, y])
);
}
}
break;
default:
break;
}
}
return neighbours;
}
Code language: PHP (php)Create a function that removes the cell wall based on the direction. The procedure takes in the two-dimensional index of the cell (x, y) and the direction.
public void RemoveCellWall(
int x,
int y,
Directions dir)
{
if (dir != Directions.NONE)
{
Cell cell = GetCell(x, y);
cell.SetDirFlag(dir, false);
}
Directions opp = Directions.NONE;
switch (dir)
{
case Directions.UP:
if (y < mRows - 1)
{
opp = Directions.DOWN;
++y;
}
break;
case Directions.RIGHT:
if (x < mCols - 1)
{
opp = Directions.LEFT;
++x;
}
break;
case Directions.DOWN:
if (y > 0)
{
opp = Directions.UP;
--y;
}
break;
case Directions.LEFT:
if (x > 0)
{
opp = Directions.RIGHT;
--x;
}
break;
}
if (opp != Directions.NONE)
{
Cell cell1 = GetCell(x, y);
cell1.SetDirFlag(opp, false);
}
} // end of function RemoveCellWall
} // end of class Maze
Code language: C# (cs)In the above implementation, we first remove the wall of the cell based on the direction. Then we remove the wall in the opposite direction of the neighbouring cell we are moving into from the current cell.
The Maze Generator Monobehavior Class
Right-click on the Unity editor’s Hierarchy window and create a new empty game object. Call it MazeGenerator. Select this game object and add a new script component from the Inspector. Name this script MazeGenerator.
Double-click and open the file in Visual Studio (or any editor that you prefer).
Add the following variables.
public class MazeGenerator : MonoBehaviour
{
// the number of rows and columns
// set this via the editor.
public int rows = 11;
public int cols = 11;
public GameObject CellPrefab;
// The 2d array of monobehavious maze cells.
MazeCell[,] mMazeCells;
// The maze
public Maze maze
{
get;
private set;
}
// The stack for backpropagation.
Stack<Cell> _stack = new Stack<Cell>();Code language: C# (cs)We generate the Maze in the Start method.
void Start()
{
int START_X = -cols / 2;
int START_Y = -rows / 2;
maze = new Maze(rows, cols);
mMazeCells = new MazeCell[cols, rows];
for (int i = 0; i < cols; ++i)
{
for (int j = 0; j < rows; ++j)
{
GameObject obj = Instantiate(CellPrefab);
obj.transform.parent = transform;
Cell cell = maze.GetCell(i, j);
cell.onSetDirFlag = OnCellSetDirFlag;
obj.transform.position = new Vector3(
START_X + cell.x,
START_Y + cell.y,
1.0f);
mMazeCells[i, j] = obj.GetComponent<MazeCell>();
}
}
CreateNewMaze();
}
Code language: JavaScript (javascript)We now implement the CreateNewMaze method.
public void CreateNewMaze()
{
// Remove the left wall from
// the bottom left cell.
maze.RemoveCellWall(
0,
0,
Directions.LEFT);
// Remove the right wall from
// the top right cell.
maze.RemoveCellWall(
cols - 1,
rows - 1,
Directions.RIGHT);
// Push the first cell into the stack.
_stack.Push(maze.GetCell(0, 0));
// Generate the maze in a coroutine
// so that we can see the progress of the
// maze generation in progress.
StartCoroutine(Coroutine_Generate());
}Code language: JavaScript (javascript)I have provided comments within the code for your understanding. The process is simple. We first open up the left wall for the bottom left and right wall for the top-right cells to provide an entry and exit from the Maze.
Next, we add two utility methods to highlight a specific cell or remove highlights from all the cells.
public void HighlightCell(int i, int j, bool flag)
{
mMazeCells[i, j].SetHighlight(flag);
}
public void RemoveAllHightlights()
{
for (int i = 0; i < cols; ++i)
{
for (int j = 0; j < rows; ++j)
{
mMazeCells[i, j].SetHighlight(false);
}
}
}
public void OnCellSetDirFlag(
int x,
int y,
Directions dir,
bool f)
{
mMazeCells[x, y].SetActive(dir, f);
}
Code language: C# (cs)We will now create the essential method that iterates through the backpropagation algorithm for the maze generation. We will implement this as a Step function, meaning we implement one iteration.
bool GenerateStep()
{
if (_stack.Count == 0) return true;
Cell c = _stack.Peek();
var neighbours = maze.GetNeighboursNotVisited(c.x, c.y);
if (neighbours.Count != 0)
{
var index = 0;
if (neighbours.Count > 1)
{
index = Random.Range(0, neighbours.Count);
}
var item = neighbours[index];
Cell neighbour = item.Item2;
neighbour.visited = true;
maze.RemoveCellWall(c.x, c.y, item.Item1);
mMazeCells[c.x, c.y].SetHighlight(true);
_stack.Push(neighbour);
}
else
{
_stack.Pop();
mMazeCells[c.x, c.y].SetHighlight(false);
}
return false;
}Code language: C# (cs)Finally, we create the coroutine to generates the Maze by repeatedly calling the GenerateStep function above until the Maze is completed. The completion of Maze happens when the stack size becomes empty.
IEnumerator Coroutine_Generate()
{
bool flag = false;
while (!flag)
{
flag = GenerateStep();
//yield return null;
yield return new WaitForSeconds(0.05f);
}
//MazeGenerationCompleted = true;
} // end of function Coroutine_Generate
}// end of Procedure namespaceCode language: JavaScript (javascript)To show the animation of the maze creation process, I have set the yield return for the coroutine to a specific duration. You may change this duration, or you may yield return null.
Go to Unity editor. Drag and drop the Cell prefab (Resources/Prefabs/Maze) to the CellPrefab field of the MazeGenerator component. Set values for rows and cols.
Click Play and run the application. You should see the maze generation in action.
Below is a gif of the maze creation process.
In the following tutorial, we will apply pathfinding to this Maze using our generic pathfinder.
Read the tutorial Implement a Generic Pathfinder in Unity using C# to learn how to create a generic pathfinder in C#.
You may also read 8-Puzzle Problem Using A* in C# and Unity, 2D Grid-Based Pathfinding Using C# and Unity and Graph-Based Pathfinding Using C# in Unity to learn how to apply our generic pathfinder to a different set of problems.
Read My Other Tutorials
- Reusable Finite State Machine using C++
- Flocking and Boids Simulation in Unity2D
- Runtime Depth Sorting of Sprites in a Layer
- Implement Constant Size Sprite in Unity2D
- Implement Camera Pan and Zoom Controls in Unity2D
- Implement Drag and Drop Item in Unity
- Graph-Based Pathfinding Using C# in Unity
- 2D Grid-Based Pathfinding Using C# and Unity
- 8-Puzzle Problem Using A* in C# and Unity
- Create a Jigsaw Puzzle Game in Unity
- Implement a Generic Pathfinder in Unity using C#
- Create a Jigsaw Puzzle Game in Unity
- Generic Finite State Machine Using C#
- Implement Bezier Curve using C# in Unity
- Create a Jigsaw Tile from an Existing Image
- Create a Jigsaw Board from an Existing Image
- Solving 8 puzzle problem using A* star search
- A Configurable Third-Person Camera in Unity
- Player Controls With Finite State Machine Using C# in Unity
- Finite State Machine Using C# Delegates in Unity
- Enemy Behaviour With Finite State Machine Using C# Delegates in Unity
- Augmented Reality – Fire Effect using Vuforia and Unity
- Implementing a Finite State Machine Using C# in Unity
- Solving 8 puzzle problem using A* star search in C++
- What Are C# Delegates And How To Use Them
- How to Generate Mazes Using Depth-First Algorithm
A committed and optimistic professional who brings passion and enthusiasm to help motivate, guide and mentor young students into their transition to the Industry and reshape their careers for a fulfilling future. The past is something that you cannot undo. The future is something that you can build.
I enjoy coding, developing games and writing tutorials. Visit my GitHub to see the projects I am working on right now.
Educator | Developer | Mentor