Simple Maze Generation using Coldfusion: Kruskal's Algorithm

In my first post on maze generation I looked into creating a maze using the simple Recursive Backtracking algorithm. A lot of credit in my understanding of that algorithm and the framework in which to apply the maze algorithms goes to Jamis Buck and his fantastic series on Maze Generation. Exploring Kruskal's Algorithm for maze generation was no exception.

Kruskal's Algorithm
Kruskal’s algorithm is a way of finding a minimum spanning tree from a weighted graph by connecting all vertex (nodes) using the edges (path between the nodes) with the smallest weight. The algorithm is quite simple:

• Starting with a graph,
  • Create a list of all of the edges that connect the nodes
  • Consider each node to contain a tree (initially rooted by the node)
• Iterate over the list of edges,
  • Choose one with the least weight
  • If the nodes linked by this edge are contained in two different trees, connect their trees and continue.
  • Otherwise, simply continue to the next edge
• Repeat until all edges have been looked at and/or all nodes in the graph are contained by the same (spanning) tree.

Here is an illustration of a weighted graph and what the resulting spanning tree will look like after applying Kruskal’s algorithm:


Kruskal's algorithm used only the necessary edges (smallest weights first) to connect all nodes in the graph.

So how does this apply to maze generation?
If we think of our maze as a graph where all edges have the same 'weight', we can then easily represent it using a two-dimensional array. Look at the following illustration:

You can see how we associate the nodes in the graph to array cells and correlate edges to the walls in our cells. Walls with have both a North and South or East and West direction depending on which cell you are looking at it from, but from the perspective of examining the edge, we only need one direction to represent it (I hope the code will make this a little more clear).

Because we treat the maze as an unweighted graph, the part in Kruskal's algorithm that seeks out the smallest edge gets replaced with by randomized selection. This give all 'edges' a fair chance of being inspected will produce the randomized paths that we seek in the mazes.

Trees first
If you remember in the first step of Kruskal's algorithm, it notes that each vertex(node) should contain a tree. That tree will be used in the algorithm to determining if a path exists between two neighboring cells. Here is an implementation of tree that we will use in our example:
With the tree defined, we can begin constructing the overall algorithm: After running the code, Kruskal's Algorithm will produce a similar looking maze to this one below.



Please feel free to download the source and experiment in local environment. Compared against the non-recursive Backtracking implementation, Kruskal's algorithm runs much slower as it constantly traverses through disjointed and connected tree recursively.

• Posted by Sam on Aug 26, 2011 at 1:15 PM
  
  Kruskal,
  
  Amazingly good. Very well put. Keep it up my friend.
  
  Cheers!
  Sam.
  
  

 

Leave Feedback

Name

Email

Email will not be displayed

Website

( Optional )

Feedback

Post your feedback, HTML will not be rendered, only plain text.

Security

Answer the math problem below.

=

Subscribe

Receive emails when others submit comments