search

roy-t / AStar

A fast 2D path finding library based on the A* algorithm. Works with both grids and graphs. Supports any .NET variant that supports .NETStandard 2.0 or higher. This library has no external dependencies. The library is licensed under the MIT license.
http://roy-t.nl
MIT License
340 stars 60 forks source link

Discussion on algorithms #50

Closed jiaweirobot closed 7 months ago

jiaweirobot commented 7 months ago

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? image

roy-t commented 7 months ago

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 commented 7 months ago

I have created a unit test that, I think, mimics the picture you are showing: https://github.com/roy-t/AStar/pull/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?

image

jiaweirobot commented 7 months ago

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 commented 7 months ago

image 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 commented 7 months ago

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