Mazes for Programmers

Chapter 4Avoiding Bias with Random Walks

So far, we’ve looked at two different maze algorithms, and while both were straightforward to understand and implement, they also had some pretty significant biases. They could be worked around, sure, but maybe there’s a better way. In this chapter we’re going to try to balance the scales a bit by exploring two new algorithms, Aldous-Broder and Wilson’s, both of which are guaranteed to be absolutely unbiased.

If that sounds too good to be true, that’s because it almost is! Nothing comes without a price, so we’ll also see where these two algorithms—despite their mathematical flawlessness—ultimately end up with their own set of disappointments.

To get there, though, we need to have a better understanding ...