Inter-tile routing failures - not all our fault?
There is a particular failure of inter-tile routing that we have seen quite often which is that it fails to find a route when the source and destination are in the same tile and the only (sensible) route is via another tile. (If a sub-optimal route that only uses the source tile is available that will get used.) Well, I naturally assumed that this was caused by mkgmap doing something wrong but I'm not so sure now because I have been looking at the free nz mapset that is generated using cgpsmapper and that exhibits exactly the same behaviour as our maps do in this respect. So, either the bug is in mapsource (and all Garmin GPS units?) or mkgmap and cgpsmapper are both getting it wrong in the same way. Cheers, Mark
Mark Burton schreef:
There is a particular failure of inter-tile routing that we have seen quite often which is that it fails to find a route when the source and destination are in the same tile and the only (sensible) route is via another tile. (If a sub-optimal route that only uses the source tile is available that will get used.)
Maybe we should investigate one such problem really thoroughly? I've also been thinking that a map with all of these problems would be a good idea, but I don't know if that would be feasible. Pro: have all problems in one, easily compilable, easily editable map; this map being small and exchangeable (by e-mail or svn). Con: the need to maintain this map; in fact, many of the corner cases will only be transferrable to this testmap once you know what to transfer, which is probably 90% of the investigation. What do you think?
Well, I naturally assumed that this was caused by mkgmap doing something wrong but I'm not so sure now because I have been looking at the free nz mapset that is generated using cgpsmapper and that exhibits exactly the same behaviour as our maps do in this respect.
They're built on the same reverse engineered information, aren't they?
So, either the bug is in mapsource (and all Garmin GPS units?) or mkgmap and cgpsmapper are both getting it wrong in the same way.
As said before (in the first A, B, C routing problem), my Garmin Nuvi will take routes that Mapsource won't. Also, the first problem had to do with three tiles, MapSource unwilling to route from tile A to tile C through tile B on a specific road. So we're not sure if it's Mapsource, mkgmap & cpsmapper, or some subtle interaction between all three. V. -- Durgerdamstraat 29, 1507 JL Zaandam; telefoon 075-7074579
MB> There is a particular failure of inter-tile routing that we have MB> seen quite often which is that it fails to find a route when the MB> source and destination are in the same tile and the only (sensible) MB> route is via another tile. (If a sub-optimal route that only uses MB> the source tile is available that will get used.) MB> MB> Well, I naturally assumed that this was caused by mkgmap doing MB> something wrong but I'm not so sure now because I have been looking MB> at the free nz mapset that is generated using cgpsmapper and that MB> exhibits exactly the same behaviour as our maps do in this respect. MB> MB> So, either the bug is in mapsource (and all Garmin GPS units?) or MB> mkgmap and cgpsmapper are both getting it wrong in the same way. 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... Chris
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
Hi Mark, MB> The bug can easily be reproduced by finding a road on tile A that MB> forks on one side of a boundary and both of the forkees? cross the MB> boundary to tile B. You then try and route between the ways on tile MB> B. Sometimes it works OK and sometimes not. Another example is MB> simply where a road goes across a tile boundary and then back to the MB> original tile. Thanks for the clear example, I'll see what I can find when I get home. One thing I have noticed, especially with the more recent Garmin maps, is that they appear to have quite carefully handcrafted the tile boundaries such that it might be quite hard to find an example like this - possibly even because this problem is exactly what they're trying to circumvent! MB> So, at this time, I can't imagine what we could be doing wrong to MB> cause this but I can easily imagine how a routing algorithm could MB> have problems when faced with non-trivial boundary crossings. I tend to agree which is why I hope looking at the Garmin maps will shed some more light on the situation. However I can still imagine scenarios that would break the routing intermittently where the map might be at fault rather than the algorithm (or it could be a combination of the two). It could be a subtle alignment issue (similar to the tile problem I recently fixed(?) in the splitter). For example imagine trying to route from point 'a' in tile A to point 'c' in tile A, where passing through point 'b' in tile B should in theory be the optimal route. If there was a problem calculating how far tile B is offset from tile A, the routing algorithm might decide it's shorter to take a longer route that stays on tile A because it calculates that point 'b' is a lot further away than it really is. If on the other hand you were trying to get to somewhere on tile B anyway, that extra distance has to be covered regardless, so the routing would suddenly appear to work. Hope that example makes sense. Of course I have no idea how valid that particular theory is given I currently still know nothing about the img file format or how the distance and routing calculations are performed. Chris
Using a recent GB tiled map on my eTrex, I have found that it performs differently (better?) to mapsource with regard to the problem of not routing across a boundary and back to the source tile. An example route I tried used a road that snaked across a boundary. Mapsource failed miserably in the manner previously described. The eTrex faired better in that it could manage to route across the boundary and back again for at least one crossing pair but when I tried to cross and back again for the second time, it took a really long time to calculate the route and the result was very silly. On another example route, that crossed the boundary to a fork and then crossed back to the original tile, mapsource failed but the eTrex was quite happy. So I remain far from convinced that the problem is due to buggy map data generated by mkgmap. However, it may be that we have to generate map data that is in some way "more sympathetic" to the needs of the Garmin routing engines. Mark
did some experiments in Mapsource and Garmin maps don't suffer from this problem.found a place where the direction of the route defines which way is chosen. makes perfect sense because right turns are faster and easier than left turns. Mapsource will even choose the longer way across the tile boundary to avoid the left turns. Is there anything I can check for? map is not protected and should be possible to load in Gpsmapedit. On Fri, Aug 14, 2009 at 3:34 AM, Mark Burton <markb@ordern.com> wrote:
Using a recent GB tiled map on my eTrex, I have found that it performs differently (better?) to mapsource with regard to the problem of not routing across a boundary and back to the source tile.
An example route I tried used a road that snaked across a boundary. Mapsource failed miserably in the manner previously described. The eTrex faired better in that it could manage to route across the boundary and back again for at least one crossing pair but when I tried to cross and back again for the second time, it took a really long time to calculate the route and the result was very silly.
On another example route, that crossed the boundary to a fork and then crossed back to the original tile, mapsource failed but the eTrex was quite happy.
So I remain far from convinced that the problem is due to buggy map data generated by mkgmap. However, it may be that we have to generate map data that is in some way "more sympathetic" to the needs of the Garmin routing engines.
Mark
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Apollinaris Schoell wrote:
did some experiments in Mapsource and Garmin maps don't suffer from this problem.found a place where the direction of the route defines which way is chosen. makes perfect sense because right turns are faster and easier than left turns. Mapsource will even choose the longer way across the tile boundary to avoid the left turns.
Is there anything I can check for? map is not protected and should be possible to load in Gpsmapedit.
I recall reading in the cgpsmappers manual that routable preview maps are required for "proper" inter map routing in mapsource. Nether cgpsmapper nor mkgmap generate routable preview maps (it should be possible to try this manually?), but a Garmin compiled map may be different. As the preview map is not uploaded to the GPSr, the handling of inter-map routing must be different between the GPSr and mapsource. Garvan
Sorry to say I too have tried to find a problem with the Garmin maps and failed. No matter what combination of tile crossings, it always seems to do the right thing. I probably tried 20-30 combinations of routes across various tile borders. Is that a big enough sample size to see the problem or shall I keep trying? I've attached one example where everything looks good despite multiple crossings. Chris AS> did some experiments in Mapsource and Garmin maps don't suffer from AS> this problem. AS> AS> found a place where the direction of the route defines which way is AS> chosen. makes perfect sense because right turns are faster and AS> easier than left turns. AS> AS> Mapsource will even choose the longer way across the tile boundary AS> to avoid the left turns. AS> AS> Is there anything I can check for? map is not protected and should AS> be possible to load in Gpsmapedit. AS>
Hi Chris,
Sorry to say I too have tried to find a problem with the Garmin maps and failed. No matter what combination of tile crossings, it always seems to do the right thing. I probably tried 20-30 combinations of routes across various tile borders. Is that a big enough sample size to see the problem or shall I keep trying?
Is that using mapsource and if so, what version is that?
I've attached one example where everything looks good despite multiple crossings.
The picture was corrupted, I could not see it. Cheers, Mark
Hey Mark, MB> Is that using mapsource and if so, what version is that? Yes MapSource, v6.15.6 MB> The picture was corrupted, I could not see it. Damn, probably something to do with this NNTP client of mine :( Try here: http://redyeti.net/routing.png Chris
Hi Chris,
Sorry to say I too have tried to find a problem with the Garmin maps and failed. No matter what combination of tile crossings, it always seems to do the right thing. I probably tried 20-30 combinations of routes across various tile borders. Is that a big enough sample size to see the problem or shall I keep trying?
No, along with AS's report I think that it's fairly conclusive that the Garmin maps don't suffer from this problem. So either they are providing extra info, or the info we are providing (and cgpsmapper too) is duff in some way. I haven't the faintest clue what could be the issue here so until we get some hint as to what the problem could be, I'm ignoring it. I simply don't have spare time to dream up possible reasons why this problem exists. Cheers, Mark
MB> I haven't the faintest clue what could be the issue here so until we MB> get some hint as to what the problem could be, I'm ignoring it. MB> I simply don't have spare time to dream up possible reasons why MB> this problem exists. Can't say I blame you, doesn't sound like an easy one to get to the bottom of. Thanks for your efforts so far. I'm sure the nature of the problem will become clearer eventually anyway as we get a better understanding of how everything hangs together. Chris
participants (5)
-
Apollinaris Schoell -
Chris Miller -
Garvan & maew -
Mark Burton -
Valentijn Sessink