How to Generate a Maze You Want to Explore
Maze generation isn’t just about confusing the player. A good maze should spark curiosity, create a sense of forward motion, encourage risk-taking, and invite exploration. Especially when the player can’t just stop and look around — decisions must be made quickly.
How the Maze is Built
At its core, the maze is a 2D grid made up of individual cells, each of which knows whether it has a wall on its top, bottom, left, or right side. This is represented by the MazeCell class, and all cells are managed within a Maze object. A cell also supports custom markers (like "Visited" or algorithm-specific flags), which are used by different algorithms during generation.
public class MazeCell {
public Vector2Int Position;
public bool TopWall, BottomWall, LeftWall, RightWall;
public void SetMarker(string key); // Markers used by the algorithm
}The maze is initialized with all walls intact. During generation, most algorithms progressively remove walls between adjacent cells to carve out paths — forming a connected network. This is done via helper methods like RemoveWall(a, b) and GetNeighbors(cell) to ensure consistency and bidirectional wall removal.
However, some algorithms — like Recursive Division — work in the opposite direction: they start with an empty space and build walls to divide it into sections, carving occasional openings to keep the maze connected. The underlying system supports both approaches.
Step-by-step Generation
Maze generation is deliberately broken down into discrete steps, via the IMazeGeneratorAlgorithm interface:
public interface IMazeGeneratorAlgorithm {
void Initialize(Maze maze, int seed);
bool Step(); // Returns true when the algorithm is finished
}Each call to Step() advances the algorithm by a small amount — typically one modification at a time. This has several key benefits:
- 🌀 Visual Debugging: We can insert artificial delays and visualize how the maze is constructed over time.
- ⏳ Progress Display: A loading indicator or progress bar can show real-time feedback while the maze is building.
- ⚙️ Non-blocking UX: Since generation happens asynchronously (via coroutine), it doesn't freeze the application or UI.
In Unity, this logic is handled in MazeGenerator.cs, which starts generation with a coroutine:
IEnumerator GenerateMazeStepByStep() {
while (!algorithm.Step()) {
// Update cell visuals based on their state
yield return new WaitForSeconds(1f / speed);
}
}Architecture Benefits
This architecture allows full separation of:
- Maze logic (data, state, algorithm),
- View (visual representation via prefab instances),
- Control flow (via coroutine and step-by-step logic).
It's easy to swap in different algorithms (DFS, Prim, Kruskal, etc.) by selecting from the MazeAlgorithm enum, and each algorithm can be implemented independently with just Initialize() and Step().
Visualizing the Result
Each maze algorithm is visualized step-by-step in a 2D top-down view. Thanks to the coroutine-based generation, we can animate the entire process in real time — with delays, color-coded cells, and UI feedback.
This helps both with debugging and level design — and in Running Lantern, that’s exactly where we place the maze’s exit.
Maze Generation Algorithms
Randomized depth-first search
Also known as the recursive backtracker, this is a randomized version of DFS.
Fast, compact, and produces a highly branched structure with one guaranteed path to the exit. DFS mazes tend to have low branching and long corridors, as it explores deeply before backtracking.
How it works
Start at a random cell and mark it as visited.
- While there are unvisited neighbors:
- Choose a random unvisited neighbor.
- Remove the wall between the current cell and the neighbor.
- Recursively move to the neighbor and repeat.
- If there are no unvisited neighbors, backtrack to the previous cell until you find one.
The process continues until all cells have been visited.
Why DFS works well for Running Lantern:
- Plenty of dead ends — good for tense gameplay: players can make mistakes
- Natural difficulty scaling — as maze size increases, paths get longer and riskier
Downsides:
- Visually repetitive — one long “stem” with lots of dead ends
- Few early branches — limited directional choice near the start
- Long dead ends — backtracking can be frustrating with movement constraints
Recursive Division
Recursive Division works by repeatedly dividing space with walls, then opening small passages between the divided sections. It’s fast and very structured, producing predictable layouts unless modified.
How it works
- Start with a large open rectangle (no walls inside).
- Choose to divide either horizontally or vertically, depending on shape.
- Add a wall across the area with a single random opening.
- Recursively apply the same process to each sub-area.
The process continues until the areas are too small to divide further.
Note: This algorithm builds walls instead of removing them — it starts with an empty area and adds structure.
Recursive Division is a good framework, but must be “corrupted” with dead ends, loops, and randomness to feel like a real maze.
Also, it can suffer from bottlenecks. See: Better Recursive Division Algorithm
Prim’s Algorithm
Prim’s algorithm builds a maze by growing a tree — starting from a random cell and expanding outward through a frontier of unvisited neighbors. It’s inspired by graph theory and minimum spanning trees.
How it works
- Start with a random cell and mark it as visited.
- Add all unvisited neighbors of that cell to a frontier list.
- While the frontier is not empty:
- Pick a random cell from the frontier.
- Find its visited neighbors (i.e., already part of the maze).
- Connect it to one randomly chosen visited neighbor by removing the wall between them.
- Mark the cell as visited.
- Add its unvisited neighbors to the frontier.
The algorithm continues until there are no more frontier cells.
The result is a loop-free structure (a spanning tree), with many branches and frequent intersections, but no cycles.
Kruskal’s Algorithm
Kruskal’s algorithm builds a maze using principles from graph theory. It starts by treating each cell as an isolated set and progressively connects them by removing walls — but only if the cells are not already part of the same connected group.
How it works
- Each cell is initialized as its own unique set.
- A list of all possible walls between adjacent cells is created and randomly shuffled.
- Then, wall by wall:
- If the two cells on either side of the wall belong to different sets, the wall is removed and their sets are merged.
- If the cells are already in the same set, the wall is kept to avoid creating loops.
This process continues until all cells are part of a single connected structure.
Like Prim’s and DFS algorithms, Kruskal’s does not create loops. The result is a minimum spanning tree — every cell is connected, but there’s only one unique path between any two points.
Kruskal’s algorithm is useful when you need full randomness without sacrificing connectivity
Sidewinder
The Sidewinder algorithm is a simple and fast maze generation method, inspired by binary tree structures. It processes the maze row by row, carving horizontal corridors and occasionally linking them to the row above.
How it works
- The top row is initialized with all cells connected horizontally (no top walls).
- For each subsequent row:
- Iterate from left to right, maintaining a “run” — a list of adjacent cells in the current row.
- With a 50% chance (or when hitting the eastern boundary), close the run by:
- Picking a random cell from the run.
- Carving a passage upward to the cell above.
- Clearing the run and starting a new one.
- If not closing the run, carve a passage to the right.
This process continues until the bottom row is processed.
The Sidewinder algorithm does not produce loops — each cell connects upward through a single path, and horizontal runs do not circle back.
Pros for Running Lantern:
- Extremely fast — ideal for infinite or streaming levels.
Sidewinder is perfect for generating simple, corridor-heavy levels. It’s a great choice for early game zones, tutorial areas, or endless runner-style modes where speed and consistency matter.
Eller's Algorithm
Eller’s Algorithm generates mazes row by row, maintaining set-based connectivity as it progresses downward. It’s designed for line-by-line generation, making it especially suitable for environments with limited memory — like old arcade machines or vertically scrolling games.
How it works
- Start with the first row: each cell belongs to its own unique set.
- Randomly merge adjacent cells within the current row (remove horizontal walls between different sets).
- For each set, randomly create at least one vertical connection to the row below (remove downward walls).
- In the next row:
- Cells connected from above inherit the same set.
- All others are assigned new, unique sets.
- Repeat until the last row, which is merged completely to ensure full connectivity.
Like Prim and Kruskal, Eller’s algorithm does not create loops in its standard form. All paths are unique unless the implementation is modified.
Pros for Running Lantern:
- Line-by-line generation — works well for streaming mazes or procedural chunks.
- Memory-efficient — only needs to track the current and previous row.
Eller’s Algorithm is a great fit for vertical maze generation or memory-limited environments. In games like Running Lantern, it could power infinite scrolling levels or tightly packed challenge sections with precise control over connectivity.
Aldous-Broder
The Aldous-Broder algorithm generates mazes through a pure random walk. It doesn’t prioritize efficiency — instead, it relies on uniform randomness to ensure that every cell is eventually reached and connected. The result is a truly chaotic and organic-looking maze.
How it works
- Start from a random cell and mark it as visited.
- Repeatedly:
- Move to a randomly chosen neighboring cell.
- If that neighbor hasn’t been visited yet:
- Remove the wall between the current cell and the neighbor.
- Mark the neighbor as visited.
Continue until all cells have been visited.
The algorithm creates lots of loops during generation (the random walk may return to the same cell many times), but only adds a passage when visiting a cell for the first time — so the final maze is still loop-free.
This approach guarantees uniform randomness: every possible spanning tree has an equal chance of being generated.
Pros for Running Lantern:
- Chaotic and organic layout — perfect for mazes meant to feel hand-made.
- Unbiased randomness — mathematically fair generation.
Cons:
- Extremely inefficient — can take a long time to finish, especially in large mazes.
- Hard to control — unpredictable generation makes it less suited for tight level design.
Why Use a Seed
To make maze generation reproducible — for example, in multiplayer or challenge modes — we use a seed-basedapproach. A seed allows the same maze layout to be regenerated consistently, as long as the same algorithm and parameters are used.
In the current implementation, we use System.Random to generate mazes. Unity also provides its own alternative — UnityEngine.Random. Here's how they compare:
| Feature | System.Random |
UnityEngine.Random |
|---|---|---|
| Type | .NET standard PRNG | Unity-specific PRNG |
| Seeding | Via constructor | Via Random.InitState() |
| Usage scope | Per-instance | Global static |
| Thread safety | ❌ Not thread-safe | ❌ Not thread-safe |
| Platform consistency | ⚠️ Not guaranteed | ⚠️ Not guaranteed |
| Determinism | Mostly deterministic | Mostly deterministic |
| Cross-platform | ❌ Not guaranteed | ❌ Not guaranteed |
| Use case | Logic, algorithms | Visual effects, Unity-specific logic |
System.Random nor UnityEngine.Random guarantee identical output across platforms or Unity versions. This means the same seed may produce different mazes on different devices — especially on different architectures (e.g., Windows vs Android).How seeds are used now
Currently, seed values are mostly used for debugging and local reproducibility: to re-run a specific maze layout during development or test a specific scenario repeatedly.
What about future support?
n the future, we may upgrade this system to support true cross-platform reproducibility — for example:
- By switching to a platform-independent PRNG.
- By creating a custom deterministic random wrapper.
This would allow mazes to be reliably shared between players and devices — for example:
- Multiplayer: same layout for all participants.
- Challenges: share a maze with a friend via a seed string.
- Replays & leaderboards: sync gameplay and ghost data.
AI Disclaimer
The maze algorithms were implemented using AI-assisted code generation. While powerful, this approach requires careful review — bugs are possible.
What’s Next?
Next, we’ll explore how to move through the maze. In the next article, we’ll cover how we implemented controls in Unity: swipes, stop mechanics, Input System, and mobile testing.