Unity Maze Generation Using Disjoint Sets

This project showcases an efficient maze generator implemented in Unity 3D, utilizing the disjoint-set data structure (GitHub ).

The generator creates random, solvable mazes with a unique path and no cycles, based on a randomized version of Kruskal’s algorithm. As a demonstration of the maze’s solvability, I’ve implemented a Depth First Search algorithm for visualization.

Key Features

• Fast generation (50,000 cells in under 100ms)
• Guaranteed solvable mazes with a unique path
• Visualization options for step-by-step generation
• Depth First Search for path finding visualization
• Based on randomized Kruskal’s algorithm for maze generation

Technical Implementation

The core of this project lies in the elegant simplicity of disjoint sets and the randomized Kruskal’s algorithm. Here’s an overview of the maze generation process:

1. Initialize the grid:
   • Create a list of all walls in the grid.
   • Create a disjoint set for each cell, each containing just that one cell.
2. Randomize the wall list.
3. For each wall, in the randomized order:
   • Check if the cells divided by this wall belong to distinct sets using the Find operation.
   • If they are in distinct sets:
     • Remove the current wall (creating a passage).
     • Join the sets of the formerly divided cells using the Union operation.
4. The resulting structure is a perfect maze with no loops and a unique path between any two cells.

The implementation includes two classical optimizations for the disjoint-set data structure:

1. Path Compression
2. Union by Rank

Here’s a glimpse of the DisjointSet class:

public class DisjointSet 
{
    private int[] _parent;
    private int[] _rank;
    
    public DisjointSet(int size)
    {
        _parent = new int[size];
        _rank = new int[size];
        for (int i = 0; i < size; i++)
        {
            _parent[i] = i;
            _rank[i] = 0;
        }
    }
    
    public int Find(int x)
    {
        if (_parent[x] != x)
            _parent[x] = Find(_parent[x]);
        return _parent[x];
    }
    
    public void Union(int x, int y)
    {
        int xRoot = Find(x);
        int yRoot = Find(y);
        if (xRoot == yRoot)
            return;
        
        if (_rank[xRoot] < _rank[yRoot])
            _parent[xRoot] = yRoot;
        else if (_rank[xRoot] > _rank[yRoot])
            _parent[yRoot] = xRoot;
        else
        {
            _parent[yRoot] = xRoot;
            _rank[xRoot]++;
        }
    }
}

This implementation allows for near-constant amortized time complexity for both Find and Union operations.

The maze generation process can be slowed down for visual appreciation, feel free to explore the full source code on GitHub and experiment with your own modifications!