O'Reilly logo

Mazes for Programmers by Jamis Buck

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required