Graphhopper: Wrong and missing turn instruction

[karussell]

in this situation:

http://graphhopper.com/maps/?point=52.006528%2C4.372382&point=52.006908%2C4.369898

Graphhopper is not showing a 'sharp left turn', possibly because the from and to ways are the same (Poortlandplein, since that's the name of the square)

Here are other examples of missing instructions:

• http://graphhopper.com/maps/?point=49.76661%2C43.648478&point=49.765854%2C43.658381&vehicle=FOOT
• http://graphhopper.com/maps/?point=48.614598%2C8.033752&point=48.61664%2C8.021629&vehicle=bike&elevation=true

Another improvement would be (create another issue?) to use a 10 or 20 meter tolerance to calculate the instructions. E.g. then the 'slight left turn' will be a 'left turn' here

A further improvement is to add a name from the relation if no street name exists. E.g. this route should show 'North Downs Way'

An other simpler idea (instead of junction analysis) would be to use changing OSM way ID to detect when to print instructions

We should attach names of the main road if there is a parallel cycle or foot path without a name.

Question: I noticed that any time there is a fork in the road, the direction given is simply "Continue onto [highway name]". Would it be possible to specify whether to take the right or left side of the fork? (Also this is especially problematic at exits, which have no street name; the direction given is simply "Continue" and one must know that that means "Take the exit".)

[marq24]

Hi,
actually I have spend some time with improving the turn instructions [specially for Roundabouts and for offroad routing (bike, foot)]

I have forked the current master and have created a branch
https://github.com/marq24/graphhopper/tree/turn_instructions

here is the diff...
https://github.com/marq24/graphhopper/compare/turn_instructions

and the link to the commit of all the changes
https://github.com/marq24/graphhopper/commit/cc716aee998d70336c3c7557ee1d3b254bd0b424

What is included:
1)
Counting exits of Roundabout's [so you get the Instruction to enter the roundabout and leave it at Exit #]

2)
Truncation of "continue" Instructions that are not nessecary (cause there are no real alternatives) or you are on the main road

3)
Basic Motorway/Link Instructions to (need to be integrated in the transltion bundle with appropriate messages)

Please note, that the changes requires to turn off CH - since the inspection of the turn alternatives will not be correct when CH is enabled

[martinsauvage]

Hello,
Is it supposed to fix #185?

[marq24]

Yes - you get the instruction at which exit (count) you have to leave the round about [but yu should turn off CH in order to ensure that it's working correctly]

[martinsauvage]

Ok thank you.

I tested your code disabling CH and I see several problems on exit number, sometimes this is good, sometimes not. I guess it depends on roundabout configuration. Did you finish your implementation?

[karussell]

I'm currently trying to make it working with CH too. Will take a bit. In all cases we would need some unit tests.

[karussell]

Additionally I would like to fix #185 before and keep the fix separated from this here.

[martinsauvage]

OK let me know when you need tests, I can spend some time to validate this feature.

[jansoe]

To summarize my recent experience and the previous posts, I think there are several fixes which could improve turn instructions (condisering roundabout instructions are now included):

• if both incoming and outgoing edges have no streetname, instructions are completly ommitted (e.g. https://graphhopper.com/maps/?point=48.614598%2C8.033752&point=48.61664%2C8.021629&vehicle=bike&elevation=true)
• if you first have to cross a link between the two opposing lanes before turning left, then entering the link dominates the left turn (e.g. https://graphhopper.com/maps/?point=52.508392%2C13.326287&point=52.509456%2C13.325692&layer=Lyrk)
• there are no instructions for u-turns (e.g. https://graphhopper.com/maps/?point=52.510178%2C13.323063&point=52.510573%2C13.324115&layer=Lyrk)
• there are no instructions for motorway links (e.g. https://graphhopper.com/maps/?point=28.956888%2C-13.598853&point=28.95516%2C-13.607619&layer=Lyrk)
• if a street splits there is no intruction, which side to use
  (https://graphhopper.com/maps/?point=53.618694%2C11.404297&point=53.618983%2C11.407585&layer=Lyrk)
• there are possibly unecessary instructions for example if street name is only shortly interupted, but no turning alternatives (https://graphhopper.com/maps/?point=52.512767%2C13.325193&point=52.513263%2C13.33295&layer=Lyrk)

I think many points can be addressed together by some kind of junctionAnalyzer (once #116 is completed). (Even motorway links, although they could be provided as tag in the encoder)
Unfortunately such a junctionAnalyzer could signigicantly increase computation time. It might help to take taxicap geometry (http://www.freesteel.co.uk/wpblog/2009/06/05/encoding-2d-angles-without-trigonometry/) but I'm not sure if it really outperforms the current atan implementation.
More effective would be some kind of pregenerated HashSet which tells at which node the junctionAnalyzer has to startup (e.g. at juctions where >=3 edges have the same name).

[karussell]

Thanks for the analysis! Probably the angle computation won't be the bottleneck (as it is already nearly just a table lookup). Instead I fear that the traversal of all nodes in the path is the most expensive. The proposed pre-generated datastructure could improve this but maybe we just try to implement this at some point and see how it performs. Additionally if we separate the route calculation and the instruction calculation a bit better, then applications can fetch the instructions later e.g. only on user demand.

[don-philipe]

I've done some simple changes to the Path class to have some more turn instructions.
As you can see here the decision of whether or not to add a new Instruction is based on the turn instruction. Now only the continue instruction on a road whose name an annotations don't change is omitted.

[boldtrn]

I've done some simple changes to the Path class to have some more turn instructions.

Is there a reason why we have not added something like this yet? I could create a PR for that, if we were looking for something like that.

[karussell]

Looks like I've overlooked the comment from @don-philipe. Having this as PR would be indeed nice!

[devemux86]

Do we need the continue instruction after start?
Besides the 1st instruction which can be continue (line now), most routers tend to avoid continue in their algorithms.

[don-philipe]

A continue instruction is of interest for e.g. (indoor-) routing for blind persons:

• Walk up to connection door.
• Continue and follow the corridor ...

[devemux86]

@don-philipe you are right.
Though an algorithm cannot serve perfectly all cases simultaneously. Probably an option like with encoders could be useful?

[don-philipe]

Probably an option like with encoders could be useful?

Indeed, I would appreciate that.

[boldtrn]

@don-philipe nice to hear back from you :). Since this was your change, do you want to add it as PR to GraphHopper?

Probably an option like with encoders could be useful?

Yes, that is a really nice idea. We could add a reduceContinueInstruction flag to the AbstractFlagEncoder that is TRUE by default and may be overwritten to FALSE in any extending class.

Also I think it would be a good idea, if we want to ignore an Instruction, to set it to an own type instead of Continue, e.G. introduce Instruction.IGNORE.

[don-philipe]

Since this was your change, do you want to add it as PR to GraphHopper?

Yeah, can do it within the next days.

[boldtrn]

Yeah, can do it within the next days.

Nice, thanks for contributing :+1:

[karussell]

Yes, that is a really nice idea. We could add a
reduceContinueInstruction flag to the AbstractFlagEncoder that is TRUE

Just as info: I plan to use mainly one encoder in the future and move all profile dependent logic into the weighting (or a renamed similar class) where also these settings would be placed. See also #730 where such a "one encoder" solution sketch is presented

[boldtrn]

where also these settings would be placed

Thanks for the info. But for now we should place it in the encoder, right?

[karussell]

But for now we should place it in the encoder, right?

For now I just would delay this and try to hurry up the data encoder thing, which we need in too many places already. I would not completely replace the existing approach with one encoder for one vehicle, instead I plan to introduce this "data encoder" which will be available in all other encoders, so that they also do not need to store roundabout or tunnel bits. And potentially migrate in later versions to a "one encoder"-approach

[karussell]

BTW: I meant delay with this continue thing, not the improvement from @don-philipe ... would highly appreciate a PR which improves instructions with little effort.

[boldtrn]

Continuing discussion of #895 here. The question is which class should orchestrate the instruction generation.

Why would you put that in the weighting?
Because at some point we have only one (data)encoder used from multiple Weightings. And as a Weighting can also block roads via infinity, or being used for car or foot we need this difference there or in a new InstructionCreator or renaming Weighting etc

I actually thought about this a bit different, I thought we would pass some sort of "TransportationMode" to the Weighting. The weighting would query the DataFlagEncoder if Edge E is accessible for TransportationMode T. I thought the same would apply for the instruction creation. The InstructionCreator would query the DataFlagEncoder for the instruction mode for a certain "TransportationMode". But this actually might be a bit too much responsibility for the DataFlagEncoder as the responsibility of the DataFlagEncoder is en-/decoding values in the graph. Maybe we should put the logic into the InstructionCreator?

[karussell]

Maybe we should put the logic into the InstructionCreator?

Yes, probably. Have not really thought about it. I only know that it cannot be encoder dependent :)

[boldtrn]

Ok, I am currently thinking about this issue once again.

So I think if possible we should only create a turn instruction if there is actually a turn necessary and not if we follow the street or its the only way to turn anyway.

So I think a couple of things have already been mentioned here or in other issues. For me this would mean:

• Remove Continue instructions when not absolutely necessary
  
  
  
  • I think they are only necessary if the main road is turning to one side, but we want to go straight.
  
  
• What about the start instruction? Should we create a special sign for that and drop the continue for that instead?
• Analyzing the possible turns and create turn instructions according to these results. So I think that way we could get rid of a lot of slight turns. There are curves which are seen as slight turns.
• With the Dataflagencoder we can save the highway type, this would allow us to create instructions for *_link roads, especially enter highway or leave highway (requires new sign).

Any more thoughts about that?

Where should we put that? Should we put that in the Path class? Maybe a TurnInstructionGenerator? This class could implement the EdgeVisitor Interface of the Path class and therefore we could make the Path class smaller. Or should we try to analyze these things on import and save them in the graph? Maybe as InstructionAnnotation, but this could then only be used for one encoder?

[devemux86]

I think they are only necessary if the main road is turning to one side, but we want to go straight.

Continue instructions could be used on start or immediately after a via point too.

I think we shouldn't tie the process to graph creation, but while calculating a route so being flexible as each encoder could have different needs?

[karussell]

Thanks for this. And I wouldn't drop the Continue instruction for now as this can still be partially useful.

Indeed, we need the highway type to decide if the road is followed. So either we could (a) make this turn calculation more or less encoder independent and enable better instructions only if the DataFlagEncoder is there or (b) we refer inside every encoder to one DataFlagEncoder, which is kind of ugly but would integrate relative smoothly (have done this for a project already) or (c) implement all the vehicles with the DataFlagEncoder which is probably too complex undertaking for now. My preference is (a) and then replicate single vehicle behaviour via (c) later.

I think we shouldn't tie the process to graph creation, but while calculating a route so being flexible as each encoder could have different needs?

I would for now put this indeed just in the route calculation process and cover everything with unit tests. Still I think we need to have it in the graph (somehow and at some later point) because then we can e.g. easily avoid left turns and this requires a very fast access of junction properties.

this would allow us to create instructions for *_link roads, especially enter highway or leave highway (requires new sign).

Here we need to publish a less strict client i.e. a JS & Java client that do not fail if they don't know the sign

[boldtrn]

Just found a roundabout instruction bug. See this route. It say: at roundabout take exit 2, but it should be exit 1. This is probably created by this track, that is probably seen as the 1st exit. A bit ugly, not sure how to fix this...

[karussell]

Have added it to #319

[karussell]

This is mostly fixed. We will open separate issues if there are more specific cases.