Maze Generation Using Randomized Kruskal's Algorithm25 May 2015
I previously posted a maze generator using depth-first search and backtracking. This implementation however uses a randomized version of Kruskal's Algorithm (Minimum Spanning Tree Algorithm).
The Wikipedia description of the algorithm does a far better job summarising it than I ever could:
For my implementation I stored a list of the edges (walls) between each cell and DisjointSets data structure to keep track of which cells are traversable. Simply, DisjointSets keeps track of a fixed number of disjoint sets (sets that do not overlap). Here initially each cell is a disjoint set. The sets can be unioned together as they need to be merged, i.e when a wall is destroyed between two sets of cells. As described above, I select random edges from my list to remove provided removing that edge will join two disjoint parts of the maze together until my DisjointSets contains a single set containing every cell. I assume the start and end points to be in the top-left and bottom-right positions of the maze respectively, but this is arbitrary as any cell can be reached from any other cell via some route. Below is the source code for my algorithm and DisjointSets data structure. Either generate() or animate() can be called depending on whether you want the drawing delay as the algorithm runs.