How to Create Mazes Using Minimum Spanning Trees

Procedural maze generation is a fundamental technique in game development used to build dynamic, replayable levels without manual level design. By translating a grid into a mathematical graph, developers leverage minimum spanning tree (MST) algorithms to carve out labyrinthine structures that guarantee full connectivity with zero isolated areas. This article details how developers represent game space as graphs, apply algorithms like Kruskal’s and Prim’s using randomized weights, and modify the resulting spanning trees to suit specific gameplay requirements.

1. Representing the Game Grid as a Graph

To generate a maze using graph theory, developers first abstract the play area into an undirected graph composed of nodes (vertices) and connections (edges):

  • Nodes: Every individual cell or room in the grid represents a node.
  • Edges: The borders or walls separating adjacent cells represent potential pathways (edges).
  • Weights: Developers assign a randomized numerical weight to every edge. Randomizing edge weights ensures that every generated maze features a unique, unpredictable layout rather than a uniform geometric pattern.

2. Choosing and Applying an MST Algorithm

A minimum spanning tree connects every node in a graph using the minimum possible total edge weight, inherently preventing closed loops (cycles). Two primary algorithms are used in game development:

Randomized Kruskal’s Algorithm

Kruskal’s algorithm processes edges globally:

  1. All edges are added to a list and sorted in ascending order according to their randomized weights.
  2. Each cell begins in its own isolated set using a Disjoint Set Union (DSU) data structure.
  3. The algorithm iterates through the sorted edges. If the two cells connected by an edge belong to different sets, the edge is carved into a passage, and the sets are merged.
  4. If the cells are already in the same set, the edge is skipped to prevent creating a loop.
  5. This produces a maze with a uniform, branch-heavy structure where pathways expand evenly across the entire map.

Randomized Prim’s Algorithm

Prim’s algorithm grows a maze locally from a starting point:

  1. A random starting cell is marked as visited, and its neighboring walls are added to an active list.
  2. The algorithm repeatedly selects the lowest-weight wall from the active list that connects to an unvisited cell.
  3. The wall is removed, the adjacent cell is marked as visited, and its neighboring walls are added to the list.
  4. This process repeats until no unvisited cells remain.
  5. Prim’s algorithm tends to produce mazes with shorter dead ends and a more pronounced radial branching pattern outward from the origin point.

3. Translating the Tree into Gameplay Geometry

Once the MST calculation is complete, the resulting mathematical tree is mapped back into the game engine's coordinate system:

  • Retained Edges: Paths where edges were accepted by the algorithm are marked as walkable floor tiles or open corridors.
  • Discarded Edges: Paths where edges were rejected remain as solid, impassable collision geometry (walls).

4. Gameplay Adjustments and Braiding

A pure minimum spanning tree creates a "perfect maze," meaning there is exactly one viable path between any two points and numerous dead ends. While mathematically sound, this can lead to frustrating navigation in action or exploration games.

Developers adjust the layout by "braiding" the maze—intentionally removing a small percentage of the remaining walls to introduce alternative routes and loops. Additionally, developers can manipulate weight distributions (such as artificially lowering weights along a horizontal axis) to create directional bias, longer straightaways, or cavernous open areas to accommodate combat encounters and dynamic camera angles.