The understanding of bidirectional search changed significantly in the last few years. This talk gave a high-level overview of when you will want to use bidirectional search. The material here supplements the talk with technical details, demos, and test tools for determining if bidirectional search will work well for your game.
Talk Slides
- Download slides (pdf - 6MB)
- [2017] Front-to-End Bidirectional Heuristic Search with Near-Optimal Node Expansions
This paper develops the NBS algorithm and describes how it works. - [2017] The Minimal Set of States that Must be Expanded in a Front-to-end Bidirectional Search
This paper generalizes the MM algorithm (below) to one that can meet anywhere, and shows that one such meeting point must be optimal. - [2017] Sufficient Conditions for Node Expansion in Bidirectional Heuristic Search
This paper develops the theory behind bidirectional search and which states must be expanded. - [2016] Bidirectional Search That Is Guaranteed to Meet in the Middle
This paper describes how to build a bidirectional algorithm (MM) that meets in the middle. - NBS Source Code
- NBS.h A generic implementation of NBS that is designed for any undirected state space.
- BDOpenClosed.h A generic open/closed list data structure for the ready and waiting priority quees used by NBS.
- NBSQueue.h The high-level queue for NBS that maintains the forward and backwards frontiers for NBS search.