Wilson's Algorithm Maze Generator

Wilson’s algorithm is a loop-erased random walk method that generates uniform spanning trees for maze creation. This means that all possible mazes of a given size are equally likely to be generated, making it an unbiased maze generation technique. Wilson's algorithm can be considered an improved version of the Aldous-Broder algorithm, as it generates mazes with identical characteristics, but it runs much faster, so I haven't bothered implementing the Aldous-Broder algorithm here.

A perfect maze is a maze in which there is exactly one path from any point in the maze to any other point. That means you can't end up going around in circles, but you will often encounter dead ends, forcing you to turn around and go back.

The maze maps generated here includes a default version without any start and finish positions, so you can decide those for yourself: there will be a solution from any point in the maze to any other point. If you want inspiration, you can enable a suggested start and finish position - and even see the solution between the two.

About Wilson's Algorithm

Wilson's algorithm for generating uniform spanning trees using a loop-erased random wall was created by David Bruce Wilson.

Wilson originally introduced this algorithm in 1996 while researching random spanning trees and Markov chains in probability theory. Although his work was primarily in mathematics and statistical physics, the algorithm has since been widely adopted for maze generation due to its ability to produce perfectly uniform mazes.

How Wilson’s Algorithm Works for Maze Generation

Wilson’s algorithm ensures that the final maze is fully connected without any loops by iteratively carving paths from unvisited cells using random walks.

Step 1: Initialize

• Start with a grid filled with walls.
• Define a list of all possible passage cells.

Step 2: Choose a Random Starting Cell

• Pick any random cell and mark it as visited. This serves as the starting point of the maze during generation.

Step 3: Random Walk with Loop-Erasing

• Pick an unvisited cell and begin a random walk (moving in random directions).
• If the walk reaches an already visited cell, erase any loops in the path.
• Once the walk connects to the visited region, mark all the cells in the path as visited.

Step 4: Repeat Until All Cells Are Visited:

• Continue selecting unvisited cells and performing random walks until every cell is part of the maze.