Better Weaving with Kruskal

Generating consistent mazes

We've seen randomized Kruskal’s algorithm, and now you might be wondering what this has to do with weave mazes. Recall how weave mazes were presented earlier, where the algorithm randomly attempts to move over or under passages. This certainly works, but it’s not very consistent. Sometimes, we may get a maze with a dozen crossing passages, and other times, we 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 number of crossings. Different applications have different needs, so it would be nice to be able to reduce the weave density for a lightly woven maze or increase it all the way to eleven to pack the crossings in as tightly as possible.

So, what can we do?