On: PathFinding.js

[imaginenore]

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.

[amitp → imaginenore]

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)

[rcfox → imaginenore]

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 → rcfox]

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

[amitp → imaginenore]

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.