Note: This page has been tested fairly thoroughly, but I would appreciate bug reports, as well as suggestions for improvement.

All mazes start with each "cell"—square, triangle, or hexagon—completely isolated (surrounded by walls). Walls are removed until what is left is a "perfect" maze, meaning that there is exactly one path from any cell to any other cell. The algorithms differ in how they choose which walls to remove. You can watch some of these algorithms in action on my maze generation page. More detailed descriptions for most of these algorithms can be found at Think Labyrinth!.

The available algorithms are:

• Random walk/"Depth-first search"
  1. Start in a randomly-chosen cell.
  2. If the current cell has at least one unvisited neighbor, choose one at random, knock down the walls between the current cell and the new cell, move into the new cell, and return to step 2.
  3. If the current cell has no unvisited neighbors, backtrack into the cell from which we "broke into" the current cell, then return to step 2. Maze is finished when we backtrack into the cell in which we started.
• Kruskal's algorithm
  1. Make a list of every available wall.
  2. Choose a wall and remove it from the list.
  3. If there is no path between the two cells on either side of that wall, remove it.
  4. If all cells are connected, we are done; otherwise, return to step 2.
• Wilson's algorithm:
  1. Choose a random cell, and mark it as "used."
  2. Start in a randomly-chosen unused cell (call is "START").
  3. Do a random walk—keeping track of the path taken—until you stumble into a "used" cell (call it "END").
  4. Remove walls along the path from START to END. If any cells on that path were visited more than once during the walk, only remove the wall in the most recent direction. Mark all cells on that path (including START) as "used."
  5. If unused cells remain, return to step 2.
• Eller's algorithm:
  1. Randomly connect some of the cells on the top row of the maze. Make a list of the sets of connected cells. (A cell which is not connected to any other cell is in a set by itself.)
  2. For each connected set, make at least one connection between it and the next row. Update the connection sets. (A cell in the next row which is not connected to other cells constitutes a new connection set.)
  3. If the next row is NOT the bottom row: On the next row, randomly connect some of the cells (and update the connection sets), but do NOT connect two cells that are already in the same set. Then return to step 2.
  4. On the bottom row, connect each pair of adjacent cells if they are not already in the same set.
• Prim's algorithm
  1. Choose a random starting cell, and put it in a list of "used" cells.
  2. Choose a random used cell from the list. (If the list is empty, we are done.)
  3. If it has no unused neighbors, remove it from the list, and return to step 2.
  4. Otherwise, choose a random unused neighbor of that cell, remove the wall between them, add the new cell to the list, and return to step 2.
• Prim's algorithm (alternate)
  1. Choose a random starting cell, and make a list of all the cells adjacent to it.
  2. Choose a random cell from the list, and remove it from the list. (If the list is empty, we are done.)
  3. One or more walls of that cell separate it from a used cell. Choose at random one of those walls, and remove it.
  4. Add to the list all of the unused cells adjacent to this cell. (Don't put a cell in the list if it is already there.)
  5. Return to step 2.
• Prim's algorithm (alternate #2)
  1. Choose a random starting cell, and make a list of all the walls of that cell.
  2. Choose a random wall from the list, and remove it from the list. (If the list is empty, we are done.)
  3. If one of the two cells adjacent to that wall is "unused," remove that wall, and add to the list all of the walls of the previously-unused cell.
  4. Return to step 2.
• Prim+DFS
  1. Choose a random starting cell, and put it in a list of "used" cells.
  2. Choose a random used cell from the list. (If the list is empty, we are done.)
  3. If it has no unused neighbors, remove it from the list, and return to step 2.
  4. Otherwise, perform a random walk from the current cell, adding each visited cell to the list.
  5. When the random walk hits a dead end, return to step 2. (Do not backtrack.)
• Prim-Geometric
  1. Choose a random starting cell, and put it in a list of "used" cells.
  2. Choose a random used cell from the list. (If the list is empty, we are done.)
  3. If it has no unused neighbors, remove it from the list, and return to step 2.
  4. Otherwise, for each unusedneighbor, flip a coin which comes up heads with probability p. If the coin turns up heads, remove the wall between them and add the new cell to the list.
  5. Return to step 2.
• Bacterial growth algorithm
  1. Choose a random starting cell, and put it in a list of "used" cells.
  2. Scramble the list—that is, put it in in random order. (If the list is empty, we are done.)
  3. For every cell in the list, if it has no unused neighbors, remove it from the list.
  4. Otherwise, choose a random unused neighbor of that cell, remove the wall between them, and add the new cell to the list.
  5. Return to step 2.
• Bacterial growth algorithm (vers. 2)
  1. Choose a random starting cell, and put it in a list of "used" cells.
  2. Scramble the list—that is, put it in in random order. (If the list is empty, we are done.)
  3. For every cell in the list, if it has no unused neighbors, remove it from the list.
  4. Otherwise, choose a random neighbor (used or unused) of that cell. If it is unused, remove the wall between them, and add the new cell to the list.
  5. Return to step 2.