Kruskal's Maze Generator is a randomized version of Kruskal’s algorithm: a method for producing a minimal spanning tree for a weighted graph.

Kruskal's is interesting because it doesn't "grow" the Maze like a tree, but rather carves passage segments all over the Maze at random, making it very fun to watch. Still, it results in a perfect Maze in the end.

The counterpart is to require storage proportional to the size of the Maze, along with the ability to enumerate each edge between cells in random order (Using here a set of edges and taking them randomly).

Once we have all of the edges into a big set and a unique subset id associated to each cell; all we need is to pick an edge at random, check if the neighbouring cells belong to a different subset and unify them by setting the same id for all cells of both subsets.

Steps

Kruskal's Original Version Maze Generator Version
  • Give a unique subset id for each existing cell.
  • Throw all of the edges into a big set.
  • While there is edge to be handled in the set:
  • 1. Pull out the edge with the lowest weight.
  • 2. If the edge connects two disjoint subsets:
    a. Connect cells.
    b. Join the subsets.
  • Give a unique subset id for each existing cell.
  • Throw all of the edges into a big set.
  • While there is edge to be handled in the set:
  • 1. Pull out one edge at random.
  • 2. If the edge connects two disjoint subsets:
    a. Connect cells.
    b. Join the subsets.

The randomized algorithm just changes the first loop step, so that instead of pulling out the edge with the lowest weight, you remove an edge from the set at random.

Pseudo-Code

Maze KruskalS(int width, int height)
{
  Maze maze(width, height);

  // Create a set with all connecting edges
  // Create a vector of buckets for each cell with their id.
  Set edges(maze);                  // #edges = (height - 1) * width + (width - 1) * height
  BucketsVector bucketCells(maze);  // #buckets = #cells = height * width

  // While the set of edges is not empty
  while (!edges.empty())
  {
    // Randomly get an edge and remove it from the set
    auto edge = GetRandom(edges);

    // If cells are not already in the same bucket: Connect them and Merge Buckets
    if (BucketId(edge.first) != BucketId(edge.second))
    {
      Connect(edge.first, edge.second);
      MergeBuckets(bucketCells, edge);
    }
  }

  return maze;
} 

Mazes generated tend to have a lot of very short dead-ends, giving the maze a kind of "spiky" look. This algorithm yields Mazes with a low "River" factor, but not as low as Prim's algorithm.