pathfinding playground
BFS, DFS, Dijkstra and A* exploring a grid you draw
Question
How do four pathfinding algorithms differ on the same grid? Draw walls and mud, move the start and the goal, then step through breadth-first search, depth-first search, Dijkstra and A* and watch the frontier, the explored cells and the final path. Everything runs in this browser; it is not tied to any project.
Bench
Keyboard: arrow keys move between cells, Home and End jump along the row, Enter or Space applies the selected tool.
Touch: tap a cell to apply the tool. Dragging scrolls the page, so draw lines with a mouse or the keyboard.
Queue, oldest first. Fewest moves. Ignores weights, so it can walk through mud.
- S start
- G goal
- # wall, cannot be entered
- ~ mud, entering it costs 5
- f frontier: discovered, not explored yet
- · explored
- * final path
Reduced motion is on: run finishes at once instead of animating. Step still explores one cell.
Draw walls, move the start and the goal, pick an algorithm, then step or run.
- Status
- not started
- Explored
- 0
- Frontier
- 0
- Path moves
- 0
- Path cost
- 0
Fewest moves: no path has fewer moves. Lowest weight: no path costs less. Without mud they are the same thing. Explored counts cells, not time.
What to watch
- frontier and explored
- The frontier (f) holds cells that were discovered but not explored. Exploring a cell moves it to the explored set (·) and adds its new neighbors to the frontier. The algorithms differ only in which frontier cell they take next.
- BFS
- Takes the oldest frontier cell, so it grows in rings. With every move costing the same, the first path it finds has the fewest moves. It does not look at mud: draw a mud strip across the shortest route and it goes straight through.
- DFS
- Takes the newest frontier cell, so it commits to one direction until it hits a dead end. It finds a path whenever one exists, but not the shortest: on an empty grid it often wanders. Compare its path length with BFS.
- weighted and unweighted
- Unweighted algorithms count moves. Weighted ones add up the cost of the cells entered. With mud, the fewest moves and the lowest cost can be different paths, and only Dijkstra and A* optimize the second.
- Dijkstra
- Always explores the cell with the lowest total cost so far, which is why the first time it reaches the goal the cost is minimal. It has no idea where the goal is, so it spreads in every direction.
- A*
- Adds a guess of the remaining distance (Manhattan distance, never more than the true cost here because every cell costs at least 1). That keeps the result optimal while steering the search toward the goal. Press compare to see it explore fewer cells.
- tie-breaking
- Neighbors are tried in the order up, right, down, left. Equal priorities go to the entry queued first; A* first prefers the cell closer to the goal. This is why the same grid always gives the same search.
Limits
- Movement is up, right, down and left only. There are no diagonals.
- Mud is the only weight, fixed at 5. Entering a cell costs its weight; the start cell is never charged.
- Grids hold at most 30 × 16 cells, and a search or a comparison finishes quickly on them.
- Explored counts are not timings. Real performance depends on the data structures, which this page keeps deliberately simple.
- Generated grids are repeatable by seed but are not guaranteed to have a path.
Fidelity
A teaching implementation written for the Lab, with fixed tie-breaking so every run repeats. Movement is four-directional and mud is the only weight. Explored counts are not timings.