Maze — Wilson

O(rows·cols) expected

Wilson's algorithm is the elegant one: it produces an unbiased maze, where every possible maze layout is exactly equally likely (a uniform spanning tree). It seeds the maze with a single room, then repeatedly starts a random walk from some unvisited room. The walk wanders freely; whenever it crosses its own path it erases the loop it just made, and the moment it bumps into the existing maze it stops and the whole loop-erased path is carved in. Early walks are long (the maze is small), but they get shorter as the maze fills, giving expected linear time. Unlike the backtracker and Prim's — which have characteristic textures — Wilson's has no bias at all.

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

How it works

  1. Seed the maze with one room.
  2. From a random unvisited room, take a random walk.
  3. Whenever the walk loops back on itself, erase the loop.
  4. When the walk reaches the maze, carve its whole path in; repeat until none are left.

Pseudocode

1wilsonMaze(grid):                    # O(rows·cols) expected2  seed the maze with one room3  while unvisited rooms remain:4    random-walk from an unvisited room,5    erasing any loop the walk forms,6    until it reaches the maze7    carve the loop-erased path in8  # every maze equally likely (uniform spanning tree)