- Drag between two locations to perform a pathfinding task. The progress of the bidirectional NBS algorithm will be animated.
- The plot on the bottom of the page shows the cumulative work by forward/backwards A* up to a given g-cost. In bidirectional
search, the key is setting a meeting point (in g-costs), where the searches divide the work between the backwards and forward search
and meet a given cost.
- The red line is the cumulative work required to solve with forward A*.
- The blue line is the cumulative work required to solve with backward A*.
- The purple line is the cumulative work required to solve with a bidirectional search that meets at the given point.
- The green line is the work by the bidirectional NBS algorithm. This line only appears after the search is complete, and is approximately at the place where the forward and backwards A* lines cross.
- You can click on the graph and drag to see what happens when a bidirectional search meets at different meeting points.
- NBS is guaranteed to do no more than 2x the work of the best possible algorithm (given our theoretical framework, which isn't too restrictive).
- Bidirectional search tends to do well when there are costs in the world, asymmetry, or imperfect heuristics.
- Unidirectional search does well when the heursitic is perfect near the start/goal. (e.g. both the start and goal are in open space)
Maps: