Procedurally Generated 3D Mazes
Mazes, known to be a collection of twisting paths and convoluted routes made with the intent to cause confusion, there have been a wide variety of mazes made over all these years. One of the most infamous types of maze is the Labyrinth of Crete, so elaborately confusing and convoluted that even its creator, Daedalus, could hardly solve it. It is strongly implied through the descriptions of this labyrinth that it should contain endless dead ends, twisting routes with branching paths and confusing turns, and logically it would stand to reason that such a structure that is impossible to solve would contain such things. However, in almost all visual representations of the Cretan Labyrinth, it is a unicursal maze, that is, it is a singular path from the start to the end.
Since the visual look of the labyrinth that it is known for does not seem to match up to what has been described, I wanted to instead create my own version of the labyrinth. In doing this, I would be able to create a structure akin to the level of complexity that was detailed in the myth. While it may not be able to be classed as a labyrinth, since that is now synonymous with the unicursal path, it will still be classified as a path due to the confusing routes and intent to disorientate anyone who solves it.
Therefore I decided to procedurally generate mazes in Unity using a variety of algorithms. As there are many algorithms that can create different mazes, I only used algorithms that have obvious differences, whether that be with the maze generation or the visual aspect of the maze. Due to my intent to create a maze that cannot be solved easily, the mazes generated will be different each time, in order for it to be impossible to memorise a route.
Research
There are many different variations on the basic mazes. Just by changing dimensions, the way the path is created, how the path is created, or even the general shape of the overall maze itself, there can be vastly different mazes produced.
In terms of dimension, the standard maze is 2D, where it can be fully represented on a single plane. These are the most common types of mazes and are what the original algorithms are created for. 3D mazes are layered versions of 2D mazes, where instead of just 4 directions that a path can take, there are 6: North, South, East, West, Up, and Down. 3D mazes themselves can be implemented in multiple ways where either the maze can go in every direction, or alternatively, each layer is its own individual maze with a singular route up or down at one location and the 3D structure comes from the stacked layers. These kinds of mazes typically make a cuboid structure, and 3D mazes in every direction are what this dissertation is focused on.
Regardless of dimension, there is also routing, which refers to the geometry of the paths within the mazes. Perfect mazes are those that are simply connected. There are no loops, close circuits, or inaccessible areas in these mazes. This also means that each perfect maze features exactly 1 solution. Because of this, perfect mazes can be represented with a spanning tree, with the branches of the tree representing the various paths. Braided mazes are those that feature no dead ends, and instead are filled with loops and coiling pathways, hence the name. Because of loops these mazes can be a lot harder to solve as it is easy for people to get turned around going in circles.
The final four algorithms selected are:
Recursive Backtracking
This algorithm works by randomly walking through a grid to any unvisited cells, clearing any walls on its way, and adding every visited cell to a stack. Once it can no longer pick any direction, it backtracks along the route taken until it can go in a new direction. This is repeated until every cell has been visited and it is back at the cell it started on. It creates long wandering paths with multiple branches and ensures that every cell has been visited by marking them as such. However, it can be hard on memory, as the stack size required is proportional to the size of the maze.
Recursive Backtracking Example
The first implementation of this code was focused on only a single-layered, 2D maze. To implement this, I first created a path which was an empty list of cells to which the visited cells could be added. This was to serve as the stack, and when the list contained 1 item, and there were no more cells to which a path could be made the algorithm was marked as complete.
So that a new cell could be randomly selected and added to the stack, I worked on selected directions and destroying walls next. The initial direction selection was by a random number generator that selected between a range of 0 (inclusive) and 4 (exclusive). Each number would then correspond to a direction. I set it up so that 0 = North, 1 = South, 2 = East, and 3 = West. As the grid worked off of coordinates, for each direction either the row (x coordinate) would increment or decrement, or the column (y coordinate) would. Therefore, depending on which direction was selected, different walls would be destroyed. Since each cell within the maze had 4 walls, in order to create a path between two cells, two walls would have to be destroyed - being the wall in the appropriate direction for the current cell, then the wall of the opposite direction in the next cell, so that they could properly connect. Because of this, each direction had slightly different variations on what walls had to be destroyed. As I was focused on getting the algorithm to first correctly function with the intent to optimise it afterwards, all of the wall destruction was implemented into if statements along with checks to see if there was a cell in that direction.
At this point, the first two points of the algorithm had been covered, but it could not repeat any steps. This part was a simpler step to implement as all it required was a while loop with a check at the end of every iteration. For this, the check was if the stack only had one cell in it, and there were no unvisited adjacent cells.
For the backtracking, as every other part of the algorithm had been implemented, it was also fairly simple. Each new cell that was randomly picked to be the next step of the path was added onto the stack. If no direction can be picked, then instead the last item on the stack is removed, effectively backtracking through the path.
Having done the 2D implementation of the algorithm, developing it into 3D wasn’t as complicated. To begin with, as the current layout was set up for 2D mazes only, I had to modify it so that multiple layers could be added. Following that, all this algorithm required was two more directions - Up and Down. At this point in the project, the code was fairly impractical for a system that required multiple algorithms. Previously I had focused on getting the Recursive Backtracking algorithm correctly implemented, but with that done I had to then work at tidying the code, in order to make it both more efficient, and more practical.
When focusing on efficiency, the directions were a major area that needed improvement. For the initial 2D implementation, when choosing a random direction a number between and including 0-3 would be generated. Depending on what number was generated, the algorithm would destroy a certain set of walls. Code-wise, this resulted in 4 if statements for each of the directions and then a further 2 when the 3D aspect was implemented. I instead used an enum class for the directions, which aided in making the code more readable and compact. This allowed me to remove the if statements and put the code that destroyed surfaces into a separate function that could take in a direction and destroy the appropriate surfaces.
Binary Tree (northeast bias)
The binary tree algorithm works by starting in one of the corners of a grid and systematically making its way through the grid, destroying walls in one of two directions for each cell. For a northeast bias, the algorithm picks between the north wall or the east wall to destroy each time. If it cannot destroy the wall in one direction, it is forced to pick the other, and if neither can be picked then the cell is left. Because of this, for each maze generated with this algorithm, there are two sides that are completely clear - in this case, these are the north and east sides. The algorithm is named as such due to the fact that the maze can always be represented with a binary tree. This algorithm is guaranteed to create a perfect maze each time without having to keep its state. As it is memory-less, there is in theory no limit to the size of mazes it can generate. However, because there are two sides that are guaranteed to be clear each time, it can be an easier maze to navigate.
Binary Tree Example
Even though this algorithm has a very simple premise, it wasn’t as simple to implement due to a particular feature of the Binary Tree algorithm. The algorithm is as follows:
For every cell in the grid, make a path in one of two directions.
While the first part of this is easy to implement with for loops iterating over every coordinate in the grid one by one, the second section caused a few problems. On account of how the algorithm works, each maze generated has a bias in a set direction out of northeast, northwest, southeast, and southwest, where the sides of the maze in that direction are completely clear of walls. For most cells in the grid, when a random direction is selected, it is possible to make a path in that said direction. However, for the northmost and eastmost cells within the grid the direction selection is a little different. In the case of the northmost cells, if the direction “north” is selected it is not possible to make a route in that direction. The only possible direction is east, and vice versa for the eastmost cells.
Originally I had implemented the direction selection without many checks, so there would be occasions within the grid where no paths were made as it was not possible to make a path in the direction chosen. Because of this I then added a while loop that would repeat until a wall was destroyed. While this did work and prevented cells from being skipped, it was an inefficient temporary solution, and it could mean that there would be multiple iterations of the while loop if invalid directions were repeatedly selected. It was mainly inefficient as for every direction selected, valid or not, it would run the function to destroy walls before the code would be stopped if it could not destroy walls. Because of this, I then added the relevant checks for the north and east directions so that the code for destroying walls would not be run unless the direction was a viable choice for the cell.
However, there was a large downside to this that I had not initially realised. As explained previously, the bias has a point where the row and column connect. In the case of the northeast bias, this cell is the northmost, eastmost cell, where it is not possible to go in either direction. This resulted in the algorithm being stuck in an endless loop where it would repeatedly select invalid directions for the cell, as every direction was invalid. This meant that I had to add an extra check at the beginning, where for that one particular cell, it would skip the loop and move onto the next cell.
With the algorithm now working on a single-layered maze, I moved onto adding the extra layers. Having worked through the direction selection in the 2D implementation, it made the third direction easier to understand when adding it into the algorithm. I used Up as my third direction, so that the random direction generation could be as a number from 0-3, then multiplied. This is because of how the enum directions were ordered, and which number is casted to which direction. In this case, North = 0, East = 2, Up = 4. Therefore, choosing Up meant that the casting to a direction enum was kept as a simple section of code, instead of having to add in unnecessary if statements to check certain cases. Following that, I added in the extra checks for the new direction to the surface destruction and the cell where the row, column, and now layer meet up.
Growing tree (oldest)
This algorithm works by randomly selecting a start location and adding it to a list. A path is carved to a neighbouring cell that has not yet been visited and said neighbouring cell is added to the list. A cell is selected from the list which becomes the new current cell from which a path is carved. If the cell selected has no unvisited neighbours, it is removed from the list. The mazes created by this can vary a lot depending on how the next cell is selected. If it is a random selection it behaves like Prim’s, if it is the newest cell added it behaves like the Recursive Backtracking. In this case, it is the oldest cell in the list that is selected each time, resulting in the long corridors spanning out from the starting location. Growing Tree is fairly fast, as the cell removal from the list helps speed up the iterations. Same as the Recursive Backtracking, it too has memory use proportional to the maze size. The long corridors and lack of branching paths can mean that the mazes generated can be easy to solve, however, there are simple modifications such as 3D or braiding that can make it much more confusing and harder to solve.
Growing Tree Example
Because of some of the similarities this algorithm shares with Recursive Backtracking in how it is implemented, the implementation went smoothly, without much trouble. Again, I started with making an empty list as I needed somewhere to store the cells. As the Recursive Backtracking also used a list of cells, the implementation was already in place to easily make a new empty list.
Following that, the first main difference of this was the random starting location, which is generated by selecting a random number in between 0 and the maximum layers, rows, or columns. This guarantees that the starting location will be different each time the algorithm is run. However, after that the algorithm yet again is very similar to the Recursive Backtracking with its while loops, in that while there are unvisited adjacent cells to the one it is currently on, it will loop through random directions, building the paths in the viable directions.
The most notable differences in the implementation of the algorithm compared to the Recursive Backtracking is that for every time a direction is selected in which to make a path, the next cell is also added to the list. The other main difference is the one that was mentioned at the start of this implementation - how the next cell is selected. As adding to a list appends the cell to the end, the oldest cell in the list is the one that is at the start, index[0]. Therefore, each time a new cell is selected, it is the cell at the start of the list. To replicate other algorithms, all that has to be changed is how the next cell is selected.
Once again, due to the aforementioned similarities this implementation of the algorithm shares with the Recursive Backtracking algorithm, the 3D implementation was straightforward. As with the previous algorithms when implementing the 3D version, I had to include the third coordinate that defined the layers, which for this was mainly located in the initial starting cell location generation. I also expanded the range of directions the algorithm could pick between, so that it could travel in the 3D space when generating the maze.
Prim’s
This algorithm works by selecting a random starting location and adding any potential cell it can “spread to” to a list, and from that start cell it carves a path to a potential cell. It then picks a cell from the list of potential cells and from there spreads. If the cell selected has no cell surrounding it that has not been visited it is removed from the list of potential cells. It is completed once there are no longer any potential cells. Prim’s creates a minimal spanning tree from an undirected weighted graph. It tends to produce mazes that feature many short dead ends, which can make it confusing for larger mazes. This too has memory use proportional to the maze size.
Prim’s Example
This algorithm was originally based on Prim’s algorithm that is used to create minimal spanning trees in weighted undirected graphs. While the maze variant still maintains similarities to the original, as the sides of the maze cells are unweighted, instead of selecting the side with the lowest weight the selection is random. The algorithm still produces a minimal spanning tree, starting from a random location. This algorithm is as follows:
Add a random cell to an empty list.
Select a random cell from the list, and if there are unvisited neighbours, make a path in a random direction. Else, remove the cell from the list.
Repeat 2 until the list is empty.
While this algorithm also uses a list, it is used in a slightly different manner. However, as it is still a list of cells, the implementation again was straightforward for this part of the implementation. Instead of keeping track of every cell that has been visited but still has unvisited adjacent neighbours, this list keeps track of all the potential cells that the algorithm can select, where they are not necessarily of one particular path. This algorithm also uses a random starting location same as Growing Tree, so the implementation for that too was without any trouble.
The more complex part of this implementation was in the main part of the algorithm where the walls are destroyed. For this a random cell from the list is selected to be the new position. If this cell doesn’t have any neighbouring cells that haven’t been visited then it is removed from the list, otherwise a random direction is selected and if possible, a path is made. While this implementation itself is fairly simple, working out how I should implement it took some time to work out, as the original algorithm works slightly differently from the maze algorithm. As the maze can only spread from the end of the visited cells, maintaining a list of those potential cells from which it can spread ensures that the algorithm is implemented correctly.
Having implemented three other algorithms into 3D, implementing this last one into 3D was an uncomplicated process. Yet again, I added in the extra coordinate for the random starting location, and ensured that all the directions were added in.
Braiding
As mentioned in research, a braided maze is one that has no dead ends. While the other types of routing would depend on their own algorithms separate to the maze algorithms, the braid is one that can work in conjunction with the four algorithms implemented. In order to do the braiding, I first had to locate all the dead ends in the mazes. Since a dead end is a cell that only has one way in and out, any cell that only has one surface missing is counted as a dead end. Therefore I created a new class that looped through every cell in the grid after the main algorithm has been run, and would return a list of every cell that counted as a dead end. However, because I was trying to count the surfaces that had been “destroyed” by the algorithms, I had to change how the surfaces were destroyed so that it was possible to only count the remaining walls assigned to the cells. Previously, the GameObjects were destroyed using a function that came with Unity, called Destroy(). However, while the destroyed objects would be gone, they were still assigned to the cell, and therefore there was no way to tell them apart from the intact surfaces. Because of this, the functions that were used to destroy surfaces had to be modified so that they instead set the walls that are destroyed to be inactive instead of active. This way, there was a clear difference between the surfaces assigned to the cells, and the dead ends could be detected.
Following this, since there was now a list of all the cells that were dead ends, they could be run through an algorithm that would destroy an extra surface in the cells, so that there was a route through them. This would work through each cell in the list, first checking if that cell still counted as a dead end. If it did not it would skip the cell. Otherwise, a randomly selected surface would be destroyed.
Rooms
These are another variant to mazes that can be added without interfering with the main four algorithms. As a room is just an area within the maze where all the walls and pillars are destroyed all that needs to be done is to specify a room size based on the size of the maze, and give it a random starting location that does not come in contact with the sides of the maze. While the first part of this - specifying the scale of the room, was fairly simple, the random location of the room was a bit more complex as the correct parameters had to be calculated so that the room would not collide with the edges of the mazes.
Demonstrating the generation of a variety of mazes
