This is just a fan letter about the maps-and-directions software that I guess has been in GPS products for years and is now on every Internet-capable phone.
I’m a little too close to most technology, particularly the sort you get over the Net: either I can see the glitches and flaws, or I can see how I could have built it myself, in principle. But not the directions-to-anywhere stuff; to me, it’s pure black magic. I have no idea what the inputs are, what sort of data structures you build with them, or what sort of algorithms you’d use to compute the directions.
The other day we were off to visit a friend in a remote corner of Surrey — one of Vancouver’s big medium-distant suburbs. We also had to stop at this particular mall to pick up a couple of things. The problem was, getting ready to leave the mall parking, I found a big blank space in my mind where the route from the mall to southwest Surrey should be. A glance at the map-book seemed to suggest doubling back about thirty blocks to a through road. About 30 seconds with the Maps app on the NexusOne suggested a non-obvious couple of turns leading to a road I’d never even heard mentioned on the traffic broadcasts that dumped us onto the approaches to the right bridge.
It was at that point that I realized I had no idea how it was done. I still don’t. Which bothers me a little, but I sure enjoy the results.
Comment feed for ongoing:
From: Ryan Cousineau (Mar 03 2010, at 10:45)
I agree that GPS mapping is deep, useful magic. But every so often you do see some amusingly telling cracks.
I've mapped out a telling navigation oddity I encountered using my Tom Tom GPS.
The device plotted a detour that at all points left the car closer to its destination than the shorter and simpler "obvious" route.
Amusingly, I followed along at the time, because I was paying more attention to the map than to the territory.
[link]
From: Justin Watt (Mar 03 2010, at 11:04)
Another simple illustration of said amazement:
http://justinsomnia.org/2005/08/google-maps-i-salute-you/
[link]
From: Michael Weisman (Mar 03 2010, at 11:23)
If you have any interest in this stuff you should check out Demo Camp Geo tomorrow night in Vancouver.
http://democamp10yvr.eventbrite.com/
[link]
From: Jim Duey (Mar 03 2010, at 11:32)
Route planning is a great application of logic programming. Every intersection can be represented as a node in a graph with roads between intersections being the edges. Then the problem becomes finding a route between two nodes in a graph. Various cost functions, like max speed, can be associated with each link in the rode. Very cool stuff.
[link]
From: Steve Loughran (Mar 03 2010, at 11:41)
Right now a lot of routing stuff is based on mapping and guesswork. But once you instrument the vehicles and people's phones, the people themselves start to provide the routing information. Every time your android goes to google maps to get the next direction, they find out how long it took for you to get from your last direction to there.
It becomes a feedback loop: when a route is invalid, you see people backtracking and trying again. And you get the locals providing their routes from their phone's journeys, building up the real routing map.
I would so love to get this data.
[link]
From: David Magda (Mar 03 2010, at 14:22)
Now try imagining how "normal" people view things like the Internet, the iPad, computers in general, etc.. A lot of "magic" out there. :)
Any sufficiently advanced technology is indistinguishable from magic. -- Arthur C. Clarke
[link]
From: Chris (Mar 03 2010, at 15:03)
If it's not a variation on A*, I'll eat my hat. And I've got more of those than I used to have since the treatment started!
[link]
From: Bob Aman (Mar 03 2010, at 16:57)
Even better was when you asked for directions to another continent and it told you to swim as step eight or nine. I think now it just says it can't calculate, which is a shame.
[link]
From: Martin Probst (Mar 04 2010, at 04:28)
I always imagined this was simply Dijkstra's Algorithm with some clever tricks to limit the number of nodes/edges, for example by partitioning the map and simply finding the next highway if your goal is outside the current partition.
[link]