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.
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.
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]++;
}
}
}