search

CodingTrain / AStar

AStar example with community contributions
117 stars 66 forks source link

Added example of tie-breaker code for faster and more "expected" resu… #2

Closed ootsby closed 7 years ago

ootsby commented 7 years ago

…lts when using grid movement in relatively open map searches and the like.

Hi, I just watched the stream and noticed that you hit a common snag with using AStar with grid movement in that you were getting lots of cells examined and "ugly" paths. I've added some bits to allow switching diagonals on/off and an example of how to use an extra heuristic element to break the inevitable dead-heat situations that occur all the time with Manhattan distance measures. No problem if it's not something you want to include but I thought you'd be interested in understanding the problem a little more as hardly any standard tutorials etc. will mention it.

shiffman commented 7 years ago

This is great, thank you! Unfortunately I goofed and cleaned up the code and added a bunch of comments before merging. Can you check and resolve conflicts?

ootsby commented 7 years ago

Okay, I resolved the conflicts. I'm looking at adding some controls and ways of probing the algorithm state on the page to help people understand what's going on but I see there's another pull request with some broader changes and more of a performance focus so I don't know which way you want to take things.

shiffman commented 7 years ago

Thanks for this! I agree a simple interface with some basic controls (starting / stopping, diagonals on/off, etc.) would be useful!