Wilson's Algorithm

Background

Wilson’s algorithm was developed by David Bruce Wilson, a principal researcher at Microsoft and an affiliate associate professor of mathematics at the University of Washington. Like Aldous-Broder, this algorithm depends on the idea of a random walk but with a twist. It performs what is called a loop-erased random walk, which means that as it goes, if the path it is forming happens to intersect with itself and form a loop, it erases that loop before continuing on.

Wilson’s algorithm explained and illustrated

The algorithm starts by choosing a point on the grid—any point—and marking it visited. Then it chooses any unvisited cell in the grid and does one of these loop-erased random walks until it encounters a visited cell. At that point, it adds the path it followed to the maze, marking each cell as visited along that path, and then it goes again. The process repeats until all the cells in the grid have been visited. Let's look at the steps below:

That's a mouthful! Let's walk through it together through the slides below.

1. We choose some random cell to start and mark it visited. We start with the northwest corner.

2. Next, we choose another cell at random. We call this the current cell (marked with a smiley in the slides below), and it is where we begin our loop-erased random walk. Note that we do not consider this cell visited.

3. From here, we choose a random neighbor and make that neighbor the current cell repeatedly. We'll move in this way four times. Remember that we are not actually carving passages or modifying the grid at all here. We’re just noting the path we’re taking.

4. Here’s where the “loop-erased” part of the loop-erased random walk comes into play. We’ve (randomly) decided to move east, which causes us to intersect our current path. A loop is created, so we erase that loop before moving on.

5. We continue in this fashion until we stumble upon a cell that has already been visited. The first time through, this means we have to find the one cell that started out visited. It can take a while, but eventually, it’ll find it.

6. Once we have that path, we carve it into the maze by linking all the cells along that path and marking them visited.

The algorithm has been explained with illustrations in the slides below.