Implement Mazes in Unity2D

Implement Mazes in Unity2D

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.

  1. 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)
  2. 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.

This figure shows the 2d scene with camera manipulator 2d 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 stack
Code 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.

The four walls directions
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.

The figure shows the neighbour cells of the current cell in dark blue. In this case, all four neighbour cells are not visited yet.
The figure shows the neighbour cells of the current cell in dark blue. In this case, 1, 3, and 4 cells are neighbours that are not visited. cell 2 to the right is marked visited and so is not added to the list of neighbours.
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 left square is the current cell. From the current cell, we are moving right. Meaning we will need to remove the wall with the RIGHT direction from the current cell, and subsequently, we will need to remove the LEFT wall from the neighbouring cell.
A corridor is formed after removing the two walls.

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 namespace
Code 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.

Set the Cell prefab to the CellPrefab field of the MazeGenerator component.

Click Play and run the application. You should see the maze generation in action.

Below is a gif of the maze creation process.

A gif animation showing the formation of the Maze iteratively using the backtracking algorithm.

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

  1. Reusable Finite State Machine using C++
  2. Flocking and Boids Simulation in Unity2D
  3. Runtime Depth Sorting of Sprites in a Layer
  4. Implement Constant Size Sprite in Unity2D
  5. Implement Camera Pan and Zoom Controls in Unity2D
  6. Implement Drag and Drop Item in Unity
  7. Graph-Based Pathfinding Using C# in Unity
  8. 2D Grid-Based Pathfinding Using C# and Unity
  9. 8-Puzzle Problem Using A* in C# and Unity
  10. Create a Jigsaw Puzzle Game in Unity
  11. Implement a Generic Pathfinder in Unity using C#
  12. Create a Jigsaw Puzzle Game in Unity
  13. Generic Finite State Machine Using C#
  14. Implement Bezier Curve using C# in Unity
  15. Create a Jigsaw Tile from an Existing Image
  16. Create a Jigsaw Board from an Existing Image
  17. Solving 8 puzzle problem using A* star search
  18. A Configurable Third-Person Camera in Unity
  19. Player Controls With Finite State Machine Using C# in Unity
  20. Finite State Machine Using C# Delegates in Unity
  21. Enemy Behaviour With Finite State Machine Using C# Delegates in Unity
  22. Augmented Reality – Fire Effect using Vuforia and Unity
  23. Implementing a Finite State Machine Using C# in Unity
  24. Solving 8 puzzle problem using A* star search in C++
  25. What Are C# Delegates And How To Use Them
  26. How to Generate Mazes Using Depth-First Algorithm

Leave a Reply

Your email address will not be published. Required fields are marked *