google-maps - query - google maps url parameters marker




Map Routing, a la Google Maps? (4)

I've always been intrigued by Map Routing, but I've never found any good introductory (or even advanced!) level tutorials on it. Does anybody have any pointers, hints, etc?

Update: I'm primarily looking for pointers as to how a map system is implemented (data structures, algorithms, etc).


A* is actually far closer to production mapping algorithms. It requires quite a bit less exploration compared to Dijikstra's original algorithm.


Barry Brumitt, one of the engineers of Google maps route finding feature, wrote a post on the topic that may be of interest:

The road to better path-finding 11/06/2007 03:47:00 PM


Take a look at the open street map project to see how this sort of thing is being tackled in a truely free software project using only user supplied and licensed data and have a wiki containing stuff you might find interesting.

A few years back the guys involved where pretty easy going and answered lots of questions I had so I see no reason why they still aren't a nice bunch.


Making maps and pathfinding AI

I've worked on a routing application for a while. The most common algorithm for this is to start on both ends (start and finish) and move towards each other, traversing all possible methods of travel. The branches that meet in the middle will be your ideal path.

You can weight things appropriately, like speed limit, by setting checks in the code to only move x distance every time step.

These should do you:

Good graph traversal algorithm

http://www.policyalmanac.org/games/aStarTutorial.htm

http://en.wikipedia.org/wiki/A*_search_algorithm/

Map Routing, a la Google Maps?







gis