Aldous-Broder maze algorithm
Aldous-Broder wanders the grid at random and carves a passage every time it steps into a cell it hasn't seen before.
How it works
Pick a starting cell. Move to a random neighbour, any neighbour, visited or not. If that neighbour hasn't been visited before, knock down the wall you just walked through. Keep wandering until every cell has been visited.
It is the simplest uniform maze generator: every perfect maze is equally likely. The price is speed. Near the end the walk can spend a long time wandering through finished maze looking for the last few unvisited cells.
What to watch for
Watch it fill most of the grid quickly, then crawl as it hunts for the last unvisited corners.
Properties
- Texture
- Unbiased, natural mix
- Dead ends
- Average
- Uniform
- Yes
- Speed
- Slow at the end
- Memory
- Almost none
Try it
Open the studio to carve your own Aldous-Broder maze at any size, solve it with up to four algorithms, and save the video. Or print one.
FAQ
Why is Aldous-Broder slow?
It walks at random through cells it has already carved, so finding the last few unvisited cells can take a long time.
Why use it at all?
It's tiny, needs almost no memory, and is provably unbiased.