[mkgmap-dev] Inter-tile routing failures - not all our fault?

Fri Aug 14 10:01:02 BST 2009

Hi Chris,

> When I get a chance in the next couple of days, I'll have a play around with 
> some of the official Garmin maps and see if they can be made to exhibit the 
> same problem. If so then the limitation is most likely in the routing algorithm 
> in MapSource and/or on the device. If that's the case then we should probably 
> start thinking of it as a 'feature' rather than a bug...

That would be extremely useful.

The bug can easily be reproduced by finding a road on tile A that forks
on one side of a boundary and both of the forkees? cross the boundary
to tile B. You then try and route between the ways on tile B. Sometimes
it works OK and sometimes not. Another example is simply where a road
goes across a tile boundary and then back to the original tile.

I found a great example on the NL map where a road snaked across a
boundary about 4 times and mapsource would route happily from any point
on the road on tile A to any point on tile B but would not route back
to tile A again. It was like this:

  \    |
   1   |
    \  |
     \ |
      \|
       |\
       | \
       |  \
       |   2
       |  /
       | /
       |/
      /|
     / |
    /  |
   3   |
    \  |
     \ |
      \|
       |\
       | \
       |  \
       |   4
       |  /
       | /
       |/
      /|
     / |
    /  |
    5  |

Routing from 1 or 3 or 5 to 2 or 4 was fine but 1 to 3 or 5 failed.

I realise that there are huge gaps in our knowledge of the Garmin data
formats but this strikes me as being more likely to be a problem in the
router rather than the data itself. My thinking here is that as the
crossing points are not broken when considered individually and all of
them can be routed across,  that is strong evidence that there is
nothing wrong with them.

I mean, what are we looking for? a special bit or value that says that
a tile (or way or node) can be routed through as described above? That
would be perverse in the extreme (OK, I know we're dealing with Garmin
here so, I guess, that anything is possible). Also, if we're missing
some vital piece of data, you wouldn't expect it to work at all, but it
does work, say 50% of the time or better.

So, at this time, I can't imagine what we could be doing wrong to
cause this but I can easily imagine how a routing algorithm could have
problems when faced with non-trivial boundary crossings.

Cheers,

Mark