Mazes for Programmers

Kruskal’s (Randomized)

In a nutshell:

Begin by assigning each cell to a different set. Randomly link two adjacent cells, but only if they belong to different sets. Merge the sets of the two cells. Repeat until only a single set remains.

Typical features:

Largely unbiased (see Appendix 2, ​Comparison of Maze Algorithms​, and note how similar Kruskal’s mazes are to those produced by Aldous-Broder and Wilson’s). Produces very regular, uniform mazes. Excels at producing mazes that are the union of disjoint subsets, where the grid is prepopulated with some cells already connected in different areas.

Variations:

Template mazes (by applying template designs ...