BRouter with navigatin hints. Tracking script included - Version 0.5

[gel...@gmail.com]

Hi,
I'm using BRouter with QlandkarteGT to plan hiking routes. I like to have navigation hints when I'm on my way, but the public routing server generate navigation hints being next to useless for hiking.
I added navigation functionality to BRouter modified QlandkarteGT slightliy to use the extra data now coming from Brouter.

I faced a real challenge when digging into the code of BRouter and that had nothing to do with the complexity of the algorithms :-). Due to my problems with the code I decided to couple Brouter and the navigation processing as loosely as possible. I wanted to use and modify Brouter as little as possible.

Being mostly independent from BRouter is good for reusing the code it in another context but not for the overall performance.
The performance is okay in a single instance environment. I do not recommend using it for running a heavily used public routing server.

The code is only tested in a BRouter-Server context. I did not test it in any other way.
Like parts of BRouter the actual navigation hint processing is moved to a script.
For scripting the SISC Scheme interpreter in included. This should give all the power to scripting you could hope for.

In the current version a very simple hiking navigation script is included.

The main purpose of this code is working with my modified QLandkarteGT installation giving some navigation hits.

I did not bother modifying the maven configuration. I use Eclipse build in functionality for building the code. So, please try to live with that and do not throw dung at me for not updating the proper build environment.

I actually modified these Brouter-Source-Files only slightly:
brouter-core/ btools.router.OsmTrack
brouter-core/ btools.router.RoutingEngine
brouter-server/ btools.router.RouteServer

I added 4 classes in:
brouter-core/ btools.router.navi.

All the rest of the code is in the separate project navigator.

Attached you will find the source as well as the compiled version.

Have fun,
Ralf

PS: I'm here the first time and just realized not to be able to attach anything.
Here is the link: http://www.datafilehost.com/d/dca5097e

[abre...@googlemail.com]

Hi Ralf,

Am Sonntag, 21. Juni 2015 20:00:32 UTC+2 schrieb Ralf:
> I added navigation functionality to BRouter modified QlandkarteGT slightliy to use the extra data now coming from Brouter.

interesting.

regarding this script-based approach for voice hints and the way to carry them in a gpx I will have a deeper look.

As for the way you implemented the access to the routing graph: Note that BRouter is doing one or two routing passes to find the track, and an addional, fast final pass, "guided" by the aleady known result, to add detail information to this track. In RoutingEngine.java, this final path is identified by "guideTrack != null".

Currently, you collect all visited nodes from all passes in a hash-set to get a copy of the relavant part of the routing graph. From my understanding, it should be sufficient to collect them only from the final path - that should completely eliminate the performance-impact you report, because you collect much less nodes. Just move the call to "addViditedNode" 4 lines down.

> I faced a real challenge when digging into the code of BRouter and that had nothing to do with the complexity of the algorithms :-).

On your code-quality remarks: true that this is not something to win a beauty contest - too much complexity added and not enough refactoring done, that leads to a state where the code is hard to understand. This is espacially true for the "core" package. Some others are in a better shape, especially the pre-processor ("mapcreator"), that has undergone one iteration of refactoring, or the "util" package.

But there's also the "clash of cultures": there are people feeling really bad when seeing a foreign identention style, public members or references to non-interfaces. This is partly religious and the correlation to the real structual or technological issues not always obvious. Other than "equal-but-not-hashcode" used in a HashSet can drive you crazy :-) .

[gel...@gmail.com]

> Currently, you collect all visited nodes from all passes in a hash-set to get a copy of the relavant part of the routing graph. From my understanding, it should be sufficient to collect them only from the final path - that should completely eliminate the performance-impact you report, because you collect much less nodes. Just move the call to "addViditedNode" 4 lines down.

Thank you for the hint. I agree, collecting the nodes from the final path should suffice.

Regarding the potential performance issues. The scheme interpreter is initialized for each navigation processing from start. This could take >100 ms or so. I'm quite sure that could be improved, but did not bother for my purpose.

[Zossebart]

On Monday, June 22, 2015 at 6:47:34 PM UTC+2, abre...@googlemail.com wrote:

Hi Ralf,

Am Sonntag, 21. Juni 2015 20:00:32 UTC+2 schrieb Ralf:
> I added navigation functionality to BRouter modified QlandkarteGT slightliy to use the extra data now coming from Brouter.

interesting.

regarding this script-based approach for voice hints and the way to carry them in a gpx I will have a deeper look.

Interesting indeed! @Arndt: Did you have time yet to look into this? Is this a server-solution only or would it be possible to include it in the android app as well?
 
I think you are also aware, that at least some Locus users (including me ;-) ) would love to have navigation hints support in Brouter. There is a discussion about it in the Locus forum, but nobody has a clue how to transfer the hints to the navigation app (via gpx?). Maybe Ralf's implementation could help to shed some light on this?

regards,
zossebart
 

[gel...@gmail.com]

> I think you are also aware, that at least some Locus users (including me ;-) ) would love to have navigation hints support in Brouter. There is a discussion about it in the Locus forum, but nobody has a clue how to transfer the hints to the navigation app (via gpx?). Maybe Ralf's implementation could help to shed some light on this?
>
> regards,
> zossebart
>  

Zossebart,
I can see no technical restriction why the code should not work in an app anvironment in principle. I did not test it yet and I doubt that it will just run out of the box. Most likely there is a necessity to enhance/modify the current interface, but not the core functionality.
In regard locus:
It depends on how locus expects the handover of navigation hints. The current implementation within Brouter writes the collected navigation hints as way points into the gpx stream. This part of the code is extremely simple and only a few lines long. If another transformation to fit the needs of locus is required... well this should be an easy job.

Regards,
Ralf

[Zossebart]

On Thursday, July 9, 2015 at 12:02:06 PM UTC+2, gel...@gmail.com wrote:

> I think you are also aware, that at least some Locus users (including me ;-) ) would love to have navigation hints support in Brouter. There is a discussion about it in the Locus forum, but nobody has a clue how to transfer the hints to the navigation app (via gpx?). Maybe Ralf's implementation could help to shed some light on this?
>
> regards,
> zossebart
>  
Zossebart,
I can see no technical restriction why the code should not work in an app anvironment in principle. I did not test it yet and I doubt that it will just run out of the box. Most likely there is a necessity to enhance/modify the current interface, but not the core functionality.

Sounds good!
 

In regard locus:
It depends on how locus expects the handover of navigation hints. The current implementation within Brouter writes the collected navigation hints as way points into the gpx stream. This part of the code is extremely simple and only a few lines long.

Ok. Is this way of storing the hints provided by the standard gpx format, or do you extend the gpx format with your "way points"? Sorry, I don't have experience with the gpx format :-(
However, there should not be an app-specific interface, because Locus is not the only app which can work with Brouter.
 

If another transformation to fit the needs of locus is required... well this should be an easy job.

I don't think this would be necessary, the format should use a generic standard. But until now, we were not able to find such a generic standard (maybe only because of the lack of knowledge). Arndt asked the developer of Locus some time ago about the interface used with the other routing options supported by Locus (MapQuest, Yours, OSRM), but he said they all use different approaches and there was no standard way of doing it.
I think it would be no problem to convince the author of Locus to extend the gpx import with the functionality, if there should be something missing in the current implementation.
Would it be possible for you to export a sample gpx file generated by your implementation and make it available for download? Then I would try to import it into Locus and look if it is "navigatable" out of the box...
@Arndt: is the current internal format of transferring the calculated route to the navigation app similar to the gpx format, or is it something entirely different? If it is similar, maybe it would be easy to extend it with the generated way points?
 
Regards,
zossebart

[gel...@gmail.com]

> Would it be possible for you to export a sample gpx file generated by your implementation and make it available for download? Then I would try to import it into Locus and look if it is "navigatable" out of the box...
> @Arndt: is the current internal format of transferring the calculated route to the navigation app similar to the gpx format, or is it something entirely different? If it is similar, maybe it would be easy to extend it with the generated way points?

The gpx format defines in essence a way to disciple positions (waypoints) (POI and such) position defining a track and positions defining a route.
Each of these positions can hold the same meta data, such as geo position, name, comment, type, description, time and such.
There is no defined attribute to place navigation hints (let me know if this is not correct). Therefore systems either use a proprietary extension or misuse one of the existing attributes to store and evaluate navigation hints.
To pass navigation hints to QLandkateGT I added waypoins and placed the navigation hint in the name attribute. I used the comment attribute to store the index of the related track step for this navigation hint. I added a few lines of code to the QLandkarteGT to use this information for its internal processing.
I'm using OruxMaps for hiking and OruxMaps has the capability to read the names of waypoints. With an additional little program I convert the QLandkarteGT gpx export, holding “my” navigation hints as positions defining a route to just plain waypoints.
If the navigation hints are just waypoints and the hint is the name of that waypoint OruxMaps is happy, and so am I :)

You see, all depends on how locus expects to get navigation hints. Providing them within the gpx-file is no thing. If the data exchange between BRouter and Lucos is not gpx but another format, things might be different.

This is an example of my export [The navigation hints are in German :-)]
<?xml version="1.0" encoding="UTF-8"?>
<!-- track-length = 847 filtered ascend = 0 plain-ascend = -39 cost=4649 -->
<!-- (alt-index 0: track-length = 847 filtered ascend = 0 plain-ascend = -39 cost=3965 ) -->
<gpx
xmlns="http://www.topografix.com/GPX/1/1"
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://www.topografix.com/GPX/1/1 http://www.topografix.com/GPX/1/1/gpx.xsd"
creator="BRouter-1.2" version="1.1">
<wpt lon="8.891369" lat="49.765308"> <name>Halb rechts</name><cmt>4</cmt></wpt>
<wpt lon="8.890701" lat="49.766144"> <name>Gradeaus</name><cmt>7</cmt></wpt>
<wpt lon="8.887579" lat="49.769395"> <name>Scharf rechts</name><cmt>13</cmt></wpt>
<wpt lon="8.888839" lat="49.769663"> <name>Halb rechts</name><cmt>14</cmt></wpt>
<trk>
<name>brouter_trekking_1</name>
<trkseg>
<trkpt lon="8.892028" lat="49.765331"><ele>237.25</ele></trkpt>
<trkpt lon="8.891959" lat="49.765358"><ele>237.25</ele></trkpt>
<trkpt lon="8.891853" lat="49.765363"><ele>236.75</ele></trkpt>
<trkpt lon="8.891640" lat="49.765308"><ele>236.0</ele></trkpt>
<trkpt lon="8.891369" lat="49.765308"><ele>235.5</ele></trkpt>
<trkpt lon="8.891202" lat="49.765536"><ele>235.25</ele></trkpt>
<trkpt lon="8.890860" lat="49.765970"><ele>231.75</ele></trkpt>
<trkpt lon="8.890701" lat="49.766144"><ele>229.0</ele></trkpt>
<trkpt lon="8.890219" lat="49.766818"><ele>222.0</ele></trkpt>
<trkpt lon="8.889796" lat="49.767437"><ele>220.5</ele></trkpt>
<trkpt lon="8.889211" lat="49.768224"><ele>218.0</ele></trkpt>
<trkpt lon="8.888490" lat="49.768783"><ele>216.0</ele></trkpt>
<trkpt lon="8.887626" lat="49.769361"><ele>214.5</ele></trkpt>
<trkpt lon="8.887579" lat="49.769395"><ele>214.5</ele></trkpt>
<trkpt lon="8.888839" lat="49.769663"><ele>213.0</ele></trkpt>
<trkpt lon="8.889290" lat="49.769355"><ele>213.5</ele></trkpt>
<trkpt lon="8.890449" lat="49.769785"><ele>203.75</ele></trkpt>
<trkpt lon="8.890581" lat="49.769838"><ele>198.25</ele></trkpt>
</trkseg>
</trk>
</gpx>

[Zossebart]

On Thursday, July 9, 2015 at 2:45:02 PM UTC+2, gel...@gmail.com wrote:

The gpx format defines in essence a way to disciple positions (waypoints) (POI and such) position defining a track and positions defining a route.
Each of these positions can hold the same meta data, such as geo position, name, comment, type, description, time and such.
There is no defined attribute to place navigation hints (let me know if this is not correct). Therefore systems either use a proprietary extension or misuse one of the existing attributes to store and evaluate navigation hints.

Thanks for the explanation. Too bad that there seems to be no standard way to do it in gpx, but I think the format was never meant to have such a feature. Although the format is extendable, there seems to be no commonly aggreed 'standard' for a navigation extension (yet?).
 

To pass navigation hints to QLandkateGT I added waypoins and placed the navigation hint in the name attribute. I used the comment attribute to store the index of the related track step for this navigation hint. I added a few lines of code to the QLandkarteGT to use this information for its internal processing.
I'm using OruxMaps for hiking and OruxMaps has the capability to read the names of waypoints. With an additional little program I convert the QLandkarteGT gpx export, holding “my” navigation hints as positions defining a route to just plain waypoints.
If the navigation hints are just waypoints and the hint is the name of that waypoint OruxMaps is happy, and so am I :)

Thanks for sharing your example! I loaded it with Locus, I can see the waypoints (including their names with the hints), but it is not possible to use them for navigation (which I almost expected). 

You see, all depends on how locus expects to get navigation hints. Providing them within the gpx-file is no thing. If the data exchange between BRouter and Lucos is not gpx but another format, things might be different.

I think we should wait for Arndt to answer this, but I can't imagine that the internal format is gpx, because it has lots of overhead.

Regards,
zossebart

btw: I'm german too, so no problem with the german navigation hints ;-)

 

[abre...@googlemail.com]

Am Freitag, 10. Juli 2015 14:02:28 UTC+2 schrieb Zossebart:

I think we should wait for Arndt to answer this, but I can't imagine that the internal format is gpx, because it has lots of overhead.

It is GPX. Here's the aidl-definition of the interface that Locus uses:

http://brouter.de/brouter/IBRouterService.aidl

OsmAnd still uses KML, but for just historical reasons. Meanwhile there's also GeoJSON (added by Norbert as a low-overhead format for BRouter-Web), but that's not yet supported by the aidl-interface.

I'm following the discussion with great interest, but, to be fair, I'm not going to implement into the Android app some quick-hack that's Locus-Only, or german-only, and I'm somewhat sceptical about adding a third-party scripting library to the android app. This Android App is all about memory queezing and keeping it slim, so beeing conservative on technologies is the only way to avoid regressions.

However, if the requirements, the interfaces and the algorithm's are clear, I'm sure that technolgie will not be a problem.

[gel...@gmail.com]

> It is GPX. Here's the aidl-definition of the interface that Locus uses:
>
> http://brouter.de/brouter/IBRouterService.aidl

Hmm, I did not recognize any parameter being able to transport navigation hints.

> I'm following the discussion with great interest, but, to be fair, I'm not going to implement into the Android app some quick-hack that's Locus-Only,...

Sure thing. It might be a BRouter specific extension that by “chance” is very close to the format some of the common apps use.

...or german-only, …
The implementation is language independent. It example is German, just because my example script has German hints. BRouter is not only for bikes just because the example profile seems to focus on biking. Adding or modifying the script could result in much more sophisticated navigation hints and any language you would like. The script is located in the BRouter profile dir.

...and I'm somewhat sceptical about adding a third-party scripting library to the android app. This Android App is all about memory queezing and keeping it slim, so beeing conservative on technologies is the only way to avoid regressions.

Fair, I did not check the memory footprint and it might be okay or might not be a good idea to add it to a standard router. A configurable extension could be a solution, so people could choose.

> However, if the requirements, the interfaces and the algorithm's are clear, I'm sure that technolgie will not be a problem.

Agreed.

[Zossebart]

On Sunday, July 12, 2015 at 7:37:02 PM UTC+2, abre...@googlemail.com wrote:

Am Freitag, 10. Juli 2015 14:02:28 UTC+2 schrieb Zossebart:

I think we should wait for Arndt to answer this, but I can't imagine that the internal format is gpx, because it has lots of overhead.

It is GPX. Here's the aidl-definition of the interface that Locus uses:

http://brouter.de/brouter/IBRouterService.aidl

Thanks for pointing this out.
 

OsmAnd still uses KML, but for just historical reasons. Meanwhile there's also GeoJSON (added by Norbert as a low-overhead format for BRouter-Web), but that's not yet supported by the aidl-interface.

I'm following the discussion with great interest, but, to be fair, I'm not going to implement into the Android app some quick-hack that's Locus-Only

Yeah, that's fair.
 

, or german-only,

I wonder what would be a generic way of transferring navi instruction hints between applications. For portability, text strings in any language are clearly not the way to go (even if it's english). So maybe sort of a coded value (e.g. 0x1 == straight, 0x2 == left, 0x3 == right, 0x4 == u-turn, maybe with turn angles in degrees)? It's too bad that something like this doesn't seem to exist right now, or we don't know of it.
In the Locus Forum, there where some discussions about the (Garmin?) TCX format, which might have support for this, but I think it's a propriertary format.
 

and I'm somewhat sceptical about adding a third-party scripting library to the android app. This Android App is all about memory queezing and keeping it slim, so beeing conservative on technologies is the only way to avoid regressions.

You are right! But would it be possible to implement it in java inside the app, instead of using the script approach? Maybe that would't be as much of a problem performance-wise?

[abre...@googlemail.com]

Am Freitag, 17. Juli 2015 14:17:29 UTC+2 schrieb Zossebart:

I wonder what would be a generic way of transferring navi instruction hints between applications. For portability, text strings in any language are clearly not the way to go (even if it's english). So maybe sort of a coded value (e.g. 0x1 == straight, 0x2 == left, 0x3 == right, 0x4 == u-turn, maybe with turn angles in degrees)? It's too bad that something like this doesn't seem to exist right now, or we don't know of it.

Just by chance saw that www.gpsies.com allows some filtering options when downloading a GPX. One of them is adding navigation instructions.

They look very similar to gelra01's, but with additional tags "sym" and "type" (with always sym=type). Is that a common standard?

  <wpt lat="51.36373763" lon="6.315708730">
    <ele>34.000000</ele>
    <name>100 m Links abbiegen, Kurs: 159° S</name>
    <sym>Left</sym>
    <type>Left</type>
  </wpt>
  <wpt lat="51.34723003" lon="6.324083325">
    <ele>37.000000</ele>
    <name>100 m Weiter, Kurs: 167° S</name>
    <sym>Straight</sym>
    <type>Straight</type>
  </wpt>
  <wpt lat="51.34136306" lon="6.326228354">
    <ele>37.000000</ele>
    <name>100 m Links leicht, Kurs: 156° SE</name>
    <sym>TSLL</sym>
    <type>TSLL</type>
  </wpt>

 

.. would it be possible to implement it in java inside the app, instead of using the script approach? Maybe that would't be as much of a problem performance-wise?

Scripts are cool. BRouter profiles are scripts as well. Maybe this can get together.
 

[gel...@gmail.com]

> I wonder what would be a generic way of transferring navi instruction hints between applications. For portability, text strings in any language are clearly not the way to go (even if it's english). So maybe sort of a coded value (e.g. 0x1 == straight, 0x2 == left, 0x3 == right, 0x4 == u-turn, maybe with turn angles in degrees)? It's too bad that something like this doesn't seem to exist right now, or we don't know of it.

I don't think so. In many cases routing is much more complex than just “turn right” or “turn left”. A more sophisticated navigation hint in a given context could be “follow the road for another 2 km and then turn right into the farm track”. You would need a more complex structure to transport this message by language independent codes. Transporting just the message does give you all the flexibility you might need.

> You are right! But would it be possible to implement it in java inside the app, instead of using the script approach? Maybe that would't be as much of a problem performance-wise?

I think it is vital to put navigation hint calculation into a script. Depending on the navigation context the results might be very different. If you are driving a car, you don't want to know that it might be a good idea to stay on the road and not to take the steps on the right hand side. If you are just hiking, it might be worth knowing.
BRouter uses scrips to customize routing to your context and preferences. I definitely like this idea. The same should be true for navigation hint processing, especially because navigation hints have most likely to do with language and that should not be contained within a closed code.

[Poutnik]

Do 3rd party online router services provide navigation hints ?
Or, are they created by target application like OSMAnd, based on
provided route ?


Dne 23/07/2015 v 08:39 gel...@gmail.com napsal(a):

[Zossebart]

Hi,

On Thursday, July 23, 2015 at 8:54:40 AM UTC+2, Poutnik wrote:

Do 3rd party online router services  provide navigation hints ?
Or, are they created by target  application like OSMAnd, based on
provided route ?

there are some 3rd party online routing services which provide navigation hints e.g. MapQuest or Google. However, the developer of Locus allegedly stated, that they each have a different way of transferring the nav hints. See the quote in this (german) thread in the Locus Forum about the very same topic:

http://forum.locusmap.eu/index.php?topic=4064.msg36849#msg36849

Locus falls back to it's internal navigation hint generator in case the routing service does not provide hints (e.g. Brouter). This is in fact working quite good, but not optimal, as you can imagine.

 

[Zossebart]

I did some further investigation in this and can only confirm: all of the routing providers seem to have their own routing API, as well as different ways of exporting the route with navi hints to GPX format :-(

APIs:
Google: https://developers.google.com/maps/documentation/directions/intro
Yours: only returns simple GPX (track) without instructions
MapQuest: JSON or XML return: http://www.mapquestapi.com/directions/#response
OSRM: JSON return: https://github.com/Project-OSRM/osrm-backend/wiki/Server-api
Graphhopper: JSON or GPX return: https://github.com/graphhopper/directions-api/blob/master/docs-routing.md

GPX export:
- bikemap, outdooractive, strava, bikeroutetoaster, yours, openrouteservice and OSMR don't seem to export any turn instructions to GPX
- bbbike, gpxgmap, cycle.travel and cyclestreets only export turn instructions or street names in <name> or <desc> -tags of <rtept> or <trkpt> elements

- GPSIES exports the track (<trk>), as well as turn instruction texts and types wrapped in waypoints:
  - <wpt><name>: textual instruction
  - <wpt><type>: instruction type, I discovered the following values:
    - TSLR: slight right
    - Right: right
    - TSHR: sharp right
    - TSLL: slight left
    - Left: left
    - TSHL: sharp left
    - TU: u-turn
  - <wpt><sym>: instruction symbol, same as <type>, but lowercase

- OSMAnd exports the track (<trk>), as well as turn instruction texts and turn-angles, turns etc. in extensions to <rtept> elements:
  - <rtept><desc>: textual instruction
  - <rtept><extensions><turn>: turn/instruction type, I discovered the following values:
    - no <turn> element: straight ahead
    - KR: keep right
    - TSLR: slight right
    - TR: right
    - TSHR: sharp right
    - KL: keep left
    - TSLL: slight left
    - TL: left
    - TSHL: sharp left
    - TU: u-turn

- Locus exports the track (<trk>), as well as turn instruction texts and point actions in extensions to <wpt> elements:
  - <wpt><name>: textual instruction
  - <wpt><extensions><locus:rtePointAction>: point action (turn instruction), I discovered the following values:
    - 1: straight ahead/follow street
    - 2: ??
    - 3: slight left
    - 4: left
    - 5: sharp left
    - 6: slight right
    - 7: right
    - 8: sharp right
    - 12: u-turn
    - 14: destination

- Graphhopper exports the track (<trk>), as well as turn instruction texts and instruction signs in extensions to <rtept> elements:
  - <rtept><desc>: textual instruction
  - <rtept><extensions><gh:sign>: turn sign/instruction, I discovered the following values:
    - 0: straight ahead
    - 1: slight right
    - 2: right
    - 3: sharp right
    - -1: slight left
    - -2: left
    - -3: sharp left
    - 4: destination
    - 5: via point

We are far from a consistent standard, you see :-(
With some apps (e.g. Locus and Oruxmaps) I discovered "ugly" results with GPX-exports which contain a track (<trk>), as well as a route (<rte>) (like Graphhopper and OSMAnd exports): the app displays both the (detailed) track, as well as the (rough) route simulaneously. Therefore, I would prefer a format with the turn instructions packed into waypoints (<wpt>), like Locus or GPSIES does.
Furthermore, I think formats which only contain instruction texts are not as suitable for turn-by-turn navigation as formats containing both texts and distinct instruction values (like OSMAND, Locus, Graphopper and GPSIES)

Given the variety of existing solutions, you might as well define your own one. Obviously, everyone does this ;-)
Or you could decide to re-use one of the existing solutions (probably the one most of the apps already support) and implement it into brouter (provided the licence allows this).

I hope we can make some progress in this field. I (and I think many more) would love to have turn instructions natively provided by Brouter!

regards,
zossebart

[abre...@googlemail.com]

Am Freitag, 2. Oktober 2015 16:33:52 UTC+2 schrieb Zossebart:

Given the variety of existing solutions, you might as well define your own one. Obviously, everyone does this ;-)
Or you could decide to re-use one of the existing solutions (probably the one most of the apps already support) and implement it into brouter (provided the licence allows this).

Cool, good work. Yes I think the most promising approach is to not care on interface formats, but just on the model and the algorithm, that is, produce good data, choose a data-model with a small missmatch to the existing approaches, write that in comment-syntax into the xml  and see wht happens. This is likely to be my topic for the next Karlsruhe hack-weekend at geofabrik in to weeks.

[Zossebart]

This is likely to be my topic for the next Karlsruhe hack-weekend at geofabrik in to weeks.

 Ahh yes, this sounds like a nice topic for the hack-weekend. Maybe there are even people attending which have some more insight in this field?!
Given that there already is a first implementation from the original author of this thread, and you already put some thoughts into this discussing with him, I'm sure you will come up with a good solution.

Yes I think the most promising approach is to not care on interface formats, but just on the model and the algorithm, that is, produce good data, choose a data-model with a small missmatch to the existing approaches, write that in comment-syntax into the xml  and see wht happens.

I'm not sure what you mean by "comment-syntax into the xml"? Does this mean that the navi instructions in the first implementation will end up not being useable by an app, but at least human-readable as comments in the gpx-file for verification?

btw., I found yet another (different) routing API description using a JSON-format (used by Mapzen): https://github.com/valhalla/valhalla-docs/blob/master/api-reference.md

[Zossebart]

Hi,

On Tuesday, October 6, 2015 at 2:35:35 PM UTC+2, Zossebart wrote:

This is likely to be my topic for the next Karlsruhe hack-weekend at geofabrik in to weeks.

I would like to know what's the status on this? Did you attend the hack-weekend?
I assume you rather worked on the new optimized segments format then on the navi hints topic? Btw. thank you for that, this saves precious space on my mobile!
 

[abre...@googlemail.com]

Well, yes, like that. Data format re-factoring took all the resources from my limited brain, also in Karlsruhe..

Wasn't only space and bandwith savings driving that, but some fundamental memory issues affecting stability.

Don't know when to come back to to the instructions-topic, but pretty sure that the winter will be long enough.

regards, Arndt

[Zossebart]

Thanks for the information!
No hurry, take your time. I assume developing brouter is not your fulltime job, is it? Under these circumstances, it's really great what you already created until now! Thanks again for this!

regards, Zossebart

[Zossebart]

Hey Arndt,

now that the winter slowly comes to an end, I would like to ask again if you were able to spend some time on this topic during the long winter evenings? Would be great to have this available for the upcoming bike season ;-)

regards,
Zossebart

[abre...@googlemail.com]

thank's for the wakeup...

I've some holdidays currently and promise to deliver something next weekend. It will not be a silver-bullet, at least not something that is not talking bullshit at roundabouts and satifies all interfacing requirements, but it will be a starting point and define a central place for the missing logic to go, to eventually attract other developers for finetuning.

regards, Arndt

[abre...@googlemail.com]

Am Freitag, 2. Oktober 2015 16:33:52 UTC+2 schrieb Zossebart:

... Therefore, I would prefer a format with the turn instructions packed into waypoints (<wpt>), like Locus or GPSIES does.

...

I hope we can make some progress in this field. I (and I think many more) would love to have turn instructions natively provided by Brouter!

Hi,

so I gave it a try and committed a patch to github (see the latest commit in github).

It uses a new expression "priorityclassifier" to define the relative way-priorities, but the rest of the logic is hard-coded. Currently, this logic is rather simple: a turn starts at 15 degree, and if that junction has any other way with equal or higher priority, then a waypoint is created. In addition, "Straight-On" waypoints are created if any other way of that junction has a  higher priority. This is probably too simple, however, ths part of the logic is well detached (See classes VoiceHint.java and VoiceHintProcessor.java ).

I did not succeed to have Locus process these voice hints. But in my tests today, I did not succeed to create any reasonable voice hints in Locus, not even after switching to MapQuest, all I heard was confusing, so maybe I am doing something wrong. I also played with Locus specific extensions, with no success either. I asked a question in Locus forum, hope to get any feedback there.

I uploaded zip with the patched apk + jar file as well as a "trekking.brf" with the new expression added:

http://brouter.de/brouter_bin/voice_hint_patch.zip

The simplest thing you can do to test the new feature is to:

- use brouter.de/brouter-web (where the patch is active)
- modify the profile to contain the "priorityclassifier" expression (within the way-context)
- or upload the "trekking.brf" from the zip-file
- create tracks and download as GPX-Files
- display these GPX files using any tool or online site able to display both the track and the waypoints

So the most urgent issue is to solve the interfacing issue with Locus. I think the algorithm part is the fun part.

I did not try with OsmAnd. I know that the voice hint's cannot pass the service-interface (because OsmAnd's interface to Brouter I implemented myself), but maybe it works with explicit GPX tracks?

Happy for any feedback, though this is not yet a useful feature.

regrds, Arndt

[abre...@googlemail.com]

Am Samstag, 9. April 2016 17:24:46 UTC+2 schrieb abrensch:

 

I did not succeed to have Locus process these voice hints. But in my tests today, I did not succeed to create any reasonable voice hints in Locus, not even after switching to MapQuest, all I heard was confusing, so maybe I am doing something wrong.

I gave it a second try and now it works with Locus at least when importing the gpx generated by brouter.

To  achieve that, I use the locus specific extension:

  <wpt lon="8.608944" lat="49.674370">
     <name>right</name>
     <extensions>
        <locus:rteDistance>292.0</locus:rteDistance>
        <locus:rtePointAction>7</locus:rtePointAction>
     </extensions>
  </wpt>

The voice message I hear is german (for me), so the name-tag seems to be ignored and language specific messages generated b locus - that's good. "rteDistance" is the distance to the next instruction.

Unfortunatly, this breaks the gpx-syntax for non-locus use, at least OsmAnd refuses to impirt such a gpx. So I introduced a new config parameter "turnInstructionMode" with values :

  0=none, 1=gpsies-style, 2=locus-style

I adapted the "trekking.brf" at http://brouter.de/brouter-web to contain both new variables ( "turnInstructionMode" + "priorityclassifier" ), but set  turnInstructionMode = 0.

So to test with locus via brouter-web, just switch to turnInstructionMode = 2.

Or use the trekking.brf and the APK from the updated patch-zip-file: http://brouter.de/brouter_bin/voice_patch.zip and genarete a GPX on android, then import that into Locus.

I also tested GPX-Import with OsmAnd ( using turnInstructionMode = 1 ), but I got a confusing mixture of waypoint-announcements and generated turn instructions.

I did some field tests with Locus and the new voice hints and it was already quite usable. Definitly needs more fine-tuning, e.g. at roundabouts, narrow forges, or "curved" legs. But still the most urget issue is to get the interfacing done - so that it will also work when using BRouter via the service-interface.

@Poutnik: thanks for your feedback (private message?). For your remark on way-priorities: my approach generates voice hints for equal-priority junctions, so I guess having track=road=path all equal is o.k.?

[Volker]

Osmand can import turninstructions like this:

</rtept>
<rtept lat="49.2094392" lon="10.0648713">
<desc>keep right</desc>
<extensions>
<turn>KR</turn>
<offset>103</offset>
</extensions>
</rtept>

Offset is the the number of the trackpoint with the same coordinates. Desc is shown in the navigation list but seems not to be spoken. Turn are the instructions, see https://github.com/osmandapp/Osmand/blob/master/OsmAnd-java/src/net/osmand/router/TurnType.java but you can't import C (go straight).

[Poutnik]

Dne 10/04/2016 v 15:58 'Volker' via OSM Android bikerouting napsal(a):

Hm, it looks like the need to have different set of profiles
for Locus and for OSMAnd.....
.. unless turnInstructionMode info would be kept out of the profiles.

--
Poutnik ( The Wanderer )

My Brouter profiles
https://github.com/poutnikl/Brouter-profiles/wiki

[Zossebart]

Hey,

I only had time to do a short test on the sofa so far (was busy biking ;-) ), but I can confirm that the current version generates turn instructions useable by Locus with turnInstructionMode=2, when importing the generated GPX. This is a great starting point already!
Thank you so much for this!

I hope I can find time to test some more tomorrow....

regards,
Zossebart

[Andrew Heard]

Great beginnings of new development Arndt.

>Currently, this logic is rather simple: a turn starts at 15 degree

Does that mean there will be a waypoint on any > 15 degree bend in road which otherwise has no junction? Internal Locus navigation does that, but of no use for out-of-city quite roads with lots of bends because Locus display turns on/off all the time for no useful reason.

[Andrew Heard]

I should have experimented @ http://brouter.de/brouter-web/ before asking question. Sorry Arndt. Can answer own question. Yes - just on "proper" junctions. Wow - already quite usable, and already great advance forward from current app functionality. Even at junction where track is directly forward (less than 15 degrees turn?) it would be reassuring (for me as touring cyclist) to have Locus announce a straight ahead waypoint. Thanks for email Poutnik.

[Poutnik]

I guess I have finally got it, your ways seems correct to me now. :-)

Dne neděle 10. dubna 2016 14:46:45 UTC+2 abre...@googlemail.com napsal(a):

[poutnik]

Hmm. Wait..
In straight on Hunt is given is for higher priorities
and if path and track have the Same one......
then if the track I follow turns
But I have to follow the streight on path
Then I would not get hint. But I should get it.

11. dubna 2016 11:17:05 CEST, Poutnik <poutni...@gmail.com> napsal:

I guess I have finally got it, your ways seems correct to me now. :-)

Dne neděle 10. dubna 2016 14:46:45 UTC+2 abre...@googlemail.com napsal(a):

@Poutnik: thanks for your feedback (private message?). For your remark on way-priorities: my approach generates voice hints for equal-priority junctions, so I guess having track=road=path all equal is o.k.?

--
Sent from my phone via Android email client K-9.
Please, forgive my brevity.

[Poutnik]

Do you plan to implement also keep left / keep right ?
Like e.g. if there are 2 ways within +/- 15 degrees , possibly making confusion which one of them  is the straight one.

Dne sobota 9. dubna 2016 17:24:46 UTC+2 abre...@googlemail.com napsal(a):

[abre...@googlemail.com]

On Monday, April 11, 2016 at 3:19:12 PM UTC+2, Poutnik wrote:

Do you plan to implement also keep left / keep right ?
Like e.g. if there are 2 ways within +/- 15 degrees , possibly making confusion which one of them  is the straight one.

to be honest, my plan is not to do the fine-tuning myself. This is a perfect project for other contributors looking for something which is challenging from the algorithm side, but reasonably context-free, so without much digging into legacy code. See the opening text of this thread...

True, this is a non-trivial problem. A must-have is to do motorway-exits right. They have always small angles and sometimes the exit goes straight, and the motorway to the left... But also while biking, you sometimes hit narrow forges, with maybe both ways going slight-left, and you may want to generate a "keep right" to describe the situation.

Also the way-priorities need fine-tuning. Maybe the grade1-paths need a higher category than other paths? So the priority-expression can get as complex as the costfactor. Or just use the costfactor instead?

[Poutnik]

I see...
I could contribute a little in algorithms, but not much in coding,
as my rusty knowledge of Z80 assembler, CP/M Turbopascal, basics of C and current susing of VBforApplications will not help much.

For trackgrades, they may definitely deserve more granularity,
as grade1 is for trekking bike/MTbike/foot like as primary road for cars. grade2 like as secondary...

My latest development Trekking profile implementing Locus hints is here :
https://raw.githubusercontent.com/poutnikl/Trekking-Poutnik/psmallpaved_factor/Trekking-Poutnik.brf

Dne pondělí 11. dubna 2016 17:35:26 UTC+2 abre...@googlemail.com napsal(a):

[abre...@googlemail.com]

On Tuesday, October 6, 2015 at 2:35:35 PM UTC+2, Zossebart wrote:

Yes I think the most promising approach is to not care on interface formats, but just on the model and the algorithm, that is, produce good data, choose a data-model with a small missmatch to the existing approaches, write that in comment-syntax into the xml  and see wht happens.

I'm not sure what you mean by "comment-syntax into the xml"? Does this mean that the navi instructions in the first implementation will end up not being useable by an app, but at least human-readable as comments in the gpx-file for verification?

 

On Sunday, April 10, 2016 at 4:05:19 PM UTC+2, Poutnik wrote:

.. unless turnInstructionMode info would be kept out of the profiles.

Menion (Author of Locus) answered to my question on the interfacing problem ( see http://forum.locusmap.eu/index.php?topic=5066.msg42240#new )

He says, BRouter should'nt generate target specific syntax, but define it's own, and he's ready to evaluate whatever we deliver.

The lead's me back to the idea of using a comment-syntax that does not have any side-effects and does not break any imports. Such a comment syntax would be the default (generated by an out-of-the-box BRouter installation), with the possibilty to generate other formats by setting the turnInstructionMode  parameter.

That comment syntax would contain the superset of information of the existing formats, to keep the model-mismatch small. E.g. it would contain the lon/lat of the wayspoint *and* the offset of the corresponsing track-point (lon/lat is ambigious for tracks crossing themselves?). And it would contain the complete junction geometry, including angles and priorities of all ways, just to make it easy to check the decision the algortithm makes.

Like this:

 /* --turn-instructions-start
    --turn  TSLR at 25(8.608944/49.674370) next 630  follow 4(25)5 ignore (-15)4  (50)4
    --turn-instructions-end */

makes sense?

[Poutnik]

Dne pondělí 11. dubna 2016 18:10:59 UTC+2 abre...@googlemail.com napsal(a):

.....

That comment syntax would contain the superset of information of the existing formats, to keep the model-mismatch small. E.g. it would contain the lon/lat of the wayspoint *and* the offset of the corresponsing track-point (lon/lat is ambigious for tracks crossing themselves?). And it would contain the complete junction geometry, including angles and priorities of all ways, just to make it easy to check the decision the algortithm makes.

Like this:

 /* --turn-instructions-start
    --turn  TSLR at 25(8.608944/49.674370) next 630  follow 4(25)5 ignore (-15)4  (50)4
    --turn-instructions-end */

makes sense?

 
   --turn  TSLR at 25(8.608944/49.674370) next 630  follow 4(25)5 ignore (-15)4  (50)4

Would deserve some legend, but generally it is a good idea.
Applications not aware of those direction hints will just ignore it.