Pathfinding
Depth-First Search Visualiser
A stack, so the search runs down one corridor before trying another.
Depth-first search: a stack, so the newest cell comes out first. That runs down one corridor before trying another.
- Cells expanded
- 0
- On the stack
- 1
There are 303 cells to search on this board. The gap between that and the cells expanded is what a better search order buys you — walls and mud change it, so redraw the board and watch it move.
- Start
- End
- Wall
- Mud (costs 5)
- Waiting to be expanded
- Expanded
- Route
function dfs(grid, start, end) { const stack = [start]; const cameFrom = new Map([[start, null]]); while (stack.length > 0) { const cell = stack.pop(); // the newest waiting cell if (cell === end) return path(cameFrom, end); for (const next of neighbours(grid, cell)) { if (cameFrom.has(next)) continue; cameFrom.set(next, cell); stack.push(next); } } return null; // the end is walled off}The highlighted line is the one that produced the picture on the left.
What Depth-First Search does
Depth-first search is breadth-first search with a stack instead of a queue. Taking the newest cell rather than the oldest means it commits to a direction and keeps going until it hits a wall, then backs up to the most recent place it had a choice. It finds a route, but almost never the shortest one.
How it works, step by step
- Put the starting cell on a stack and record that it came from nowhere.
- Take the cell from the top of the stack — the one added most recently.
- If it is the goal, follow the recorded parents back to rebuild the route.
- Otherwise push every unseen neighbour, and carry on from the last one pushed.
What to watch for
- The visited cells form a long snaking line rather than a growing blob. That line is the search committing to a direction.
- The route it reports usually wanders badly, even on an empty board with the goal in plain sight.
- It can expand far fewer cells than BFS, or far more, depending entirely on whether its first guess pointed the right way.
- Recursive DFS is the same algorithm: the call stack is the stack.
Cost
| Time | O(cells + edges) |
|---|---|
| Extra space | O(cells) for the stack |
| Finds | Some route, rarely the shortest |
| Handles costs | No |
| Waiting list | Stack (last in, first out) |
When to reach for it
When you need to reach everything rather than reach it quickly: exploring a whole graph, finding connected regions, detecting cycles, generating mazes, or backtracking through a puzzle. Never use it when the shortest route is what you are after.