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

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 outside of the maze cell with the lowest edge weight that may be connected.
• 2. Add all unconnected neighbors 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 neighbors to the set

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.