Maze Generation & Solving
Maze generation creates a perfect maze (exactly one path between any two cells) by carving walls. Recursive backtracking (DFS) is common: start from a cell, randomly pick an unvisited neighbor, remove the wall, recurse; backtrack when no neighbors remain. Solving uses BFS for unweighted shortest path.
Loading demo…
Algorithm explanation
Generation (recursive backtracking): at current cell, mark visited; shuffle neighbors; for each unvisited neighbor, remove wall between current and neighbor, recurse. Solving: BFS from start, exploring neighbors until goal is reached; parent pointers give the path. A* uses a priority queue and heuristic to focus exploration.
Concepts used
- DFS
- BFS
- A*
- Recursive backtracking
- Graph traversal
Complexity
Time:
O(rows × cols) generation; O(V + E) solvingSpace:
O(rows × cols)Real-world usage
- Game level design
- Pathfinding in games and robotics
- Puzzle generation