Maze Generator & Solver

Maze generators create random, solvable mazes using various algorithms, each producing mazes with distinctive visual characteristics and solving difficulty. This is both a tool and a puzzle — the player can generate fresh mazes of any size and attempt to solve them, or watch the generation and solving algorithms work in real time. Understanding different generation algorithms adds an educational dimension, as each method produces mazes with unique properties: long corridors, many dead ends, high branching, or river-like patterns.

Rules

1. Select a maze size (width and height) and a generation algorithm.
2. Generate the maze. The result is always a perfect maze: exactly one path between any two cells, no loops, and no unreachable areas.
3. Solve the maze by finding the path from the start (typically top-left) to the end (typically bottom-right).
4. Optionally, watch the generation or solving algorithm animate step by step.
5. Compare different algorithms to see how they affect maze difficulty and appearance.

Generation Algorithms

• Recursive Backtracker (DFS): Starts from a random cell, carves a path to a random unvisited neighbor, and backtracks when stuck. Produces long, winding corridors with relatively few branches. Creates mazes that feel organic and are moderately difficult to solve.
• Prim's Algorithm: Maintains a frontier of wall candidates and randomly selects walls to remove, growing the maze outward like a tree. Produces mazes with shorter dead ends and more branching, creating a bushier appearance.
• Kruskal's Algorithm: Randomly removes walls between cells in different connected components until the entire grid is connected. Produces very uniform mazes with no apparent bias or pattern.
• Recursive Division: Starts with an empty grid and recursively adds walls with single-cell passages. Produces mazes with long straight walls and a distinctive cross-hatched appearance. Tends to be easier to solve.
• Aldous-Broder Algorithm: A random walk that carves passages to unvisited cells. Produces perfectly uniform mazes (every possible maze is equally likely) but is very slow for large grids.
• Wilson's Algorithm: Uses loop-erased random walks to produce uniform spanning tree mazes. Mathematically elegant and produces unbiased results, though with variable generation time.
• Eller's Algorithm: Generates the maze one row at a time using set tracking. Memory-efficient and can generate infinitely long mazes, as it only needs to store the current row.
• Binary Tree: Each cell connects to either its north or east neighbor (chosen randomly). Extremely fast and simple but produces a noticeable diagonal bias. Every maze has clear corridors along two edges.

Solving Algorithms

• Wall Follower: Follow the left or right wall. Works for all simply connected mazes. Simple but not optimal.
• Breadth-First Search (BFS): Explores all cells at distance N before moving to distance N+1. Guarantees the shortest path.
• Depth-First Search (DFS): Explores as deep as possible before backtracking. Finds a path (not necessarily shortest) quickly.
• A* Search: Uses a heuristic (typically Manhattan distance to the goal) to prioritize exploration toward the exit. Finds the shortest path while exploring fewer cells than BFS.
• Dead-End Filling: Identifies all dead ends and fills them backward to the nearest junction. The remaining unfilled path is the solution.
• Tremaux's Algorithm: A systematic method for solving any maze by marking passages. Can be performed by a human walking through a physical maze.

The mathematical study of mazes dates back centuries, but the algorithmic generation of mazes began with the advent of computers. One of the earliest known maze generation algorithms appeared in the 1970s, when hobbyist programmers on early microcomputers like the Commodore PET and Apple II wrote simple programs to display random mazes on screen. The "Binary Tree" algorithm was among the first used due to its extreme simplicity — it can be implemented in just a few lines of BASIC.

The formal study of maze generation algorithms connects deeply to graph theory. A perfect maze (one with exactly one path between any two cells) is mathematically equivalent to a spanning tree of the grid graph. The various maze generation algorithms are, in fact, different methods for computing random spanning trees. This connection was formalized in the 1990s, when researchers proved that Wilson's algorithm and the Aldous-Broder algorithm produce uniform spanning trees — meaning every possible maze is equally likely to be generated.

Maze generation became a staple of programming education and recreational computing. Books like "Mazes for Programmers" by Jamis Buck (2015) systematically explore dozens of maze algorithms with implementations, and the topic is a common exercise in computer science courses for teaching graph algorithms, recursion, and data structures. The visual appeal of watching algorithms generate mazes step by step makes them popular in algorithm visualization tools and programming tutorials.

In the gaming world, procedural maze generation is fundamental to the roguelike genre, where each playthrough features a randomly generated dungeon. Games like "Rogue" (1980), "NetHack" (1987), and modern titles like "Hades" (2020) and "Dead Cells" (2018) use variants of maze generation algorithms to create replayable level layouts. The field continues to evolve, with researchers exploring 3D maze generation, non-rectangular grids (hexagonal, triangular, circular), and generation algorithms that produce mazes with specific difficulty characteristics.