Sometimes you need a maze for your games or just a procedurally generated level. In Wikipedia you will find about “Maze Algorithm” some algorithms that are easy to implement. Now we would like to use the example of the “depth-first search algorithm” to create a 3D maze generator in Unity. That means, our maze should not only have ways in the two-dimensional plane, but ways may as well go up or down.

Explanation of the algorithm in wikipedia:

- Make the initial cell the current cell and mark it as visited
- While there are unvisited cells
- If the current cell has any neighbours which have not been visited
- Choose randomly one of the unvisited neighbours
- Push the current cell to the stack
- Remove the wall between the current cell and the chosen cell
- Make the chosen cell the current cell and mark it as visited

- Else if stack is not empty
- Pop a cell from the stack
- Make it the current cell

- If the current cell has any neighbours which have not been visited

### Unity project

We’ll come back to the algorithm later, let’s start with Unity. First, we will create a new project. Since we want to visualize our labyrinth later, we choose 3D as Preset.

In our project we will create a new script and call it MazeGenerator3D.cs. This script should execute the algorithm.

The created class MazeGenerator3D derives from the class MonoBehaviour, as primarily all newly created classes do. We do not need that at the moment, so we remove the derivative and the automatically created functions Start () and Update (). The script should now look like this:

1 2 3 4 5 6 7 |
using System.Collections; using System.Collections.Generic; using UnityEngine; public class MazeGenerator3D { } |

Because the algorithm is based on cells, we need another class that describes the properties of a cell in the labyrinth. To do this we create a new script and call it MazeCell.cs. We also delete the derivative and the functions here.

### Basic thoughts about a cell

Now let’s look at how a cell might look like. Primarily, our cell is a room with not quite an arbitrary number of walls. For better understanding, we imagine a two-dimensional square. This square has four walls. Each of these walls can provide a passage to the next cell or be closed. Our cell can as well have only three walls. Then our two-dimensional labyrinth would build up out of triangles. If our cell has six walls, we could have a two-dimensional labyrinth made of hexagons – or, now it’s beyond imagination, a three-dimensional labyrinth made of cubes. This is exactly what we need for our three-dimensional labyrinth.

We now had examples that are practically feasible. A cell with eight walls, for example, in a two-dimensional maze would not be feasible if all the cells are the same size and all the walls are supposed to have a potential neighbor cell. The following picture illustrates this problem:

### Properties of a cell

Since we need cubes with exactly six sides for our three-dimensional maze, we use an array of size 6 to set the walls.

We determine exactly which which wall goes in which direction. We use true and false to save whether the wall exists (true) or not (false).

In this tutorial we define it as you see in the following picture. We choose this numbering because the sum of opposite walls always gives 5 and thus it is easy to find out which wall is on the opposite side.

Finally we need a property of whether our algorithm has already visited this cell or not. Again, a bool variable is enough.

In the constructor of our class, we set the array size and set all walls to exist (= true).

The finished code of our class MazeCell should look like this:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
using System.Collections; using System.Collections.Generic; using UnityEngine; public class MazeCell { public bool[] walls; public bool visited; public MazeCell() { walls = new bool[6] { true, true, true, true, true, true }; visited = false; } } |

### Preparation and properties of class MazeGenerator3D

Our algorithm needs to know what size the maze to create should have. To do this, we create three variables in the class MazeGenerator3D:

1 2 3 |
private int sizeX; private int sizeY; private int sizeZ; |

We also need our cells, which we store in a three-dimensional array and, as the algorithm dictates, a stack in which we store the order of the cells visited. The size of the array from the stack equals the total number of cells in the maze. This is calculated from length * width * height.

1 2 |
public MazeCell[,,] cells; private MazePosition[] stack; |

The class MazePosition contains only the properties of the position in space. We declare them in the same file as the class MazeGenerator3D:

1 2 3 4 5 6 7 8 9 10 |
public class MazePosition { public int x, y, z; public MazePosition(int posX, int posY, int posZ) { x = posX; y = posY; z = posZ; } } |

In the constructor, we define the size of the array for the cells and initialize each cell in a loop. Furthermore, the size of the stack is determined and the start position of the algorithm is set randomly. The first cell is then marked as visited at the same time. So far, the walls are all locked (true), so they do not need to be changed here. As a parameter of the constructor, we let us transfer the size of our maze:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
public MazeGenerator3D (int size_X, int size_Y, int size_Z) { sizeX = size_X; sizeY = size_Y; sizeZ = size_Z; cells = new MazeCell[sizeX, sizeY, sizeZ]; // Initialisieren aller Zellen for (int x = 0; x < sizeX; x++) { for (int y = 0; y < sizeY; y++) { for (int z = 0; z < sizeZ; z++) { cells[x, y, z] = new MazeCell(); } } } // Size of the array is equal to the count of all cells in the maze // The initialization of the individual positions are later. stack = new MazePosition[sizeX * sizeY * sizeZ]; // Only the first position is initialized and set at random int startX = Random.Range(0, sizeX); int startY = Random.Range(0, sizeY); int startZ = Random.Range(0, sizeZ); stack[0] = new MazePosition(startX, startY, startZ); positionInStack = 0; // The first cel is set to 'visited' cells[startX, startY, startZ].visited = true; } |

### Programming of the algorithm

The algorithm makes it necessary to find out which of the neighboring cells have not yet been visited. For this purpose, we now create the checkNeighbours () method. The method gives us an array with the walls through which we can go to an unvisited cell. If the size of the array is 0, there are no unvisited cells around the current cell.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
private int[] checkNeighbours(MazePosition currentPosition) { List<int> result = new List<int>(); int x = currentPosition.x; int y = currentPosition.y; int z = currentPosition.z; // Check wall 0 if (x - 1 >= 0) // Are we still in the size of the maze { if (cells[x - 1, y, z].visited == false) result.Add(0); // Add wall 0 } // Check wall 5 if (x + 1 < sizeX) // Are we still in the size of the maze { if (cells[x + 1, y, z].visited == false) result.Add(5); // Add wall 5 } // Check wall 1 if (y - 1 >= 0) // Are we still in the size of the maze { if (cells[x, y - 1, z].visited == false) result.Add(1); // Add wall 1 } // Check wall 4 if (y + 1 < sizeY) // Are we still in the size of the maze { if (cells[x, y + 1, z].visited == false) result.Add(4); // Add wall 4 } // Check wall 2 if (z - 1 >= 0) // Are we still in the size of the maze { if (cells[x, y, z - 1].visited == false) result.Add(2); // Add wall 2 } // Check wall 3 if (z + 1 < sizeZ) // Are we still in the size of the maze { if (cells[x, y, z + 1].visited == false) result.Add(3); // Add wall 3 } return result.ToArray(); } |

Als letztes müssen wir noch die Methode generate() implementieren. Hier wird in einer Schleife Schritt für Schritt durch die Zellen gegangen und überprüft ob es weitere unbesuchte Nachbarzellen gibt. Der Code ist im folgenden in den Kommentaren erläutert:

Finally, we have to implement the method generate (). In a loop we go step by step through the cells and checked if there are other unvisited neighboring cells. The code is explained in the comments below:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
public void generate() { // Because the algorithm always goes backwards if there are no unvisted neighbours, // we continue executing until we are back at the beginning of our stack while (positionInStack >= 0) { // The cell we have to check is saved in the stack at the current position int x = stack[positionInStack].x; int y = stack[positionInStack].y; int z = stack[positionInStack].z; // Check the cells around (neighbours) int[] possibleNeighbours = checkNeighbours(stack[positionInStack]); if (possibleNeighbours.Length > 0) // Unvisited cells are found { // Choose a radom wall and open it to the next cell int wall = possibleNeighbours[Random.Range(0, possibleNeighbours.Length)]; // Open the wall by setting the wall to false cells[x, y, z].walls[wall] = false; // Get the new coordinates if (wall == 0) x--; else if (wall == 5) x++; else if (wall == 1) y--; else if (wall == 4) y++; else if (wall == 2) z--; else if (wall == 3) z++; // Set the new cell to visitied and open the wall on the opposite side of the previous cell // and increase the stack by one and set the new position positionInStack++; stack[positionInStack] = new MazePosition(x, y, z); cells[x, y, z].visited = true; cells[x, y, z].walls[5-wall] = false; } else // No unvisited cells are found { // So go one position back in stack positionInStack--; // and check again if there are unvisited cells around } } } |

That’s all. Another tutorial will follow soon, briefly explaining how the maze can be represented in Unity and used as a level.

You can download the complete project for unity here: