Maze Generation: How Computers Build Labyrinths
Watch algorithms carve paths through grids
Watch algorithms carve paths through grids
A maze is a grid of cells connected by passages. Each cell can have walls on its four sides. Click cells to toggle walls and see how mazes are structured!
Mazes are built on a grid. Each cell is either a wall or a passage. The challenge is creating paths without dead ends (except intentional ones!).
A "perfect" maze has exactly one path between any two points. No loops, no isolated areas - every cell is reachable!
The most popular maze algorithm! It explores as deep as possible, then backtracks when it hits a dead end. Watch the purple cell carve paths through the grid.
1. Pick a starting cell
2. Choose a random unvisited neighbor
3. Remove the wall between them
4. Repeat until no unvisited neighbors
5. Backtrack to find new paths
Creates long, winding corridors with few branches. High "river" factor - paths flow like rivers. Great for adventure games!
Instead of going deep, Prim's grows outward from a frontier. Watch the orange frontier cells expand like a growing organism!
1. Start with one cell in the maze
2. Add its neighbors to the frontier
3. Pick a random frontier cell
4. Connect it to the maze
5. Add its neighbors to frontier
6. Repeat!
Creates more "organic" looking mazes with shorter corridors. The maze grows outward evenly. Often used for cave generation in games!
The simplest maze algorithm! For each cell, just carve a passage either up OR left. That's it! But notice the diagonal bias...
For each cell, flip a coin:
- Heads: carve north
- Tails: carve west
(Handle edges appropriately)
That's the entire algorithm!
Notice the diagonal corridors? Binary Tree always has a bias toward one corner. The top row and left column are always open corridors!
Watch separate regions merge into one! Each color is an isolated region. When walls are removed, regions combine until the whole maze is connected.
1. Each cell starts as its own region
2. Shuffle all walls randomly
3. For each wall, if it separates two regions, remove it
4. Regions merge together
5. Stop when only one region remains
Uses a "disjoint set" to track which cells belong to which region. Merging regions is nearly instant with this clever data structure!
The opposite approach! Start with an open room and add walls to divide it. Each wall has exactly one passage. Divide and conquer!
1. Start with an open room
2. Draw a wall across the room
3. Add one passage in the wall
4. Recursively divide each side
5. Stop when regions are too small
Creates long straight walls and rectangular rooms. Often looks more "architectural". Great for dungeon-style games!
Works row by row! For each cell, either extend the current "run" or close it by carving up. Watch the runs form and close.
For each row (except the first):
1. Start a "run" of cells
2. Either extend the run east
3. Or close it by carving north from a random run cell
4. First row is always open
Like Binary Tree, has a bias (northern corridor). But produces more varied paths. Can generate mazes row-by-row for infinite scrolling games!
Watch all six algorithms race to generate a maze! Which one finishes first? Spoiler: speed depends on maze size and implementation.
You've explored how computers generate mazes using different algorithms. Each approach creates unique patterns and challenges!
Mazes start as a grid of cells with walls between them.
Goes deep, hits a wall, backs up - creates long winding paths.
Grows outward from a point - creates more organic-looking mazes.
Each algorithm has its own "signature" look and feel.
One line of logic creates a complete maze with a diagonal bias.
The opposite approach - start open, add walls!
Put your new knowledge into practice!