Prim's Algorithm maze algorithm
Randomized Prim's algorithm grows a maze outward from one cell by repeatedly connecting a random cell on its frontier.
How it works
It keeps a frontier: the unvisited cells next to the maze grown so far. Each step picks one frontier cell at random, connects it to a random neighbour that's already in the maze, and adds that cell's own unvisited neighbours to the frontier. It stops when the frontier is empty.
Since any frontier cell can be picked, the maze grows in every direction at once, like a crystal. The result has lots of short branches and dead ends and few long corridors, which makes it look busy but is usually easier to solve than a backtracker maze.
What to watch for
Watch the carved area spread outward from the corner in a ragged blob, filling in everywhere at once rather than following one path.
Properties
- Texture
- Short, branchy, many dead ends
- Dead ends
- Many
- Uniform
- No
- Speed
- Fast
- Memory
- The frontier list
Try it
Open the studio to carve your own Prim's Algorithm maze at any size, solve it with up to four algorithms, and save the video. Or print one.
FAQ
Is this the same Prim's algorithm used for minimum spanning trees?
It is the same idea with random choices in place of edge weights. A maze is a spanning tree of the grid.
Are Prim's mazes easy?
Usually easier than backtracker mazes: the many short dead ends are quick to rule out.