I’m trying to implement A*.
I’m storing the queue of nodes to visit in a min-heap, and I’m seeing the same node being added more than once to it (with different priority). Wikipedia’s pseudocode suggests to avoid duplicates in the queue (if neighbor not in openSet), but:
- I’m not sure how to do that in a good way. I’m using a min-heap to store the queue, and there’s no way to quickly search it to avoid duplicates.
- I’m not sure if I even need to bother, as it doesn’t seem to affect correctness, but maybe I just didn’t find the right testcase.
So is this problematic or not? Can I just keep the duplicates in the queue and not worry about it? Can this cause performance issues?
Wikipedia makes a remark about the duplicates. It suggests to eliminate them to avoid getting a suboptimal path at the end (and suggests a way to do so), but this sounds like nonsense to me, because the suboptimality can be trivially avoided, and their pseudocode already does so (before updating the ‘parent node’ of a node, they check if the new path is cheaper than the existing one (if tentative_gScore < gScore[neighbor] in their pseudocode), which already should be enough).
Here’s an example scenario where I’m getting the duplicate.
I’m doing pathfinding on a grid, with 4-way movement, and the heuristic being manhattan distance to the goal (with ties broken by eucledian distance to the goal).
Let’ say I’m in this situation:
The gray cells represent the min heap, with the number representing the estimated total cost to the goal.
In this state, the next cell to be processed is the one above 2. And that causes the cell above that one (currently having cost 28) to be added to the heap again with cost 26.
