Quick Access
Description
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.
How To Build
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  



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 unvisted neighbors to the set pathSet.insert(Getneighbors(maze, cell)); } return maze; }
Texture
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 deadends, 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.