Mazes for Programmers

Wilson’s Algorithm

Wilson’s algorithm was developed by David Bruce Wilson, a principle 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.

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 ...