Wilson’s Algorithm

Wilson’s algorithm is a method to generate mazes. Given something called a graph — here, a square grid of points — it will produce what’s called a spanning tree: a way to connect the points so that every point connects to every other, but without any loops. What’s more, it creates every possible spanning tree with equal probability — essentially, the one it picks is random. Wilson’s algorithm is the fastest known way to do this, and it’s a wonderful thing to watch.

First, a random point \((x_0, y_0)\) in the grid is chosen. Then, starting from another random point, a loop-erased random walk is performed: repeatedly moving up, left, down, or right, ignoring any loops that appear, until \((x_0, y_0)\) is reached. This path is then drawn in white on the canvas below. For the next step, another random black point is chosen and a random walk begins from there, continuing until it hits any white point. This method is repeated until every point is white.

Once the graph is complete, it’s filled with color, starting from the center. This isn’t part of Wilson’s algorithm, but it provides a beautiful visualization of how places in the maze that may appear close can really be far apart.

Maximum speed