[Roadster] Anyone working on routing / directions?

[Noel Flicken]

Has anyone started on implementing the driving directions component of
Roadster?  If so, i'd like to help.  If not, i'd like to start the
implementation.

Before finding Roadster, i investigated the current state of driving
directions in the open source community.  Currently, i have found two
other open source mapping programs that already implement driving
directions generation.   The directions produced aren't very good, 
probably at least partially due to insuffient data available (such as
one-way streets, road speeds, exit numbers, etc). Still, we may be
able to learn from their implementations to produce a decent set of
directions.

RoadNav - C++
http://roadnav.sourceforge.net/
Uses Dijkstra's algorithm [1] to find the shortest path.  This
algorithm works, but is inefficient for this domain--the algorithm
will search outward in a radius away from the starting point, visiting
nodes upto 2X distance from the end location, where X is the distance
from the start node to end node.

GMap - C#
http://gmap.sourceforge.net/
Uses a naive A-star algorithm [2].  This algorithm is well-suited for
the domain, but GMap's implementation has no estimated cost heuristic
function, so it is effectively the same algorithm as Dijkstra's and
will perform similarly.


Suggestions for Roadster's implemantion:
The A-star algorithm is a simple and powerful algorithm for shortest
path finding.  With the right heuristic function (see [3]), it can
perform amazingly well.  Look at the number of node searched in [4].

I'd be willing to start implementing an A-star algorithm for Roadster
(as soon as i can get the thing to compile (-; ).  Later, we can tweak
the heuristic and distance calculation functions to allow for the
generation of directions based on factors other than time required.

Cheers,
  Noel

Footnotes:
[1] http://www.nist.gov/dads/HTML/dijkstraalgo.html
[2] http://en.wikipedia.org/wiki/A-star_search_algorithm
[3] http://citeseer.ist.psu.edu/goldberg04computing.html
[4] http://citeseer.ist.psu.edu/cachedpage/679638/3