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

Prim's algorithm creates a tree by getting the adjacent cells and finding the best one to travel to next. To Generate mazes using Prim's, we will instead take a random cell to travel to the next one.

Although the classical Prim's algorithm keeps a list of edges, here is studied the modified version for our maze generation by maintaining a list of adjacent cells. Running faster, it still requires storage proportional to the size of the Maze.

Prim’s approaches starts from any cell and grows outward from that cell. The algorithm keeps a set of the possible cells the maze could be extended to. At each step, the maze is extended in a random direction, as long as doing so does not reconnect with another part of the maze.

Steps

Prim's Original Version Maze Generator Version
  • Choose a starting cell in the field and add it to the path set.
  • While there is cell to be handled in the set:
  • 1. Pull out the ouside of the maze cell with the lowest edge weight that may be connected.
  • 2. Add all unconnected neighbours to the set
  • Choose a starting cell in the field and add it to the path set.
  • While there is cell to be handled in the set:
  • 1. Randomly connect to one of the already connected neighbor.
  • 2. Add all unconnected neighbours to the set

The randomized algorithm just changes the cell connection, so that instead of pulling out the cell with the lowest weight, you connect a cell at random.

Pseudo-Code

Maze Prims(int width, int height, Cell startCell)
{
  Maze maze(width, height);
  Set pathSet(startCell);

  // While the set of cells is not empty
  while (!pathSet.empty())
  {
    // Select randomly a cell to extend the path and remove it from the set
    // Mark the cell as visited
    auto cell = Cell::Visite(pathSet.GetRandom());

    // Get available neighbours from bottom, left, right, top and visited
    // Randomly connect to one
    auto neighbours = GetVisitedNeighbours(maze, cell);
    if (!neighbours.empty())
    {
      // Randomly connect to an available cell
      auto randIdx = Random() % neighbours.size();
      Connect(cell, neighbours[randIdx]);
    }

    // Add all unvisted neighbours to the set
    pathSet.insert(GetNeighbours(maze, cell));
  }

  return maze;
} 

Mazes generated by Prim’s algorithm share many of the characteristics of those created via Kruskal’s algorithm, such as having an abundance of very short dead-ends, giving the maze a kind of "spiky" look. The algorithm also yields mazes with a very low "River" factor and a rather direct solution.

It will usually be relatively easy to find the way to the starting cell, but hard to find the way anywhere else.