The Aldous-Broder Algorithm
Explore the Aldous-Broder algorithm to understand how it uses a random walk approach for unbiased maze generation. Learn the step-by-step process, benefits, and challenges of this method including its simplicity and potential for long runtimes as it visits each cell randomly until all are linked.
We'll cover the following...
We'll cover the following...
Background
The Aldous-Broder algorithm was developed independently by both David Aldous, a professor at UC Berkeley, and Andrei Broder, 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.