The Fake Geek's blog: The amazing maze
Here I use randomized Kruskal's algorithm with a disjoint set data structure to perform union method. It works in the following way:- Create a list of all walls that potentially can be destroyed;
- Randomly choose a wall index;
- Union the two adjacent cells that are separated by the wall;
- Repeat until all cells are in the same set.
The union method acts like knocking down the wall, i.e., if two cells are in the same set, they are connected. When all cells are in the same set, there must be one path from the start cell to the end cell. Moreover, since every time we union two cells that are in different sets, there is no path between the cell before union, and since after the union, no other wall will be knocked down between these two cells, so there will be a unique path from any cell to another cell in the maze. Thus fulfill the "perfect" maze requirement.
Read full article from The Fake Geek's blog: The amazing maze
