Discussion on algorithms

[jiaweirobot]

Hello, thank you very much for the code, the current algorithm is exceptionally fast to compute, but after referring to it I realized that the algorithm has some differences from the actual AStar algorithm. For example, the cost function of the AStar algorithm calculates the sum of the distances between the starting point and the target point preferentially, which is indeed fine without considering obstacles, but if obstacles are added, it is more similar to the (Greedy Best First Search) algorithm if you use the minimum heap, here is my actual test, is it designed this way on purpose?

[roy-t]

Hey! Thanks for your comments.

This is weird, in your example yellow is indeed not the shortest path (32 steps) and I can easily draw a path going south first that is shorter.

I haven't seen this show up in test cases. I do intend for this library to give you the truly shortest path. What did you mean by:

"the cost function of the AStar algorithm calculates the sum of the distances between the starting point and the target point preferentially"

Did you spot that in the code?

[roy-t]

I have created a unit test that, I think, mimics the picture you are showing: #51

But I can't reproduce the problem you have. In both directions the path finder finds the correct 25 step path, not the longer 32 step path. Are the coordinates I used the same as you used? Are you also sure that you are using the latest version?

[jiaweirobot]

I'm using the latest version, I think maybe I made some adjustments on the parameters or I changed something that caused it, I'm checking it out, thanks for your support!

[jiaweirobot]

I found my problem, it's that I didn't calculate its travel time for the route, the travel time for each line is 0, that is, the parameter G is missing inside the A* algorithm, which causes it to degenerate to the GBFS algorithm (f(n)=G+H), after re-correcting it the result is correct, thank you, the problem can be closed now!

[roy-t]

Ah, that makes sense! Thanks for sharing that! Got me scared that I messed something up that only shows up in rare cases!