Mazes for Programmers

Better Weaving with Kruskal

So that’s Randomized Kruskal’s algorithm, and you might be wondering now what this has to do with weave mazes. That was, after all, how this chapter began, and I did promise that Kruskal’s would apply. Let me assure you, it definitely does.

Recall how weave mazes were presented in the previous chapter, where the algorithm randomly attempts to move over or under passages as opportunities to do so present themselves. This certainly works, but it’s not very consistent. Sometimes you may get a maze with a dozen crossing passages, and other times you might only get one or two (or none at all!). That’s the nature—and consequence—of random.

However, what we’d like to be able to do is generate mazes with a consistent, predictable ...