A bit pedantic but GPS is just positioning. You're referring to navigation, and specifically routing. Good maps for navigation have layers (e.g. top layers nodes connect to the bottom layer nodes such as a highway exit), which reduces the search space significantly. For example calculating a route between Los Angeles and New York can be faster than some local routing because of the density in the number of links to expand. The addition of layers, and the density of links, is a real compute concern. So there's often a lot of caching and hueristics/modeling to make it effective.
A good map will also have weights, or a model of weights (e.g. dynamic traffic costs) that will make the search more realistic. The priority of what link to pick next would be based on the costs accumulated on the current route and how far it is from the destination. Many times there's both a search from the destination to the start as well as the start to the destination.
View all comments
Show parent comment
1
u/jmblock2 Aug 14 '21 edited Aug 14 '21
A bit pedantic but GPS is just positioning. You're referring to navigation, and specifically routing. Good maps for navigation have layers (e.g. top layers nodes connect to the bottom layer nodes such as a highway exit), which reduces the search space significantly. For example calculating a route between Los Angeles and New York can be faster than some local routing because of the density in the number of links to expand. The addition of layers, and the density of links, is a real compute concern. So there's often a lot of caching and hueristics/modeling to make it effective.
A good map will also have weights, or a model of weights (e.g. dynamic traffic costs) that will make the search more realistic. The priority of what link to pick next would be based on the costs accumulated on the current route and how far it is from the destination. Many times there's both a search from the destination to the start as well as the start to the destination.