How to dynamically generate a maze using Prim's algorithm

#unity3d #algorithms

1. Overview

Prim’s Algorithm is traditionally used to construct a Minimum Spanning Tree (MST) in graph theory.
While thinking about how to generate mazes automatically, I came up with the idea of adapting Prim’s Algorithm into a procedural maze generation system by treating grid cells as graph nodes and walls as edges.
Instead of relying on edge weights, the system randomly expands paths through unvisited neighboring cells while still maintaining overall connectivity.
This approach allows the maze to generate a unique layout every time the game starts while preventing isolated sections or unreachable paths.

2. Development Process

core code

// Generate maze using Prim's Algorithm
protected void Prim()
{
    // Open entrance and exit
    OpenEntranceAndExit();

    // Mark entrance as visited
    Cell startCell = gridGenerator.Cells[inCol, inRow];
    startCell.Visit();

    // List of frontier walls
    List<(int fr, int fc, int tr, int tc)> frontier = new();
    frontier.AddRange(GetCandidateWalls(inRow, inCol));

    // Generate maze
    while (frontier.Count > 0)
    {
        // Select a random wall
        int index = Random.Range(0, frontier.Count);
        var edge = frontier[index];
        frontier.RemoveAt(index);

        Cell fromCell = gridGenerator.Cells[edge.fr, edge.fc];
        Cell toCell = gridGenerator.Cells[edge.tr, edge.tc];

        if (toCell.visited) continue;

        // Remove wall between cells
        RemoveWallBetween(fromCell, toCell);

        // Mark cell as visited
        toCell.Visit();

        // Add candidate walls from the newly visited cell
        frontier.AddRange(GetCandidateWalls(toCell.r, toCell.c));
    }
}

The maze generation system was implemented in Unity using a grid-based structure.
Each cell was treated as a node, and neighboring cells were connected by removing walls during the generation process.
To preserve the core structure of Prim’s Algorithm while making the maze feel less predictable, I modified the expansion logic to randomly select neighboring paths instead of using weighted edges.
The generation process continues until every reachable cell becomes connected, ensuring that the maze always remains fully traversable.
This project became a meaningful experience in creatively applying graph algorithms to actual gameplay systems and procedural generation.