How do you make a maze?

With a mountain, a pick, and a lot of code...

Maze generation is a fascinating topic, and many scholars have spent their time devising algorithms to create mazes. The one used for this game is based on the Growing Tree algorithm (see also this research paper), with a few modifications to make the maze "interesting".

Cells and links

This process works with any node map with a specific boundary for inside and outside of the maze. Each cell, or node, is a location you can occupy, and contains links to other nodes. Most people easily relate to a 2D or 3D grid, but the nodes do not have to correspond to (x, y, z) coordinates. Hexagons and octagon/square grids can also be used. In fact, for cities that have twisty and winding streets, intersections can be thought of as cells, and the streets treated as links. But for this game, the 3D grid is used because it makes the maps easy to draw.

Growing the maze

Initially, all cells are flagged as "unused", and all links are treated as walls that prevent travel between cells. A starting cell that exists at the boundary of the maze is chosen, and that cell is marked as used. The link outside of the maze is also marked as "open", allowing travel out. This entrance is also added to a list of cells that possibly can be used to move to a cell that is unused. As a modification to this algorithm, the game's maze generator creates 2 or more entrances at the start and adds them all to their own list.

Next, a cell is picked off the list of available cells and checked to see if there are any links to unused cells. The cell chosen may be the last cell added to the list, the first cell added to the list, or one at random. This game chooses a random cell from the list, giving higher weight to newer cells. If there are no unused cells adjacent to the selected cell, the cell is removed from the list and another cell is chosen. If there is an unused cell, the link(s) between cells are opened, the new cell is marked as used, and this cell is added to the list. When there are no more cells on the list of cells to check, the algorithm ends. This game goes through a list for each entrance in order, picking a new cell to use each time until that entrance has access to no more unused cells.

Try it with the demo: Next carves one step at a time and Auto keeps going on its own. The list beside the grid is the list of cells still waiting to be checked.

Finding the exit

After all cells are used, one cell that is at the maze boundary is opened up to the outside, providing a path out. To get the longest path, the A* path finding algorithm (also see the Red Blob Games website) can be used to find the boundary cell with the longest distance from the entrance and use that as the exit. To make this game more interesting, the A* algorithm is used to find the cells that are furthest from their entrances, then the links between neighboring cells that are the furthest from both entrances are opened up. This generally creates the longest path between entrances, which keeps mazes from becoming "too easy to solve" when entrances are close to each other.

Doors, keys and fair play

Once the passages are carved, the generator places locked doors across some of them and hides the key for each door somewhere the player can reach before they need it. It can also turn a few passages into one-way walls. Doors and one-way walls can easily create a trap, such as a key hidden behind its own door or a one-way passage into a part of the maze with no way out. So the generator then walks the maze the way a player would, checking that the exit can always be reached and that there is no place a player could get stuck. If it finds a problem, it repairs the maze before you ever see it.

The generator is open source: you can read the code and run it yourself at github.com/wilminator/randomaze. To see the result in action, play today's maze, or read How to Play first.