Kruskal's Algorithm Maze Generator

Kruskal's algorithm is a minimum spanning tree algorithm that can be adapted for maze generation. It is particularly effective for creating perfect mazes. An alternative to Kruskal's algorithm is Prim's algorithm, which is also a minimum spanning tree algorithm, but since they generate identical mazes and Kruskal's runs faster, I have not bothered implementing Prim's.

A perfect maze is a maze in which there is exactly one path from any point in the maze to any other point. That means you can't end up going around in circles, but you will often encounter dead ends, forcing you to turn around and go back.

The maze maps generated here includes a default version without any start and finish positions, so you can decide those for yourself: there will be a solution from any point in the maze to any other point. If you want inspiration, you can enable a suggested start and finish position - and even see the solution between the two.

About Kruskal's Algorithm

Kruskal's algorithm was created by Joseph Bernard Kruskal, Jr., an American mathematician, statistician, and computer scientist. He first described the algorithm in 1956 in his paper "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem."

The algorithm is designed to find the minimum spanning tree (MST) of a graph, ensuring that all vertices are connected with the minimal possible total edge weight while avoiding cycles.

How Kruskal’s Algorithm Works for Maze Generation

Step 1: Initialize

• Treat each cell in the maze as a separate set (a unique component).
• List all the walls between adjacent cells as potential edges.

Step 2: Sort Walls

• Shuffle or randomly order the walls. If implementing it as a true Kruskal’s algorithm, sort walls in a random order (since maze generation does not require weights).

Step 3: Process Walls

• Iterate through the shuffled walls.
• If the two cells divided by the wall belong to different sets (i.e., they are not yet connected in the maze), remove the wall and merge the sets.
• If they are already in the same set, skip the wall (to avoid cycles).

Step 4: Continue Until Completion

• Repeat this process until all cells are connected, forming a single spanning tree.
• At the end, every cell is connected to the others without loops or isolated sections.

Since Kruskal’s algorithm relies on merging sets, it can be optimized by using the Union-Find algorithm, which provides an efficient way to track connected cells during maze generation. You can see my PHP implementation of the Union-Find algorithm here: Disjoint Set (Union-Find Algorithm) in PHP