75x50 Maze generated by a Prim's algorithm with Top-Left root.

Flooding starting from root (Top-Left corner)

The tree representing its data structure topology from root (Top-Left corner).

75x50 Maze generated by a Prim's algorithm with Middle root.

Flooding starting from root (Middle)

The tree representing its data structure topology from root (Middle).

Prim's Maze Generator is a randomized version of Prim's algorithm: a method for producing a minimal spanning tree from an 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 approach 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

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

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 neighbors from bottom, left, right, top and visited
    // Randomly connect to one
    auto neighbors = GetVisitedneighbors(maze, cell);
    if (!neighbors.empty())
    {
      // Randomly connect to an available cell
      auto randIdx = Random() % neighbors.size();
      Connect(cell, neighbors[randIdx]);
    }

    // Add all unvisited neighbors to the set
    pathSet.insert(Getneighbors(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.

1. Start from any cell within the maze.

2. Add all unvisited neighbors to the set (no connected neighbor).

3. Randomly get one of the cell and connect it to one of the already connected neighbor.

4. Add all its unvisited neighbors to the set.

5. Randomly get one of the cell and connect it to one of the already connected neighbor.

6. After few more iterations.

7. All cell are processed (pathSet is empty): Maze is done!