4 ms·

Could anyone recommend a Javascript pathfinding library that doesn't assume a grid-based graph?

by rcfox 11y ago

keslag 11y ago
I've not come across a node or mesh based pathfinding library, though you can roll your own A* with modifications.
iamdave 11y ago
It's not a javascript library, but MapBox recently released the Directions API for pathfinding within the context of mapping: https://www.mapbox.com/developers/api/directions/ https://www.mapbox.com/developers/api/directions/ So...somewhat relevant to what you're asking.
- imaginenore 11y ago
  Directions algorithms on real life maps are quite different from what they teach you in CS classes. Just think of the amount of computation to get the best directions between SF and NYC, taking traffic into consideration. I'm pretty sure none of the services actually give you the best solution, but something that's pretty close to it. Full USA map graph contains around 24 million nodes, 58 million edges. Your regular A* just doesn't cut it.
  - rcfox 11y ago
    I'm sure you're right, but it seems like traffic would be easy enough to consider by simply increasing specific edges' costs. As for the scale issue: most of these nodes and edges will never change, so it might be possible to calculate a Dijkstra map.
    - imaginenore 11y ago
      The point is, if you add traffic into consideration, you can't have almost anything precalculated.
      - amitp 11y ago
        A* runs faster if you have better path cost estimates. To get the shortest paths, you want an estimate that's as close to the true cost, but not greater than it. You can precalculate to generate good estimates. Traffic makes the costs higher than normal, so those precalculated estimates are still useable (if you raise the costs because of traffic, the estimates continue to be lower than the true cost), and still much better than what you get without precalculation.
  - amitp 11y ago
    Better distance estimates and better graphs can push A* to work on larger problems. ALT gives better distance estimates: http://research.microsoft.com/pubs/64511/tr-2004-24.pdf http://research.microsoft.com/pubs/64511/tr-2004-24.pdf (PDF link) (or these slides http://www.cs.princeton.edu/courses/archive/spr09/cos423/Lectures/reach-mit.pdf http://www.cs.princeton.edu/courses/archive/spr09/cos423/Lec... ). Transit nodes do too, I think. Contraction hierarchies and arc flags let you preprocess the graph to give better information to A*. (I've not implemented any of these myself)
nacs 11y ago
You could use pretty much any pathfinding algorithm (A* for example) even if you don't have a grid based graph. In the implementation, you would just need to modify how the algorithm transverses each valid walkable/unwalkable node (how to go from waypoint to waypoint) and possibly how much extra cost each node has (water/mountainous terrain could have increased cost for example) instead of letting it go the usual up/down/left/right and possibly diagonals for grids. If the waypoint based approach isn't ideal for you, then you should look up "navigation mesh" [1] pathing which is a bit trickier to implement but works well when you have a bunch of large empty/walkable areas. [1]: https://en.wikipedia.org/wiki/Navigation_mesh https://en.wikipedia.org/wiki/Navigation_mesh
malkia 11y ago
At previous job some folks used recastnagivation (C/C++) library for what you are looking for - https://github.com/memononen/recastnavigation https://github.com/memononen/recastnavigation And there seems to be "emscripten" version of it (just googled it) - https://github.com/vincent/three-arena/tree/master/recastnavigation https://github.com/vincent/three-arena/tree/master/recastnav... - as part of the "three-arena" project demo here - http://three-arena.com/examples/#simplest.js http://three-arena.com/examples/#simplest.js and the compiled emacsen source here - http://three-arena.com/node_modules/recastjs/lib/recast.js http://three-arena.com/node_modules/recastjs/lib/recast.js also this one: https://github.com/vincent/recast.js https://github.com/vincent/recast.js found by looking here - https://groups.google.com/forum/#!searchin/recastnavigation/emscripten/recastnavigation/1i2xwXudO8c/rOzfG-1U_tMJ https://groups.google.com/forum/#!searchin/recastnavigation/... Also test from there: https://vincent.github.io/recast.js/tests/test.webgl.html https://vincent.github.io/recast.js/tests/test.webgl.html

Could anyone recommend a Javascript pathfinding library that doesn't assume a grid-based graph?

by rcfox 11y ago

Could anyone recommend a Javascript pathfinding library that doesn't assume a grid-based graph?

keslag 11y ago

I've not come across a node or mesh based pathfinding library, though you can roll your own A* with modifications.

iamdave 11y ago

It's not a javascript library, but MapBox recently released the Directions API for pathfinding within the context of mapping: https://www.mapbox.com/developers/api/directions/ https://www.mapbox.com/developers/api/directions/ So...somewhat relevant to what you're asking.

imaginenore 11y ago
Directions algorithms on real life maps are quite different from what they teach you in CS classes. Just think of the amount of computation to get the best directions between SF and NYC, taking traffic into consideration. I'm pretty sure none of the services actually give you the best solution, but something that's pretty close to it. Full USA map graph contains around 24 million nodes, 58 million edges. Your regular A* just doesn't cut it.
- rcfox 11y ago
  I'm sure you're right, but it seems like traffic would be easy enough to consider by simply increasing specific edges' costs. As for the scale issue: most of these nodes and edges will never change, so it might be possible to calculate a Dijkstra map.
  - imaginenore 11y ago
    The point is, if you add traffic into consideration, you can't have almost anything precalculated.
    - amitp 11y ago
      A* runs faster if you have better path cost estimates. To get the shortest paths, you want an estimate that's as close to the true cost, but not greater than it. You can precalculate to generate good estimates. Traffic makes the costs higher than normal, so those precalculated estimates are still useable (if you raise the costs because of traffic, the estimates continue to be lower than the true cost), and still much better than what you get without precalculation.
- amitp 11y ago
  Better distance estimates and better graphs can push A* to work on larger problems. ALT gives better distance estimates: http://research.microsoft.com/pubs/64511/tr-2004-24.pdf http://research.microsoft.com/pubs/64511/tr-2004-24.pdf (PDF link) (or these slides http://www.cs.princeton.edu/courses/archive/spr09/cos423/Lectures/reach-mit.pdf http://www.cs.princeton.edu/courses/archive/spr09/cos423/Lec... ). Transit nodes do too, I think. Contraction hierarchies and arc flags let you preprocess the graph to give better information to A*. (I've not implemented any of these myself)

nacs 11y ago

You could use pretty much any pathfinding algorithm (A* for example) even if you don't have a grid based graph. In the implementation, you would just need to modify how the algorithm transverses each valid walkable/unwalkable node (how to go from waypoint to waypoint) and possibly how much extra cost each node has (water/mountainous terrain could have increased cost for example) instead of letting it go the usual up/down/left/right and possibly diagonals for grids. If the waypoint based approach isn't ideal for you, then you should look up "navigation mesh" [1] pathing which is a bit trickier to implement but works well when you have a bunch of large empty/walkable areas. [1]: https://en.wikipedia.org/wiki/Navigation_mesh https://en.wikipedia.org/wiki/Navigation_mesh

malkia 11y ago

At previous job some folks used recastnagivation (C/C++) library for what you are looking for - https://github.com/memononen/recastnavigation https://github.com/memononen/recastnavigation And there seems to be "emscripten" version of it (just googled it) - https://github.com/vincent/three-arena/tree/master/recastnavigation https://github.com/vincent/three-arena/tree/master/recastnav... - as part of the "three-arena" project demo here - http://three-arena.com/examples/#simplest.js http://three-arena.com/examples/#simplest.js and the compiled emacsen source here - http://three-arena.com/node_modules/recastjs/lib/recast.js http://three-arena.com/node_modules/recastjs/lib/recast.js also this one: https://github.com/vincent/recast.js https://github.com/vincent/recast.js found by looking here - https://groups.google.com/forum/#!searchin/recastnavigation/emscripten/recastnavigation/1i2xwXudO8c/rOzfG-1U_tMJ https://groups.google.com/forum/#!searchin/recastnavigation/... Also test from there: https://vincent.github.io/recast.js/tests/test.webgl.html https://vincent.github.io/recast.js/tests/test.webgl.html