Look, I was merely trying to give the author more information by verifying your observation. Your remark to me seems reasonable only if the author can see how many upvotes/downvotes a certain comment has. I don't know if he can.
It just keeps exploring locations adjacent to locations it's already explored.
It chooses the next location by whatever one has the lowest "length of best known path to get there + estimate for distance to goal". The estimate for distance to goal is usually something like "distance as the crow flies".
This is a very useful tool and helped me understand Jump Point Search for a hobby project, which as it turns out is significantly faster than A* for certain use cases.
Are there any path finding algorithms for orthogonal grids optimized for frequent changes in the environment, particularly moving opponents in a game where you can't predict their next move with certainty? A* and friends do well at finding shortest paths between a start and a goal, but what if the obstacles change after you start along that path?
I was surprised at how much slower the Jump Point Search variants were than vanilla A-star. I thought it was meant to be an order-of-magnitude optimisation over A-star?
Also, any idea what the 'Trace' algorithm at the bottom is? It seems significantly faster/more efficient than the others but I can't find it in the github repo and the live version of the library is minified.
22 comments
[ 2.7 ms ] story [ 60.1 ms ] threadotherwise mighty well done!
Ideas to add:
- a short description of the algorithm
- zoom out
+ knight tour
Joke aside: kudos on turning a perceived frustration into a feature fix. I wouldn't have thought about that.
Does anyone know what the "Trace" algorithm does? I can't find anything on Google.
says "Remove Trace finder as it is the same as BestFirstFinder"
https://anvaka.github.io/ngraph.path.demo/
https://github.com/anvaka/ngraph.path
It chooses the next location by whatever one has the lowest "length of best known path to get there + estimate for distance to goal". The estimate for distance to goal is usually something like "distance as the crow flies".
Are there any path finding algorithms for orthogonal grids optimized for frequent changes in the environment, particularly moving opponents in a game where you can't predict their next move with certainty? A* and friends do well at finding shortest paths between a start and a goal, but what if the obstacles change after you start along that path?
Also, any idea what the 'Trace' algorithm at the bottom is? It seems significantly faster/more efficient than the others but I can't find it in the github repo and the live version of the library is minified.
Edit: Ugh, how do I escape an asterisk? >.<