All my life I’ve been fascinated by mazes. There is something mesmerizing about how intricate they can be. In my head they represent some sort of visualization for the order of chaos.
However, what purpose can they serve, other than entertaining people trying to find the way from the start to the end?
Why generate mazes?
Imagine the maze as a set of intersections connected by paths which make the maze’s corridors. Under this light, the maze can be interpreted as an undirected graph, where each intersection is a node, and the corridors are edges.
Taking this new interpretation into account, the maze would represent a spanning tree of the full graph. A spanning tree is a subgraph which creates a tree including all the nodes of the parent graph with the minimum amount of edges1, just like that, the problem becomes way more interesting.
Imagine that each possible corridor has length, and rather than choosing a possible corridor at random, we always pick the shortest one. It would convert the maze into a minimum spanning tree (MST)2 of the parent graph.
However, what is the utility of minimum spanning trees? you ask. Well, some notable examples include taxonomy, and network design (it could be any network like your local telecommunication connections, your city’s water supply or electrical grid)3.
Prim’s Algorithm
There are several algorithms to calculate MSTs one of which is the Prim’s Algorithm.
Created by Vojtěch Jarník later popularized by Robert Prim and Edsger Dijkstra, Prim’s algorithm finds a minimum spanning tree in a weighted undirected graph.
In a very high level, the algorithm chooses an arbitrary node and marks it. Then, from the edges connected to other nodes that are not yet in the tree select the one which weighs less and mark the connected node as part of the tree. Finally, repeat until all nodes are in the tree.
High level maze algorithm
Now coming back to the maze, the original Prim’s algorithm doesn’t work because the edge selection is focused around the weight. Fortunately, the only change we need to make in order to generate a proper maze is to select edges randomly instead of choosing the minimum weighted one.
This variation is often called the Randomized Prim’s algorithm, and in pseudo code it looks like this4:
- Select a node at random and mark it as part of the maze. Add all adjacent edges to a pending list.
- Iterate over the pending edges:
- Pick a random edge from the pending list.
- Every edge connects two nodes, if only one of the two is part of the maze, then mark the edge and node as part of the maze.
- Add all the new neighbouring edges to the pending list.
Implementation
Now for the good stuff, I included a visual implementation of the randomized Prim’s algorithm. You can execute it slow to see how each iteration performs the different decisions or run it fast and in a massive size just to appreciate the beauty of pseudo-randomness and its ordered chaos.
If you decide you like one of its creations you can download the generated maze by clicking on the PNG button below the maze and if you would like to see the details of how this is implemented you can see the full source code, download it and play with it by visiting Visual Implementation of the Randomized Prim’s Algorithm in GitHub.
Select the speed of the animation, the size of the maze, and click start.
Further Reading
Article. Maze generation in general and overview of algorithms.
“Maze generation algorithm”.
Go to article.
Article. Detailed explanation of Prim’s algorithm.
“Prim’s algorithm”.
Go to article.
Video. Prim’s algorithm sequence animated on a formal graph.
“Prim’s Algorithm Animation”.
See the video.
Article. In depth view of minimum spanning trees.
“Minimum spanning tree”.
Go to article.
Footnotes and References
-
Read more formal applications for MST in this two resources from Virginia Tech and University of Texas in Dallas respectively: Lecture in MST Applications, Applications of minimum spanning trees. ↩
-
Paraphrased from Wikipedia’s description of this same algorithm. ↩
