Introducing Prim's Algorithm
Explore how Prim's algorithm generates mazes by expanding from a starting cell and choosing the lowest-cost connections. Learn to implement simplified and true versions of this algorithm to create mazes without cycles, and understand its relation to other maze generation techniques like the Growing Tree algorithm.
We'll cover the following...
Background
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 should be able to find other algorithms that fulfill our needs.
One such algorithm, called Prim’s, adapts readily to random maze generation. We’ll take a look at how this algorithm works, and then we’ll see the two ways it is used to implement our mazes: a simplified version and a “true” version. Lastly, we’ll take a look at a closely related algorithm called the Growing Tree algorithm, which can actually be configured ...