Perfect mazes on the same 40×28 cell lattice as the pathfinding lab: recursive backtracker, Wilson, Eller, or randomized Prim; then solve with Manhattan A* (4-neighbors). Paint walls or erase passages and move S/G.
About this model
This page generates uniform random spanning-tree mazes on the same 40×28 cell lattice as engineering/astar-dijkstra-grid. Carving happens on the odd–odd room grid (13×19 rooms) with passages through the intervening wall cells, so every maze is a perfect maze (every room reachable, no cycles) before you edit walls. You can pick recursive backtracker (depth-first carving with a stack), Wilson (loop-erased random walks until the maze connects), Eller (row-wise set merging with random vertical links), or randomized Prim (grow the tree from a frontier of crossing edges). After generation, Manhattan A* with 4-neighbors and unit edge costs replays exactly the same search model as the pathfinding lab (walls block, no weighted terrain here). You may paint extra walls, erase passages, or move S and G; endpoints are forced passable when relocated. The visualization mirrors the A* page: green open, cyan closed, yellow shortest path once the replay finishes.
Who it's for: CS and discrete-math learners comparing maze construction algorithms and reconnecting them to grid shortest-path search; pairs naturally with the interactive A* lab.
Key terms
Perfect maze
Spanning tree
Recursive backtracker
Wilson algorithm
Eller algorithm
Randomized Prim
A* search
Manhattan heuristic
How it works
Perfect mazes on the same 40×28 cell grid as the A* lab: recursive backtracker, Wilson, Eller, or randomized Prim. Solve with Manhattan A* (4-neighbors); paint extra walls or erase passages, then move S/G.
Frequently asked questions
Why do Wilson mazes look different from Eller mazes?
They randomize different local choices on the same underlying grid graph (Wilson’s loop-erased walks vs Eller’s row-wise set merges and vertical picks), so the texture of corridors differs even when every maze is a single spanning tree before you edit walls.
Is the A* here exactly the same as on the A* / Dijkstra page?
Same 4-neighbor moves, Manhattan admissible heuristic, and unit costs on free cells. This maze page omits diagonals, weighted cells, and Dijkstra/greedy modes to keep the focus on maze generation plus one canonical solver.
Can I break the “perfect maze” property?
Yes—erase creates a second route between regions (a cycle), and extra walls can disconnect regions. A* then reflects the edited topology; unreachable goals show no path.