This project was greatly helped by Think Labyrnth!, Jamis Buck's blog, and the maze generation algorithm Wikipedia article.
To better understand the following pseudo-code:
Initialize current to a random cell
While not every cell is visited
Initialize next to a random neighbor of current
If next is not visited
Connect current and next
Set current to next
This algorithm is one of the fastest on the site, and it allows for mazes of infinite length to be generated because it never looks at more than two rows at a time.
Pseudo-Code:
Initialize sets to an empty disjoint set
For each row
Delete from sets the data for every cell that is neither a root nor in the row
For each cell in the row that is not in sets
Add a set containing the cell to sets
Initialize current to the leftmost cell in the row
While current != the rightmost cell in the row
Initialize next to the cell directly to the right of current
If find current in sets != find next in sets
Randomly or if the row = the bottom row
Connect current and next
Union current and next in sets
Set current to next
If the row != the bottom row
For each set in sets
Randomly at least once
Connect a cell from the set in the row and the cell directly below it
This algorithm is particularly intersting because it allows for a result identical to the simplified Prim's algorithm, the recursive backtracking algorithm or anywhere in between the two depending on how it is configured. Looking at the simplicity of the algorithms pseudo-code, it's flexibility seems almost inevitable. The "index anchor" field represents which cell the algorithm is biased to pick (0 being the oldest in the tree and 1 being the newest in the tree). The "anchor bias" field represents how biased the algorithm is to the chosen anchor (0 being entirely random and 1 being guaranteed). If the anchor bias is 0, the result is identical to the simplified Prim's algorithm because a random cell will always be chosen. If both the growing tree index and the anchor bias are 1, the result is identical to the recursive backtracking algorithm because the newest cell will always be chosen, and if the newest cell has no unvisited neighbors, the algorithm backtracks to the previous cell.
Pseudo-Code:
Initialize maze to a set containing a random cell
While maze is not empty
Initialize current to a random element of maze
If current has an unvisited neighbor
Connect current and a random unvisited neighbor of current
Else
Remove current from maze
Initialize current to a random cell
While not every cell is visited
While current has an unvisited neighbor
Initialize next to a random unvisited neighbor of current
Connect current and next
Set current to next
For each cell
If the cell is unvisited and the cell has a visited neighbor
Set current to the cell
Connect current and a random visited neighbor of current
Break
Initialize sets to an empty disjoint set
Initialize walls to a set containing every cell wall
While sets has more than one set
Connect the two cells on either side of a randomly popped element of walls
This algorithm was originally called the binary tree algorithm, but since here it is compatible with non-square cell shapes with more than two sides facing a positive direction (i.e., each node of the tree can have more than two children), it was renamed to be more accurate. The result has a very obvious flow in the positive X, Y, and Z direction. There is always a path running along all three axes for the entirety of the maze at the maximum X, Y, and Z coordinates. This algorithm is incompatible with a delta grid because every other cell has no side facing the positive Z direction which would allow for isolated sections of the maze.
Pseudo-Code:
For each cell
Initialize next to a random neighbor of the cell whose coordinates are all >= those of the cell
If next exists
Connect the cell and next
The Prim's algorithm implemented on this site is the classical Prim's algorithm, which means that every wall has a static weight. In the modified version, every cell has a static weight and a random wall is chosen of the cell with the highest weight every iteration. In the simplified version, there are no static weights, so a random wall is picked every iteration. To see what the simplified version looks like, check the growing tree algorithm.
Pseudo-Code:
Assign every cell wall a random weight
Initialize frontier to a set containing the walls of a random cell
While not every cell is visited
Initialize cell1 and cell2 to the cells separated by the popped element of frontier with the highest weight
If cell1 xor cell2 is unvisited
Connect cell1 and cell2
Add the walls of cell1 and cell2 to frontier
Initialize backtrack to an empty stack
Initialize current to a random cell
While not every cell is visited
If current has an unvisited neighbor
Initialize next to a random unvisited neighbor of current
Connect current and next
Set current to next
Else
Pop backtrack and set current to the result
This algorithm is unique because it is the only algorithm that uses wall building instead of wall breaking. The "index anchor" field represents where in each section the algorithm is biased to make a division (0 being the top or left and 1 being the bottom or right). The "anchor bias" field represents how biased the algorithm is to the chosen anchor (0 being entirely random and 1 being guaranteed).
Pseudo-Code:
Break every cell wall
Define divide as a function of a section of the maze
Initialize division to a random X or Z coordinate inside the section
Build every wall inside the section with the coordinate division
Break a random wall inside the section with the coordinate division
For each of the two subsections made by the division
Call divide on the subsection
Call divide on the maze
For each row
Initialize run to an empty set
Initialize current to the leftmost cell in the row
While current exists
Add current to run
Initialize next to the cell directly to the right of current
(Randomly or if the row = the top row) and if current != the rightmost cell
Connect current and next
Else if current != the rightmost cell
Connect a random element of run and the cell directly below it
Clear run
Set current to next
Initialize maze to a set containing a random cell
While not every cell is in maze
Initialize directions to an empty map
Initialize start to a random cell not in maze
Initialize current to start
While current is not in maze
Initialize next to a random neighbor of current
Map current to the direction of next in relation to current in directions
Set current to next
Set current to start
While current is not in maze
Add current to maze
Initialize next to the neighbor of current in the direction to which current is mapped in directions
Connect current and next
Set current to next
If enabled, equations and inequalities can be used to create custom grid shapes. This is accomplished using the math.js evaluate function. For every coordinate in the specified dimensions, the equation or inequality will be used to check whether or not to place a cell there. The top left cell on the first floor has coordinates of (0, 0, 0) and coordinates increase going to the right, down, and to the following floors. To represent the width, length, and height of the grid, the variables w, l, and h are used respectively. For the coordinates of the cell being checked, x, y, and z are used. In order for a custom grid to be legal, it must be possible to connect every cell.
Example: "x/w <= z/l" would result in a right triangle with legs spanning the left and bottom sides of the grid and its hypotenuse being the diagonal starting from the top left.