Overview

|

Try it out

|

Test on your data

This demo is associated with a GDC 2018 talk on bidirectional search. It is a simple tool for analyzing whether bidirectional search is the best approach in the problems you are solving in your pathfinding representation.

To use the tool you need to optimally solve a pathfinding problem in your game in both the forward and backwards directions. As you solve each of these problems, you need to log the g-cost of every state expanded, including the goal. Then, paste the raw numbers for the forward and backwards search in the text boxes below. The resulting plot will help you understand whether bidirectional search will work well in your game.

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 estimate of the work that would be performed by the bidirectional NBS algorithm.

Guidelines:

• [Case 1] If the purple line is U shaped, then bidirectional search will work very well in your domain. (NBS is currently the best general-purpose bidirectional search algorithm.)
• [Case 2] If the purple line is an upside-down U or mostly flat, then bidirectional search will not work well.
• [Case 3] If the purple line is sloped significantly to the left or right, then your problem has significant forward/backwards asymmetry. Bidirectional search (NBS) will work well because it will find the right direction to search.

The plot will go here when generated.