Kruskal's Maze Generation Algorithm

This is an animation of a maze being generated using a modified version of Kruskal's algorithm. The maze was generated using my maze generator, Labyrinth, and the animation was generated using Manim, an animation library geared toward mathematics.

Kruskal's algorithm finds minimum spanning trees of weighted graphs. This is useful because it turns out that generating a maze is equivalent to finding a spanning tree of a graph of its cells. The graph representing our maze is unweighted, however, so the algorithm has been modified to select edges at random rather than by lowest weight. Otherwise, it is faithful to Kruskal's original algorithm.

We will use sets to keep track of which parts of the maze are connected to each other. If two neighboring cells belong to disjoint parts of the maze (i.e., the two cells belong to different sets), we know that we can safely create a path between the cells and merge their corresponding sets. We only want to merge disjoint parts of the maze because we don't want any loops in the finished maze, and joining two parts of the maze that are already connected elsewhere would create a loop. Once you understand how this clever use of sets guarantees the properties that we want, understanding the rest of the algorithm is easy.

The algorithm starts by adding each cell of the graph to its own set. It then randomly picks an edge between two neighboring cells in the graph. If the two cells belong to different sets, it will remove the wall between the cells and merge their sets; otherwise, it will discard the edge from the final maze. The algorithm iterates in this way over all edges of the graph (in random order), and at the end, a maze pops out! Unlike the depth-first search algorithm, which produces mazes with long, winding corridors, Kruskal's algorithm tends to yield mazes with a lot of dead ends and short cul-de-sacs.

The colors used in the animation are as follows:
- Gray cells have not yet been visited.
- Blue cells have been visited and are part of the completed maze.
- Orange cells highlight the edge (path) currently being added to the maze.

Many thanks to Grant Sanderson, the original creator of Manim, for making his excellent animation framework freely available for people like me to use. Grant's outstanding YouTube channel, 3Blue1Brown, has also helped inspire me to create a maze generator and specifically to focus on the visualization of various maze generation algorithms. Thanks also to the Manim community for their excellent documentation and work on the community edition of Manim, which is what I used for this animation.