Mazes for Programmers

Simplified Prim’s Algorithm

Simplified versions of Prim’s algorithm are fairly common among maze generators, and are typically referred to merely as “Prim’s algorithm” by many sources. However, unlike the real algorithm, these simplified versions do not actually bother with different costs and weights for passages. In fact, these algorithms tend to be similar to what you would get if you ran the real Prim’s algorithm on a grid in which every passage had the same cost.

Recall how the algorithm began, after picking a cell at random as the starting point: it looked for the lowest cost passage that connected to that starting cell. But if every passage had the same weight, they’d all tie, and we’d break the tie by choosing among the candidates at ...