Introducing Kruskal's Algorithm

Background

You might have noticed something odd about the program we wrote to generate the weave mazes. Specifically, when we were experimenting with smaller mazes, we probably saw that sometimes our program didn't generate weave mazes, which it was supposed to do. We set it up, we ran the program, and all that came out was a boring, old, normal maze.

The problem is that the technique we described previously is actually not very reliable. The technique is easy to understand, straightforward to implement, and remarkably intuitive, so it has a lot of pros, but because of how it depends on random chance to determine when to tunnel under a passage, it is possible for a maze to be generated that doesn’t weave at all.

Ideally, if we set out to generate a weave maze, we should be confident of getting one. Even better, we should be able to somehow adjust the frequency of the crossings, making them appear more or less often, and—as long as we’re on the subject—we might as well mention how nice it would be if we could specify exactly where the crossings should be in the maze.

It turns out there’s a random maze algorithm that just happens to be great at fine-tuning these weave mazes. It’s based on Kruskal’s algorithm, and we’re about to explore it. First, we’ll look at how Kruskal’s algorithm itself works and then see how it can be applied to maze generation. After that, we’ll get to see how it can be used to make those weave mazes just about as configurable as we’d like.

Kruskal's algorithm explained and illustrated

Kruskal’s algorithm was developed by the mathematician and computer scientist Joseph Kruskal in 1956 to construct what are called minimum spanning trees. Spanning tree is just a fancy name for these perfect mazes we’ve been generating, and minimum simply refers to the costs and weights we discussed previously.

Basically, Kruskal was trying to solve the following problem.