Mazes for Programmers

Chapter 11Growing With Prim’s

The whole “minimum spanning tree” problem turns out to have lots of applications, like finding optimal ways to build out telephone lines, or the best way to structure a computer network. Kruskal’s algorithm was one way to solve it, but it’s not the only way, which means that we ought to be able to find yet other algorithms that we can bend to our will.

(Mwa-hahahaha!)

Sure enough, there is another algorithm, called Prim’s, and sure enough, it adapts readily to random maze generation. We’ll take a look at how this algorithm works, and then we’ll see two ways that it is commonly implemented for mazes: a simplified version, and a “true” version. Lastly, we’ll take a look at a closely related algorithm, called the ...