Parallel A* search in C# - different paths

Question

I'm working on some bidirectional A* algorithm. I'm searching from end to start, and from start to end. When the first thread encounters with a node from other thread(from open or closed list) it stops and draws a path back.

But I have the problem when the thread take different paths and they dont meet where they should.

Example: http://i.imgur.com/ittIAlI.png

Answer 1

This was a common problem that discouraged research of bidirectional search until Kaindl & Kainz proved it unnecessary in 1997. Section 2.3 of PNBA*: A Parallel Bidirectional Heuristic Search Algorithm provides additional historical background, as well as a (parallel) bidirectional algorithm that overcomes this issue.

You may wish to read Yet Another Bidirectional Algorithm for Shortest Paths first as the (serial) NBA* algorithm it describes is referenced by the first paper extensively.

I have just successfully adapted my open source Hexgrid PathFinding utility found here to use a serial version of PNBA*. (Really about half-way between NBA* and PNBA*) This will be uploaded within a day or two.

Making the Shortest Path Even Quicker gives an overview of developing the Bing Maps path finder using Bidirectional A* with pre-processing. A detailed description of the preprocessing work, and use of the relevant algorithm, is available in Reach for A* and Better Landmarks Within Reach