Maze Solver —
Draw a maze. Watch it solve itself.

Pathfinding guide

How BFS and A* find the shortest path through a maze

Maze-solving is one of the oldest problems in computer science, and two algorithms dominate: Breadth-First Search (BFS) and A* (A-Star). Both explore a graph of nodes (grid cells) and edges (passable connections), but they make very different decisions about which cell to explore next; those decisions have dramatic effects on efficiency.

Breadth-First Search (BFS)

BFS explores all cells at distance d from the start before exploring any cell at distance d+1. It uses a queue (first-in, first-out) to maintain the frontier:

Because BFS expands outward layer by layer, the first time it reaches the end is guaranteed to be via the shortest path — measured in number of steps. On an unweighted grid (all moves cost 1), BFS is optimal. The trade-off: it may explore many irrelevant cells in the wrong direction before finding the goal. The purple "explored" cells in the animation show this flood-fill behaviour.

A* (A-Star)

A* adds a heuristic, a smart estimate of how far the current cell is from the goal. Instead of a plain queue, A* uses apriority queue ordered by f(n) = g(n) + h(n), where:

This solver uses the Manhattan distance as the heuristic: h = |row_n − row_end| + |col_n − col_end|. On a grid where only 4-directional movement is allowed, Manhattan distance never overestimates the true cost, so A* is admissible; it still finds the optimal path, but explores far fewer cells than BFS by steering towards the goal.

BFS vs A*: which is better?

In a dense maze with many walls (like the ones generated by the Recursive Backtracking algorithm here), BFS and A* explore similar numbers of cells because there are few choices; the corridors constrain the path. A*'s advantage shines in open grids with scattered obstacles, where it can ignore most of the space and bee-line toward the goal.

How the random maze generator works

The "Generate Maze" button uses Recursive Backtracking (iterative DFS), the same algorithm used to generate puzzles in most maze video games:

This creates a perfect maze: exactly one path between any two cells, no loops, no isolated sections. Every cell is reachable from the start. BFS and A* are guaranteed to find the (unique) path.

How video games use pathfinding

Every enemy NPC that chases the player, from a Pac-Man ghost to a Halo Marine, runs some form of pathfinding. The techniques used in production games are more sophisticated than grid BFS, but the core ideas are the same:

• Navigation meshes (navmeshes): Instead of a grid, the walkable floor is carved into convex polygons. A* runs on the polygon graph, producing smooth paths through 3-D space at a tiny fraction of the cost of a fine grid.
• Hierarchical pathfinding (HPA*): The world is divided into clusters. A high-level path across clusters is found first, then local paths fill in the details. Used in real-time strategy games (Starcraft, Age of Empires) with thousands of simultaneous units.
• Jump Point Search (JPS): An optimisation of A* on uniform-cost grids that skips large swaths of symmetric paths, running up to 10× faster on open terrains.
• D* Lite: A dynamic replanning algorithm; it handles moving obstacles and unknown terrain without recomputing from scratch every frame. Used in robotics and Mars rover navigation.

Real-world applications

• GPS and turn-by-turn navigation: Dijkstra's algorithm (BFS with edge weights) or A* on road networks. Modern maps use bidirectional A* with contraction hierarchies to find routes across continents in milliseconds.
• Network packet routing: OSPF (Open Shortest Path First), the internet's core routing protocol, runs Dijkstra's algorithm on the network topology to find the minimum-cost path for each packet.
• Robotics: Mobile robots (warehouse robots, vacuum cleaners, surgical robots) use variants of A* or RRT (Rapidly-exploring Random Trees) to plan collision-free paths in 2D or 3D workspaces.
• Puzzle solving: Sliding tile puzzles (15-puzzle), Rubik's Cube solvers, and Sokoban all use graph search, often with bidirectional BFS or IDA* (iterative-deepening A*) to handle the astronomically large state spaces.

Time and space complexity

V = vertices (cells), E = edges, d = solution depth, b = branching factor. On a 4-connected grid, E ≈ 4V, so BFS/DFS are effectively O(V).