6 ms·

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/

by 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)

by iamdave 11y ago

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)