Exposition

This is an interactive demonstration of maze generation using a really cool application of Kruskal's algorithm. The minimum spanning tree algorithm is used creatively in the task of random maze generation.

Kruskal's algorithm is used to compute a minimum spanning tree from a weighted graph. The input is a weighted graph meaning the edges have weights. The output is a set of edges that connects all the vertices and is the minimal such set.

Kruskal's algorithm:

  1. Maintain a collection of components. Initially, each vertex is its own component.
  2. Iterate edges in order of increasing weight.
  3. If the current edge connects 2 different components then add it to the set of edges to be returned and merge the 2 components, otherwise ignore the edge.

The algorithm I implemented is a randomized version of Kruskal's, so instead of selecting the edge with the lowest weight, you assign random weights to edges. These weights are visualized through colors where red is the lightest and it is a spectrum going all the way up to the heaviest which is blue. Applying Kruskal's, the result is a convincing maze!

Inspirational material

Maze Generation Using Kruskal's Algorithm

Technical Development

The starting step in the development of this site was the visualization of the initial grid. In order to do that I created a div in the html for the grid and gave it the display value "grid" in css. In JavaScript:

  • I assigned each square an id corresponding to its row and column.
  • I also created a list of edges where each edge is a list of the ids of the 2 squares it connects.
    • The algorithm requires that you keep track of components and be able to merge components. At the start, I tried using two lists. One list to keep track of the leader of each vertex. The other is to keep track of the followers of each vertex. However, using lists was complicated and maps were the better option.
  • So I created a leaders map where the key is a vertex and the value is its leader.
  • I created a followers map where the key is a vertex and the value is a list of its followers.
  • So to check if the 2 components are different I would compare the leaders.
  • To merge 2 components I would check which leader of the 2 vertices connected by the edge I'm considering has more followers.
  • I would select the one with fewer followers, add it and its followers to the followers of the other leader, and change its leader and its followers' leader to be the other leader.
The algorithmic challenge was maintaining the components. Initially, I tried updating the leaders map first then the followers map but that resulted in the duplication of followers and the algorithm crashing. Being able to update both the leaders and followers in order to create one connected component was a challenge.