Pathfinding.js – Visualizations and Playground • Hacker News Board

Re: Pathfinding.js – Visualizations and Playground

#11

Post by 33a » Sun, Mar 03, 2019, 5:27 AM UTC

A faster way to find paths on grids http://mikolalysenko.github.io/l1-path-finder/www/

Re: Pathfinding.js – Visualizations and Playground

#12

Post by steverob » Sun, Mar 03, 2019, 6:38 AM UTC

How does this A* work. It seems almost "intelligent"!!

Re: Pathfinding.js – Visualizations and Playground

#13

Post by gpm » Sun, Mar 03, 2019, 7:18 AM UTC

steverob wrote: post #12

How does this A* work. It seems almost "intelligent"!!

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".

Re: Pathfinding.js – Visualizations and Playground

#14

Post by xtagon » Sun, Mar 03, 2019, 7:24 AM UTC

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?

Re: Pathfinding.js – Visualizations and Playground

#15

Post by huxflux » Sun, Mar 03, 2019, 7:43 AM UTC

I love this, useful for teaching purposes!

Re: Pathfinding.js – Visualizations and Playground

#16

Post by nnevala » Sun, Mar 03, 2019, 8:01 AM UTC

steverob wrote: post #12

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...

Re: Pathfinding.js – Visualizations and Playground

#17

Post by vfinn » Sun, Mar 03, 2019, 9:13 AM UTC

throway88989898 wrote: post #3

For me it hangs on IDA* otherwise mighty well done! Ideas to add: - a short description of the algorithm - zoom out + knight tour

Also thought IDA* hanged. An indicator indicating initialization would be helpful (didn't see one).

Re: Pathfinding.js – Visualizations and Playground

#18

Post by msadowski » Sun, Mar 03, 2019, 9:20 AM UTC

razorunreal wrote: post #8

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?

Re: Pathfinding.js – Visualizations and Playground

#19

Post by jonluca » Sun, Mar 03, 2019, 9:23 AM UTC

skosch wrote: post #4

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"

Re: Pathfinding.js – Visualizations and Playground

#20

Post by taneq » Sun, Mar 03, 2019, 11:14 AM UTC

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? >.<