Bidirectional BFS maze algorithm
Bidirectional BFS floods from the start and the exit at the same time and stops when the two floods meet, finding the shortest path with less exploring.
How it works
It runs two breadth-first searches, one from each end, expanding one layer at a time from whichever side has the smaller frontier. The moment a cell from one side touches a cell from the other, the shortest route is the two halves joined at that meeting point.
Each flood only needs to reach about halfway, and a flood's size grows with its radius, so in open areas it explores far less than plain BFS. In a twisty perfect maze the saving is smaller, but it never explores more.
What to watch for
Watch two floods grow toward each other from opposite corners and the path light up the moment they touch.
Properties
- Shortest path
- Yes
- Explores
- Up to about half what BFS does
- Memory
- Two frontiers
Race it
Pick it in the race and see who reaches the exit first, or run it in the studio.
FAQ
Is bidirectional search always faster?
It explores no more than BFS and often much less, but it needs to know where the exit is, so it can't be used when you're searching blind.