Choose the straightest shortest path if possible about astar HOT 8 CLOSED

There are several solutions that compute a nicer path more often (though none work 100% of the time). RedBlobGames has an article on this: http://www.redblobgames.com/pathfinding/a-star/implementation.html#troubleshooting-ugly-path

I've been experimenting with it, but I haven't come to a solution yet that I really like. I'll see if I can cook something up this weekend. (no promises).

from astar.

One solution I haven't tried yet is to start the neighborhood search with the tile that is on the line from the current cell to the finished cell.

from astar.

I've been reading your commits and in the commit where you've changed the heuristic to Chebyshev you removed something that u commented out.
// Avoid zig-zag paths by correctly penalizing the cost of diagonal movement
Did it use to work? Or u never checked?

from astar.

@SpreedBlood unfortunately that approach made the heuristic A* depends on for finding the shortest path inadmissible (it overestimates paths over the diagonal). Which caused some non-optimal paths to be found.

from astar.

I thought some more about this issue. You get the straightest path, if you follow the direction you were following. I can look up what offset was last used for the path so far and start exploring that offset in that direction first (in the case of ambiguity). It will take me a bit to figure out how to do this fast. But I think this will work.

Meanwhile I'm working on the last improvements off the viewer so I can more easily verify that changes like this have the desired effect.

from astar.

Hmm I haven't had much luck with my own idea, or other hacks. It might be best to include a string pulling algorithm in the library. I've found some info here: https://www.gamedev.net/forums/topic/539575-string-pulling-explained/

from astar.

String pulling seems to work brilliantly, I've got a WIP branch here: https://github.com/roy-t/AStar/tree/feature/string_pulling (note you can only see the effect in the viewer in release builds, (which only shows the end result) the debug build only shows the path finding steps and doesn't know about string pulling yet).

There are some issues/TODOs in my current implementation that need to solve, but I'm confident they do not block my progress.

• Make sure smoothing paths does not conflict with the movement pattern of the agent
• Make sure path segments do not become disconnected by smoothing (oops)
• Visualize the path smoothing in the debug mode in the viewer
• Test the performance (probably OK since it only affects the final path, but we might want to make the smoothing step optional).

from astar.

I've implement the string pulling algorithm. In a new section in the readme you can see how its used and what affect it has. I think this will make you very happy :). The changes are also in the update NuGet package (v1.2) which I've uploaded just now.

from astar.