December 9th, 2012Generating Mazes with Kruskal's Algorithm
Kruskal's algorithm is an efficient way to find a minimum spanning tree of a connected, undirected and weighted graph. It has a runtime of O(|E| log |E|), where E are the edges of the graph.
This makes the algorithm quite handy to generate mazes (without cycles) out of regular graphs. In this example, I generate a graph of the layout you see on the right, with many diagonal edges. Every edge then gets a random weight and Kruskal's algorithm is performed. The resulting spanning tree looks very random and nice.
By changing the structure of the base graph, one can define the general outcome of the algorithm. If you, for example, just feed Kruskal a regular grid, a "normal" labyrinth will be created.
Move the mouse to change the destination of the path. Click once to change the starting point. Doubleclick to generate a completely new graph.
The pathfinding is done using Dijkstra's algorithm. Note that none of the algorithms used in this demo are implemented perfectly, there's much room for improvement using better data structures.