Pathfinding.js – Visualizations and Playground
qiao.github.ioand then there's this awesome thing:
If anyone has a tougher path planning problem and needs a better heuristic, I wrote an article a few years ago that might help: http://razorcode.net/articles/vehicle-path-planning.html
Thanks for writing this article! Would you mind if I share it in WeeklyRobotics(https://weeklyrobotics.com/) next week?
Feel free, it exists to be read. And you just gained a subscriber.
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?
How does this A* work. It seems almost "intelligent"!!
Here's a fantastic intro from Red Blob Games: https://www.redblobgames.com/pathfinding/a-star/introduction...
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".
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.
Edit: Ugh, how do I escape an asterisk? >.<
This is so fun, wasted probably 30 min building mazes.
Several years old, but still awesome.
Does anyone know what the "Trace" algorithm does? I can't find anything on Google.
The last commit on the repo https://github.com/qiao/PathFinding.js/blob/master/visual/in...
says "Remove Trace finder as it is the same as BestFirstFinder"
For me it hangs on IDA*
otherwise mighty well done!
Ideas to add:
- a short description of the algorithm
- zoom out
+ knight tour
It's not hanging, it just takes a bit before it gets going. I had to wait about 30 seconds before the IDA* visualization started running.
Also thought IDA* hanged. An indicator indicating initialization would be helpful (didn't see one).
Indicators that indicate are of the best kind.
Joke aside: kudos on turning a perceived frustration into a feature fix. I wouldn't have thought about that.
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.
A faster way to find paths on grids http://mikolalysenko.github.io/l1-path-finder/www/
This is a great demo !!! Very interesting. It allowed me to select the appropriate algorithm for a specific purpose.
I love this, useful for teaching purposes!