Kruskal Algorithm Maze Generation

The Randomized Kruskal Algorithm

This algorithm creates a new maze from a grid of cells. To begin, each cell belongs to its own set. Then:

1. Choose a random wall (vertical or horizontal) between two cells.
1. If the cells on each side of that wall are already in the same set, do nothing.
2. If the cells on each side of the wall are not in the same set:
1. demolish the wall, and
2. merge the sets containing those two cells.
2. Continue choosing random walls until all cells are in the same set.

This algorithm tends to produce mazes with many short paths, which are therefore easier to solve than mazes generated with other techniques. The mazes are fully connected, meaning you can travel from any cell to any other cell.

About the Applet

This applet was created using JavaScript and the P5 library. No other libraries/dependencies are required. If you are having trouble viewing the applet, be sure JavaScript is enabled in your browser. Click here for instructions. Internet Explorer is not recommended for this applet.

This applet was last updated July 2019.