Mazes for Programmers

Chapter 5Adding Constraints to Random Walks

Aimless random walking may be a good strategy if you absolutely need a perfectly unbiased algorithm, but for most purposes it’s kind of overkill. An algorithm with the right kind of bias can often generate mazes that convey atmosphere, personality, or even challenge in a way that an unbiased algorithm can’t. Biases aren’t automatically a bad thing!

In this chapter we’ll test that thesis. We’ll look at two fairly similar algorithms that seem to work, superficially, much like Aldous-Broder or Wilson’s, but that introduce biases by adding constraints to their random walk. These are the ominously named Hunt-and-Kill algorithm and the Recursive Backtracker.