title: Bidirectional search or not? Speed considerations
body: <p>I'm implementing an algorithm which has to quickly decide whether a path exists between two cells in a 2D grid (for a maze-like game). It does not actually have to provide the path. This algorithm is run many thousands of times, so it must be fast.</p>
  
  <p>The quirk is, the two cells are very close to each other (within a Manhattan distance of 2), so for most reasonable mazes, the path is often trivial. Right now I have pure breadth-first search, but I'm considering implementing a bidirectional variant. The problem is, of course, that in the cases a path does not exist, the bidirectional search will fail slower, because it searches two connected components instead of one, though if a path exists, it will find it faster (probably).</p>
  
  <p>So my question is, does anyone have any experiences with bidirectional search and how it behaves in the cases mentioned above? Is the speed difference actually quite marginal?</p>