[OSM-talk] Neat routing demo

[Jon Bright]

Hi,

Martijn van Oosterhout wrote:
> Just saw this.
> 
> http://boston.freemap.in/routing.html
> 
> It'd be awesome if something like this could be adapted for OSM....

I have a working routing backend for OSM data, working straight off the 
MySQL DB.  I'm currently in the process of porting it to rails (I 
knocked up the prototype in PHP).  The bad bit: it's not nearly as 
pretty.  The good bit: it will happily plan you a route from London to 
York, using A*.

Interesting side point: the most inefficient thing about the OSM 
database for routing is, at the moment, the fact that a new way can 
start anywhere on some other way.  Instead of going from the start of a 
way and springing to the end of it then looking where to go from there, 
you end up having to look at each segment and looking whether some other 
way starts there.  This won't, I think, go away with 0.5?

To make it clearer what I'm talking about:

o--A-->--A-->--A-->--A-->--A-->--A-->*
                   |
                   B
                   |
                   v

A and B are ways.  If my route has reached o, I can't just jump to *, 
because I'd miss looking at B.

Ideal would be (and I realise that this is recommended, but it's not 
followed much):

                   x
o--A-->--A-->--A-->--C-->--C-->--C-->*
                   |
                   B
                   |
                   v

i.e. that everywhere there's some kind of junction, a new way begins.

The routing algorithm could then jump from o to x, following the two 
resulting routes along ways B and C.  Much quicker.

--
Jon