Wilson's Algorithm maze algorithm
Wilson's algorithm builds a maze from loop-erased random walks, and every possible maze is equally likely.
How it works
Start with one cell in the maze. Pick any cell outside it and take a random walk until you hit the maze. Whenever the walk crosses its own path, erase the loop it just made. When it reaches the maze, carve the loop-free path in. Repeat from another cell outside the maze until there are none left.
The loop erasing is what makes it special: Wilson's algorithm picks uniformly from every possible perfect maze on the grid, with no bias toward long or short corridors. The first walks are slow because the target is tiny, then it speeds up as the maze grows.
What to watch for
Watch the first path take a while to appear, then new branches arrive faster and faster as there is more maze to bump into.
Properties
- Texture
- Unbiased, natural mix
- Dead ends
- Average
- Uniform
- Yes
- Speed
- Slow start, fast finish
- Memory
- The current walk
Try it
Open the studio to carve your own Wilson's Algorithm maze at any size, solve it with up to four algorithms, and save the video. Or print one.
FAQ
What does 'uniform' mean for a maze generator?
Every possible perfect maze on the grid is equally likely to come out. Most fast generators are biased toward a particular texture.
Wilson's or Aldous-Broder?
Both are uniform. Wilson's is usually much faster, especially near the end.