Exploring Mazes

Algorithm Descriptions

Simple random walk (SRW, aka "depth-first search") is arguably the simplest algorithm. This produces mazes with relatively long paths, and few dead ends. ("Puzzle" mode asks you to identify the starting point of a SRW maze.)

Start in a randomly-chosen cell.
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.
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.

Wilson's algorithm produces every possible maze with equal probability, by performing a series of random walks starting from an "unused" cell, ending when the walk hits a "used" cell.

Choose a random cell, and mark it as "used."
Start in a randomly-chosen unused cell (call it "START").
Do a random walk—keeping track of the path taken—until you stumble into a "used" cell (call it "END").
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."
If unused cells remain, return to step 2.

Both Kruskal's algorithm and Prim's algorithm are methods of finding a minimal-cost spanning tree for an edge-weighted graph. When used to create a maze, the walls corresponding to the edges—all with equal weight—so when choosing a wall to remove, we pick one at random (rather than choosing the "cheapest" edge).

For Kruskal, we repeatedly choose a random wall from the maze, and then remove it (provided that doing so would not create a "loop" of connected cells).

Kruskal: Make a list of every available wall.
Choose a wall and remove it from the list.
If there is no path between the two cells on either side of that wall, remove it.
If all cells are connected, we are done; otherwise, return to step 2.

For Prim, we choose a random starting cell, then "grow" the tree (maze) out from that starting cell.

Choose a random starting cell C₀ and put it in USED_CELLS.

True Prim: Repeatedly pick a random boundary wall of the current set of used cells.	Variation 1: Repeatedly pick a random used cell, and then a random unused neighbor of that cell.	Variation 2: Repeatedly pick a random (unused) neighbor of a used cell, then a wall between that cell and a used cell.
Create WALL_LIST consisting of all the walls of C₀. Choose a random wall W from WALL_LIST, and remove it from the list. If W is next to a cell C which is not in USED_CELLS: erase W, add C to USED_CELLS, and add all of the C's walls to WALL_LIST. If WALL_LIST is empty, we are done. Otherwise, return to step 3.	If USED_CELLS is empty, we are done. Otherwise, choose a random cell C from USED_CELLS. If all neighbors of C already belong to USED_CELLS: remove C from the list, and return to step 2.1. Otherwise: choose a random unused neighbor C' of C, remove the wall between C and C', add C' to USED_CELLS, and return to step 2.1.	Create NBR_LIST consisting of all neighbors of C₀. Choose a random cell C from NBR_LIST, and remove it from the list. One or more of C's walls separate it from a cell in USED_CELLS. Choose at random one of those walls, and remove it. Add C to USED_CELLS, and add to NBR_LIST all of the unused cells adjacent to C. If NBR_LIST is empty, we are done. Otherwise, return to step 3.2.