Maze generation

O(rows·cols)

This builds a maze with the recursive backtracker — a randomized depth-first search. Every cell starts solid. From the top-left room it picks a random neighbour two cells away, knocks out the wall between them, and moves there; when a cell has no unvisited neighbours left it backtracks until one does. Because each cell is entered exactly once, the passages form a spanning tree of the grid: a "perfect" maze with exactly one route between any two cells and no loops. It runs in time linear in the number of cells. The same carved grid is then ready for the pathfinders to solve.

Click a cell to toggle a wall
Grid
Edit the input and press Play

How it works

  1. Start with every cell walled off.
  2. From the current cell, pick a random unvisited neighbour two cells away.
  3. Knock out the wall between them and move there.
  4. At a dead end, back up to the last cell with an unvisited neighbour — repeat until all are carved.

Pseudocode

1recursiveBacktracker(grid):          # O(rows·cols)2  every cell starts solid3  carve(cell):4    mark cell as a passage5    for each neighbour 2 cells away, in random order:6      if neighbour not yet carved:7        knock out the wall between them8        carve(neighbour)              # recurse, backtrack at dead ends9  carve(top-left room)                # one path between any two cells