Houston's Algorithm maze algorithm
Houston's algorithm starts with Aldous-Broder's random walk and switches to Wilson's algorithm once about a third of the maze is carved.
How it works
Aldous-Broder is quick at first, because nearly every step lands on a new cell, but crawls at the end hunting for the last few. Wilson's is the opposite: slow at first, fast once there's a big tree to hit. Houston runs Aldous-Broder until a third of the cells are in the maze, then finishes with Wilson's loop-erased walks.
Both halves pick from all possible mazes evenly, so the result looks like either one: unbiased, with lots of short dead ends.
What to watch for
Watch a wandering walk scatter corridors across the grid, then long new branches snake in from every side to join it up.
Properties
- Texture
- Even, lots of short dead ends
- Dead ends
- Many
- Uniform
- Close to uniform
- Speed
- Faster than either half alone
- Memory
- One walk
Try it
Open the studio to carve your own Houston's Algorithm maze at any size, solve it with up to four algorithms, and save the video.
FAQ
Why switch at one third?
That's roughly where Aldous-Broder starts wasting most of its steps on cells it has already visited, and where Wilson's walks start hitting the tree quickly.