Unity Tutorial 3D Maze Generator – Part 1

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:


  1. Make the initial cell the current cell and mark it as visited
  2. While there are unvisited cells
    1. If the current cell has any neighbours which have not been visited
      1. Choose randomly one of the unvisited neighbours
      2. Push the current cell to the stack
      3. Remove the wall between the current cell and the chosen cell
      4. Make the chosen cell the current cell and mark it as visited
    2. Else if stack is not empty
      1. Pop a cell from the stack
      2. Make it the current cell

 

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:

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:

Bild: Beispiel für Zellen im Labyrinth

 

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.

Bild: Nummerierung der Wände einer Zelle

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:

 

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:

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.

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

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:

 

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.

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:

 

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:

Download Tutorial Files

One reply

  1. how to make the initial cell the current cell?

Leave a Reply

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