Copied to Clipboard
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.
3.Result
The maze is generated dynamically at runtime, creating a completely different layout every time the game starts.
This system successfully produced randomized yet fully connected maze structures without isolated sections.
Play gif
Demo Video
YouTube Demo
GitHub Repository
GitHub - Maze Runner