Interactive demo
Bidirectional Search
Why search from one end only? Bidirectional search runs Dijkstra's algorithm from the start and from the goal at the same time. In open space, two small circles cover less area than one big one.
Draw walls or mud on the grid and drag the start and the goal. Once a search is finished, every change is searched again right away. Teal is the search from the start, violet the search from the goal. It keeps going for a moment after they touch: the first contact is not always the cheapest connection.
Playback
- Expanded
- –
- Frontier (max.)
- –
- Path cost
- –
Press Play or Next Step to start the search.
Grid
Options
Legend
- Start (drag to move)
- Goal (drag to move)
- Wall
- Mud
- Frontier from the start
- Visited from the start
- Frontier from the goal
- Visited from the goal
- Expanded right now
- Path
Properties
Optimal
Yes
Stops only when no cheaper connection between the two searches is possible.
Weighted cells
Yes
Both searches use the real costs, mud included.
Heuristic
No
Needs none; the second search makes up for part of the missing direction.
Any angle
No
Moves from cell to cell, straight or diagonally.
All pathfinding algorithms compared
| Algorithm | Optimal | Weighted cells | Heuristic | Any angle |
|---|---|---|---|---|
| Breadth-First Search | Without mud and diagonals | No | No | No |
| Depth-First Search | No | No | No | No |
| Dijkstra's Algorithm | Yes | Yes | No | No |
| Bidirectional Search this page | Yes | Yes | No | No |
| Greedy Best-First Search | No | No | Yes | No |
| A* Search | With weight 1 and an admissible heuristic | Yes | Yes | No |
| Jump Point Search | Without mud | No | Yes | No |
| Theta* | No | Shortcuts over open ground only | Yes | Yes |
1. Two frontiers
Each search keeps its own costs and parents. In every step, the side whose next cell is cheaper expands it, so both frontiers grow at about the same rate.
2. When to stop
Whenever a cell is reached by both searches, their costs add up to a complete path, and the best one is kept. The search may stop once the next cells of both sides together cost at least as much as that path. Only then is no cheaper connection possible.
3. The savings
For a path of length d, one search covers a disk of radius d, two searches cover two disks of radius d/2: half the area on a grid, and far less in graphs that branch quickly. Route planners for road networks build on this idea.