PathFinding.js
PathFinding.js copied to clipboard
qiao
Bidirectional A* path reconstruction is incorrect
When a node has been settled by both the forward and backward search, the search can be terminated, as the shortest path has been found. This does not mean, however, that this node must lie on the shortest path.
Take this example in a graph: http://www.cosketch.com/SavedImages/phS9Zraa.png Forward search starts at s, inserts v into queue with weight 6 and t with weight 10. Backward search starts at t, inserts v into queue with weight 6 and s with weight 10. Forward search removes v from queue, finds t with weight 12, does not add to queue, settles v. Backward search removes v from queue, finds s with weight 12, does not add to queue, settles v. The search is aborted here, yet v is not on the shortest path.
Screenshot to illustrate the problem: http://i.imgur.com/N9FaLY6.png The shortest path is obviously incorrectly drawn.
You are correct. The Bi-Directional A* Search is not guaranteed to find the shortest path and it has been noted in the README. And PathFinding.js provides a method named smoothenPath which can smoothen the found path(Though the smoothened path may not be the shortest one either).
You could track which Cell has the currently smallest tentative distance, this Cell will be on the path. So, when taking a cell from the queue, check if it has already been found by the other search. If so, its tentative distance is its forward distance plus its backward distance. Keep track of the node for which this is minimal, it will be on the shortest path. Then it's just a matter of retracing the parents in both search trees.
In http://i.imgur.com/N9FaLY6.png it looks like a diagonal step has the same weight (=distance) as non-diagonal one. In this case the route can be considered shortest.
Not true, see https://github.com/qiao/PathFinding.js/blob/master/src/finders/BiAStarFinder.js#L106
qiao wrote:
Well it does find the path, it just shows the wrong one ;)
lorenzhs wrote:
You are correct. The Bi-Directional A* Search is not guaranteed to find the shortest path and it has been noted in the README.
You implementation is not guaranteed to find the right path, because it has a bug ;)
The distance in this example is 14.24 = 10 + 3 * sqrt(2). The best should be 13.66 = 8 + 4 * sqrt(2).
The error is located here: https://github.com/qiao/PathFinding.js/blob/master/src/finders/BiAStarFinder.js#L113 "f" is the compared key on the heap. You change it without updating the heap. So it can't be moved to the right place. That means when you call pop() you don't always get the best f-value. When you can't directly remove it from the heap, you can add an "invalid" boolean to the neighbour. When you find this element you have to add it again to the open list(s). The same problems exists for non-bidirectional searches. But here it's much harder to find an example on smaller maps.
True, but that might be a separate issue. What I said was that the implementation correctly computes the shortest path, but retrieves it incorrectly. Thus, the result is wrong. @surrim just proved that it doesn't even compute the correct result, so there are two things that need to be fixed.