search

hjweide / pyastar2d

A very simple A* implementation in C++ callable from Python for pathfinding on a two-dimensional grid.
MIT License
150 stars 57 forks source link

prevent locally wandering paths by making diagonals cost 1.4x more #27

Open dicethrow opened 2 years ago

dicethrow commented 2 years ago

Hi all,

I noticed that diagonals do not have a heuristic cost that is less than the taxicab distance, so I've added it in.

Previously, this resulted in paths that seemed to wander around the shortest path somewhat, but now it looks good.

The technique I used is to approximate the diagonal distance of a unit square as the relative heuristic. However to keep the math using integers, I chose a square of side length 10 as the base cost, meaning that the diagonal would have cost 10*sqrt(2) = 14.14..., which I've approximated as 14. This seemed to work well so I haven't tried to see if there's any more optimization that can be done here.

hjweide commented 2 years ago

Thanks for taking the time to open this. Could you please attach an image showing the behavior you mention? This code was originally written to extract contours from images (where the weights do not form a uniform cost grid) so adding arbitrary values may not be the best solution.

dicethrow commented 2 years ago

No worries, here's an example:

So if I run the maze example code as in the readme file, but enable diagonals, the top-left corner of the small maze looks like this:

maze_small_soln_diagonalsenabled_original_topleftcorner

With my pull request, it looks like this

maze_small_soln_diagonalsenabled_pullreq_topleftcorner

I can see some non-shortest-path segments with the original implementation. Although the pull request isn't perfect, it looks like it does the best job possible with the 8-direction options. I came across this approach for a sub-heuristic somewhere but can't find the source, alas.

I haven't considered using this in non-black-and-white images, maybe it would have less of an effect there.

Here are the full images: original maze_small_soln_diagonalsenabled_original

pull request maze_small_soln_diagonalsenabled_pullreq

hjweide commented 2 years ago

Thanks! Let me think about the best way to handle this. I'm wondering:

  1. if this can be fixed easily by changing the order in which nodes are added to the priority queue, or
  2. if the user should be able to specify an additional penalty cost for diagonal moves that defaults to zero (similar to your idea).

Any other suggestions?

dicethrow commented 2 years ago

on 1) - I originally wrote this fix a year ago, so I'm a bit rusty on how the priority queue works here, I'll have a play with this approach later, I haven't got thoughts on this yet

on 2) - the 10-or-14 thing is based on diagonal distance in a square grid being sqrt(2) of the side length, so I'm not sure that it's best left as a user adjustable penalty cost because it does have geometric significance

I think the pull request currently only works for black-and-white images, otherwise pixel values would swamp this 10-or-14 heuristic. I had a play around and haven't yet worked out how to fix it. Maybe this wandering path thing only happens for black-and-white maps?

I'll comment back if I work it out. Thanks for looking at this!