Maze Generation Algorithms

As part of an idea to create a 3d maze game, I needed to be able to generate random maze layouts. After reading this wikipedia page, I got a general picture of how one might go about this task. I then came across this great article which went into a greated depth on more different kinds of algorithms and their properties.

From that second article, this table was very useful for selecting which algorithms I would use:

Using the knowledge gained from the articles above, I chose to try and write the recursive backtracker algorithm. That algorithm can be seen below:

Make an 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

and the result is:

Although the backtracker algorithm produces some long paths that make it reasnobly difficult to solve in 2d when presented an overview from above, in 3d the maze is simple, you just follow the path and you end up at the end as the majority of the time (especially in smaller mazes), you can see the dead ends from the main path so you know not to take them.

So to try and make them a little more difficult to solve in 3d, I coded a modified version of the prims algorithm. This algorithm can be seen below:

Each cell is one of three types: 
        (1) 'In': The cell is part of the Maze and has been carved into already
        (2) 'Frontier': The cell is not part of the Maze and has not been carved into yet, but is next to a cell that's already 'in'
        (3) 'Out': The cell is not part of the Maze yet, and none of its neighbors are 'in' either. 

Pick a cell
Make it 'in'
Set all its neighbours to 'frontier'
While there are frontier cells
        Choose a random 'frontier cell'
        Remove wall between it and an adjacent 'in' cell
        Set it as 'in'
        Set all its neighbours which are 'out' to 'frontier'

and the result is:

Overall, as stated above, the backtracker algorithm is best for generating 2d mazes to be solved from above but when walking around in 3d inside the mazes, the prims algorithm makes escaping more difficult as it is really disorientating walking down all the dead-ends.

Of course, you can solve the mazes in 2d from the ones generated above or if you want them to be generated instantly without waiting, you can see them side by side here. And if you want to attempt escaping a maze in 3d, have a go here