search

andreasterrius / godot-2d-gdscript-astar

A* Implementation in gdscript
The Unlicense
8 stars 0 forks source link

The g(x) variable should be the true accumulated cost #3

Open byfron opened 4 years ago

byfron commented 4 years ago

First of all, nice piece of code! I found it very useful.

I noticed a small bug that makes the search behave like Dijkstra rather than A. In the demo image you can see that the path is not actually the shortest, while A is supposed to guarantee shortest path.

I believe that the cost needs to be computed as cost so far + heuristic cost to the goal .
The line

var gx = _distance(prev, curr)

should instead represent the "true" cost accumulated in the current tile.

I hope it helps!

andreasterrius commented 3 years ago

Hello, I actually completely missed this issue for some reason.

Thank you for bringing this up, I don't exactly remember this code since this has been awhile, but you are correct that A* should be able to guarantee shortest path (and on this script it doesn't), since distance is admissible heuristic in this case. For the fix g(x) should probably be the cost from start to curr, instead of prev to curr.