Hacker News Reader

Comment by rcfox | Hacker News Reader

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

At previous job some folks used recastnagivation (C/C++) library for what you are looking for - 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/recastnav... - as part of the "three-arena" project

demo here - http://three-arena.com/examples/#simplest.js

and the compiled emacsen source here - http://three-arena.com/node_modules/recastjs/lib/recast.js

also this one:

https://github.com/vincent/recast.js found by looking here - https://groups.google.com/forum/#!searchin/recastnavigation/...

Also test from there:

https://vincent.github.io/recast.js/tests/test.webgl.html

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

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/

So...somewhat relevant to what you're asking.

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.

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 (PDF link) (or these slides 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)

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.

The point is, if you add traffic into consideration, you can't have almost anything precalculated.

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.

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

Reply on news.ycombinator.com