Mazes for Programmers

The Aldous-Broder Algorithm

The Aldous-Broder algorithm was developed independently by both David Aldous, a professor at UC Berkeley, and Andrei Broder, currently a Distinguished Scientist at Google. It is almost as simple to implement as the Binary Tree algorithm. The idea is just this: Start anywhere in the grid you want, and choose a random neighbor. Move to that neighbor, and if it hasn’t previously been visited, link it to the prior cell. Repeat until every cell has been visited.

Easy, right? It’s that random walk, the aimless, directionless meandering from cell to cell, that is at the root of this algorithm’s ability to avoid being biased. Sadly, as we’ll see it also means that it can take a long time to run.

Let’s walk through it once ...