Mugen87
commented
4 years ago It would be indeed helpful if you can reproduce a case where the limitation of the current implementation is demonstrated. TBH, I do not understand the problem so far.
Our code is based on a C++ reference implementation by Mat Buckland. It would be great if we could find a way to further improve it (and make the additional code robust with a new unit test).
Unforutnately, I am unable to replicate a test case whereby the shortest path tree already has something registered ... ie.
if this._shortestPathTree.has(edge.to).Compare: https://github.com/Mugen87/yuka/blob/master/src/graph/search/Dijkstra.js#L113 https://github.com/Mugen87/yuka/blob/master/src/graph/search/AStar.js#L130
versus:
https://github.com/Glidias/Asharena/blob/master/src/arena/pathfinding/GKDijkstra.hx#L116-L131 https://github.com/Glidias/Asharena/blob/master/src/arena/pathfinding/GKAstar.hx#L52-L63
I noticed your implementation does not check if the candidate destination node being considered already exists in priority queue for typical re-sort. (Rather than push new entry to priority queue). Is this deliberate? I was wondering if BinaryHeap structure is an exception to this when it comes to priority queues.., but other implementations like what i see here https://github.com/Habrador/Self-driving-vehicle/blob/master/Self-driving%20vehicle%20Unity/Assets/Scripts/Pathfinding/Hybrid%20A%20star/HybridAStar.cs#L275 also does explicitly check for already existing re-sorts rather than direct push.