tag:blogger.com,1999:blog-5210758134406178854.post2387006779728030136..comments2022-12-05T00:12:31.602-05:00Comments on blog.kdgregory.com: How a GPS Calculates Routeskdgregoryhttp://www.blogger.com/profile/03491264911815834181noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-5210758134406178854.post-29975968230713894492019-10-08T07:21:13.606-04:002019-10-08T07:21:13.606-04:00In the case of A-B versus A-E the choice is arbitr...In the case of A-B versus A-E the choice is arbitrary. If there's a real-world case of two equally-valid routes to the same intermediate point, then one will be picked arbitrarily; probably the first pair in whatever data structure you use to manage nodes.<br /><br />In the real real world, this is extremely unlikely: either one of the streets would give a different heuristic value, or be a tiny bit longer or shorter, and therefore change the overall route.kdgregoryhttps://www.blogger.com/profile/03491264911815834181noreply@blogger.comtag:blogger.com,1999:blog-5210758134406178854.post-52047351606488765112019-08-30T01:06:45.831-04:002019-08-30T01:06:45.831-04:00In the first step, we have two choices: we can go ...In the first step, we have two choices: we can go from A to B or from A to E. As far as the computer is concerned they're both equivalent: there's no existing path and the direct line from each of those points to P is the same length.<br />Question: How does it know the direct line length from B to P or E to P? how and when do u know that value ? does it store distance between a point to all other points in the grid?<br />Thanks for a good explanation for the articleV.M.Praveenhttps://www.blogger.com/profile/16881235611038117478noreply@blogger.comtag:blogger.com,1999:blog-5210758134406178854.post-77868998244988763492016-07-15T06:54:47.309-04:002016-07-15T06:54:47.309-04:00A* and other graph-traversal algorithms require so...A* and other graph-traversal algorithms require some set of connected nodes, along with the cost to move from one node to another; there's no need for actual roads to connect the nodes.<br /><br />So for an all-terrain robot, you might apply an artificial grid of nodes to a map, and then determine the cost based on terrain: smooth rock might be 1, grass 5, sand 10, and water infinity. Once you've done that, A* works.kdgregoryhttps://www.blogger.com/profile/03491264911815834181noreply@blogger.comtag:blogger.com,1999:blog-5210758134406178854.post-34032151700605648912016-07-14T21:20:08.785-04:002016-07-14T21:20:08.785-04:00Is there a way to implement a* with an area of gro...Is there a way to implement a* with an area of ground on a planet with no roads, like how an all-terrain robot would navigate?Matt Ferriehttps://www.blogger.com/profile/17663779042922098671noreply@blogger.comtag:blogger.com,1999:blog-5210758134406178854.post-65865704525346524292016-07-14T08:29:15.198-04:002016-07-14T08:29:15.198-04:00Sorry for the late reply. And the answer is that i...Sorry for the late reply. And the answer is that it really depends on what you're doing. For a rough calculation involving distances of a few miles in the temperate latitudes, it should be fine. Just be aware that, at 40 degrees latitude, one degree north/south is 111 km, while one degree east/west is 85 km. The proportion is the cosine of latitude. Here's a site that will let you explore distances at different latitudes: http://msi.nga.mil/MSISiteContent/StaticFiles/Calculators/degree.htmlkdgregoryhttps://www.blogger.com/profile/03491264911815834181noreply@blogger.comtag:blogger.com,1999:blog-5210758134406178854.post-25302473303286444402016-06-09T22:12:51.503-04:002016-06-09T22:12:51.503-04:00Since the earth is a sphere, we can't use pyth...Since the earth is a sphere, we can't use pythagorean theorem, but for comparing distances to see which one is closer can I just stick with pythagorean theorem. I am a bit worried about doing even simple trig computations in my program and I am trying to make it as short and concise as possible.<br />Thanks!Anonymoushttps://www.blogger.com/profile/13854145975957327091noreply@blogger.comtag:blogger.com,1999:blog-5210758134406178854.post-47079123589061780502015-06-28T09:16:18.309-04:002015-06-28T09:16:18.309-04:00Yes, each point has a latitude and longitude. The ...Yes, each point has a latitude and longitude. The calculation of distance is a little challenging, because degrees of longitude get closer together as you approach the pole. At the equator, one degree of longitude is 69.17 miles (111.32 km). At 40 degrees north/south, it's 53.06 miles (85.39 km). And at the poles, it's 0.<br /><br />The length of a degree of latitude is more-or-less constant over that range (not exactly constant because the earth isn't a perfect sphere). So you can't use a simply pythagorean calculation to find the distance.<br /><br />An accurate distance uses the <a href="https://en.wikipedia.org/wiki/Great-circle_distance" rel="nofollow">great circle distance</a>, but this requires a lot of computation. You can take a shortcut by multiplying 69.17 by the cosine of the latitude, and that works for points that are at similar latitudes. Another shortcut -- and the one I suspect the GPS uses -- is to use a simple table of lengths, and pick the one closest to your location.kdgregoryhttps://www.blogger.com/profile/03491264911815834181noreply@blogger.comtag:blogger.com,1999:blog-5210758134406178854.post-14023328836129280092015-06-18T00:09:45.360-04:002015-06-18T00:09:45.360-04:00Thanks!
Nice simplified explanation that most of u...Thanks!<br />Nice simplified explanation that most of us can understand.<br />One thing you didn't clarify is how it knows the shortest straight line distance. Presumably the nodes have some kind of coordinates like longitude and latitude or something like that it uses.TJPhttps://www.blogger.com/profile/05884181662212058452noreply@blogger.com