Kruskal Algorithm Maze Generation
The Randomized Kruskal AlgorithmThis algorithm creates a new maze from a grid of cells. To begin, each cell belongs to its own set. Then:
- Choose a random wall (vertical or horizontal) between two cells.
- If the cells on each side of that wall are already in the same set, do nothing.
- If the cells on each side of the wall are not in the same set:
- demolish the wall, and
- merge the sets containing those two cells.
- Continue choosing random walls until all cells are in the same set.
This applet was last updated July 2019.