martinopiaggi / unity-maze-generation-using-disjoint-sets

Random maze generation in Unity 3d using disjoint sets

Unity-Maze-generation-using-disjoint-sets

Maze generator using disjoin-sets in Unity 3D. There are no cycles and the random maze is solvable by a unique path. I have implemented a Depth First Search to show the path for visualization purposes.

Maze generation visualization

The generation is very quick (50k cells in less than 100 ms) but It's also possible to view the generation at human speed:

I inserted a delay before the start and a delay at each iteration, so that it's possible to play and see the maze growing visually.

So simple, but so elegant.

Disjoint-sets are super simple. In this project, they are implemented using two classical optimizations:

• Optimization with Path Compression
• Optimization with Union by Rank

public class DisjointSet 
{
    private int[] _set;
    private int[] _rank;

    public DisjointSet(int size)
    {
        _set = new int[size];
        _rank = new int[size];
    }
    
    public void MakeSet(int x)
    {
        _set[x] = x;
        _rank[x] = 0;
    }
    
    public int FindSet(int x)
    {
        if (x != _set[x]) return FindSet(_set[x]);
        return x;
    }

    public void UnionSet(int x, int y)
    {
        var parentX = FindSet(x);
        var parentY = FindSet(y);
        if (_rank[x] > _rank[y]) _set[parentY] = parentX;
        else
        {
            _set[parentX] = parentY;
            if (_rank[x] == _rank[y]) _rank[y]++;
        }
    }
}

References

Disjoint Sets on Wikipedia

Algorithm to generate the maze