Maze — Prim

O(rows·cols)

Randomized Prim's algorithm builds a maze the way Prim builds a spanning tree, but with random choices. It starts from one carved room and keeps a "frontier" — the set of rooms two cells away from the maze. Each step picks a random frontier room, knocks out the wall connecting it to its in-maze neighbour, carves it in, and adds its own new frontier rooms. Because growth radiates out from wherever the frontier is, the result tends to have many short branches and a more uniform texture than the long winding corridors of the recursive backtracker. It's still a perfect maze — one unique path between any two cells.

Click a cell to toggle a wall
Grid
Edit the input and press Play

How it works

  1. Carve a starting room and add its neighbours to the frontier.
  2. Pick a random frontier room and knock out the wall to its maze neighbour.
  3. Carve that room and add its own unvisited neighbours to the frontier.
  4. Repeat until the frontier is empty — every room is in the maze.

Pseudocode

1primMaze(grid):                      # O(rows·cols)2  carve one start room; add its walls to a frontier3  while frontier not empty:4    pick a random frontier room5    knock out the wall to its maze neighbour6    carve the room; add its new frontier rooms7  # frontier-driven growth → branchy perfect maze