john nesky's maze maker

random seed:
animation controls:
animation rate:
slide show rate:
presets:
max grid width/height:
max cell count:
cell/wall pixel size:
hue shift rate:
hue shift type:
lightness:
extend vs fork probability:
extend turn bias:
on collision, try a different:
fork cell range:
Up/Down/Left/Right bias:
Download as:

Maze Algorithm

These mazes are generated with an algorithm that is similar in principle to the Growing Tree algorithm.

The algorithm starts with a single cell. If you pause the algorithm animation, then press the "reset" button, you will see this cell alone. You can then press the "step" button repeatedly to watch the algorithm incrementally grow the maze by extending it into new cells.

There are different types of cells, distinguished by how many adjacent cells they connect to. A cell that has just been added to the maze is a "dead-end", meaning it only connects to the one adjacent cell that came before it. This cell can become connected to second adjacent cell, converting it into a "hall" or "path" cell between two other cells. Later, another branch may grow out of this cell, turning it into a "forked" cell.

Whenever the algorithm is about to grow the maze, it randomly decides to either extend an existing dead-end into a path, or fork off from an existing path, with a probability based on the appropriate slider on this page.

The algorithm keeps two hidden lists of cells that it can potentially grow from. The first list only contains dead-end cells, and the second list contains hall cells. When the algorithm has chosen to extend a dead-end, it takes the most recent available dead-end cell from the first list, adds a new dead-end cell next to it, and inserts the original cell into the second list since it is now a hall. When the algorithm has chosen to fork off from an existing path, it instead takes a random hall cell from the second list and starts a new branch from it by adding a dead-end cell next to it.

To grow out from existing cell, the algorithm has to decide which direction to grow in. The probabilities of each direction are weighted based on the corresponding sliders on this page. If all of the options are occupied, then the cell will be discarded from the lists and a different cell will be selected to grow from.

For more details, you can read the source code using either github or right-click -> "View Page Source".