4 ms·

The article has a section on the math used in Google Maps, which points to http://algo2.iti.kit.edu/schultes/hwy/esaHwyHierarchies.pdf http://algo2.iti.kit.edu

• psykotic 14y ago
  Good luck precomputing all those pairwise shortest paths. Storing the table might not be too bad. But standard algorithms like Floyd-Warshall are O(n^3) in the number of vertices. There are faster algorithms based on fast matrix multiplication but the precomputation time would still be prohibitive. Keeping it up to date would be even worse. The construction of a new highway could require updating the shortest paths for an enormous number of pairs. The economic argument would go like this: The revenue generated from your maps business is proportional to the number of queries actually processed, not the total number of conceivable queries. The queries processed is such a tiny subset of the possible queries that you want your computational expenses to track the former, not the latter. With a hierarchical shortest paths algorithm, you can still precompute all pairwise shortest paths at the coarser level. For road navigation you might precompute the shortest path between every pair of interstate highway exits in the USA like this paper is doing. In an open-world game like Skyrim you might precompute the shortest paths between all towns and other major hubs and points of interest. That might not yield truly optimal paths. For game use it's close enough and has the benefit of corresponding to how humans naturally navigate. Sidebar: The old Crash Bandicoot games used precomputed shortest paths in a neat way. Their navigation was based on a triangular mesh, so every triangle had up to three edgewise neighbors. Thus for a navmesh with n triangles, they needed lg(3) n(n-1)/2 <= n(n-1) bits to store the table. For convenience they probably stored this in a redundant form requiring 2n^2 bits = n^2/4 bytes. But with only 64KB of additional memory, this still let them support 512 navmesh triangles per level with lightning-fast path finding.
  • dxbydt 14y ago
    >For road navigation you might precompute the shortest path between every pair of interstate highway exits in the USA like this paper is doing. Oh, so they are populating a lookup table, not for the entire nodeset but just the tuples denoting interstate highways. All I was advocating was a much larger ( and more expensive) lookup table :) btw, you've edited your response like 6 times now...everytime I try to reply there's new info in there!
    • psykotic 14y ago
      > btw, you've edited your response like 6 times now...everytime I try to reply there's new info in there! Sorry! The lack of preview for HN comments is hell for my iterative writing style.
      • dhimes 14y ago
        A lot of us write in an offline text editor and paste the results when we are more-or-less finished (the finish line is an asymptote for people like us!).
        • psykotic 14y ago
          Dijkstra is cursing us from beyond the grave.
      • jacobr 14y ago
        Increase the "delay" in your settings to get a delay until the comment is visible to others.
  • sb 14y ago
    Hm, thanks for the nice remark on the game stuff, I kind of like that. While agree with your primary criticism, I think the principle of locality applies well to this problem. While there are 24 million places (supposedly, never checked that from the paper), I'm positive that most maps queries are served to the areas with higher population density. Therefore, it might make sense to use the look-up table approach for densly populated areas to reduce the search time. (OTOH, the computer scientist in me reminds me that the 7ms might pale in comparison to latency times for mobile phones receiving the map information...)
• azth 14y ago
  ...and use up tons of hardware when you can get by without doing that?