BRouter: offline Fahrrad-Routing für Android

Zu 1: Unterstützung in der nächsten Android-App … das hört sich gut an. In welche Datei müßte man, bis es soweit ist, denn reinschauen?

Zu 2: Ja, ich meinte die Ausgabe von Sprachtexten während der Streckenführung. Du hast es aber auf den Punkt gebracht: “Hemdentaschen-Navigation, also Sprachhinweise, die so gut sind, dass man die Karte nicht mehr braucht, wäre ein coole Sache.”

Ich übernehme deine Antworten (in den nächsten Tagen) mal ins Locus-Forum: http://forum.locusmap.eu/index.php?board=27.0 Die User dort sind zwar nicht so viele, aber sehr bemüht die Dinge weiter zu entwickeln.

Gruß Klaus

PS: Vielleicht hast du aber Lust dich im Locus-Forum selbst zu äußern …

Das Wegenetz (die ganzen Knoten und Polygonzüge/Koordinatenlisten) braucht man aber für beide Zwecke. Es stehen noch ein paar Infos zur Berechnung der Pfadmetrik drin, und die Verknüpfungen der Wege, aber eigentlich lässt sich das gut verheiraten. Mit einer Datenbankstruktur (sqlite-File?) incl. Index ist auch der Datenzugriff relativ flott. Auch für eine routingfähige Display-Karte kann man viele Keys weglassen oder effektiver speichern.

Die Trennung ist natürlich dann praktisch, wenn BRouter für andere Apps als OsmAnd routet und deren Karten nicht routingfähig sind. Als OsmAnd-Plugin wäre es aber schon praktisch wenn es die vorhandenen routingfähigen Karten nutzen könnte. Die muss man sich vor einem Urlaub sorgfältig zusammenstellen, damit alles auf die SD-Karte passt. Europa gesamt wäre schon heftig. OSM hat eben viel mehr Details in der Karte als bei den kommerziellen Routing-Lösungen.

Gibt es bei den Entwicklern Interesse, einen gemeinsamen Standard für routingfähige Vektorkarten zu formulieren? So wie bei mapsforge für die nicht routingfähigen? Wäre das OsmAnd-Kartenformat ein guter Einstieg,?

Schau dir einfach mal die Diskussion zu Graphhopper an. Dort stoßen verschiedene Theorien aufeinander.

Graphhopper benutzt laut Infoseite schnellere Varianten des Dijkstra
mit vorausberechneten Daten.

Die Dateigrößen der rd5 sind ja doch recht kompakt.
Na, vielleicht passt das dann doch nicht so recht zusammen.
Man müsste schon im Detail die Datenstrukturen vergleichen.
Vielleicht hat auch OsmAnd einen kompaktierten Datensatz für das Routing
drin, der lediglich aus den Knoten und Verbindungsmetriken besteht.

Ich verstehe euer Problem: je besser sich BRouter in OsmAnd integriert
desto schwieriger wird die Unterstützung für andere Kartenapps.
Mein Favorit wäre natürlich eine Totalintegration in OsmAnd, so dass
alle dortigen Vorzüge genutzt werden, die Kartenbasis und die Möglichkeit
des Routen-Neuberechnens.

Gerade das ist mir unterwegs auf dem Rad wichtig, da ich immer wieder
mit Absicht von der Route abweiche, und vom Router verlange, dass
er das gleich berücksichtigt, ohne anzuhalten und am Gerät herumfummeln zu müssen.

Ich weiss nicht, ob die anderen Apps dafür die Voraussetzungen mitbringen.
Jedenfalls ist eine OsmAnd-Integration einfacher, weil der Sourcecode frei ist.

Jetzt fehlt nur noch das schöne Wetter zum Testen.
Als die Sonne geschienen hatte musste ich noch im Büro sitzen …

OsmAnd und Brouter … ob das eine Erfolgsgeschichte wird bzw. werden kann?
M.E. eher nicht … Zuviele Köche verderben den Brei.

Gruß Klaus

Hallo Brouter Gemeinde,

ich hab mal “just for fun” den BRouter in einen Desktop-MapsforgeViewer eingebaut. Das GANZE ist “gefrickelt” und in einer frühen Beta Phase. Aber das funktioniert erschreckend gut. Ich habe als Ziel, dass ich auf einem Windows PC meine “Fahrradrouten” und “Wanderrouten” planen kann. Was mir besonders gefällt ist, dass im BRouter “vernüftige” alternative Routen berechnet werden, zumindest soweit ich das beurteilen kann.
Ich hoffe, dass BRouter nicht nur in Richtung OSMAND geht und die “Desktop-Schnittstellen” erhalten bleiben und weiterentwickelt werden. Das ist eine persönliche BITTE an Arndt.

Arbeitet daran noch jemand (Thema:Desktop-Mapsforge-Router)?

In diesem Sinne
Achim

Ps: An die Grashopper-Kenner…wie kann man Grashopper in eine DesktopAnwendung einbinden? Keine ServerVersion sondern über eine entsprechende API-Schnittstellle like BROUTER?

Zwei Meister ihres Fachs. OsmAnd hat die Kartenapp und einen mittelmäßigen Router. Brouter hat den besten Router (to be field tested), aber mangelt es an einer Karten-App. Beide ergänzen sich gut.

Welche Alternativen gibt es? OsmAnd ist die einzige gute Karten-App, die als OpenSource publiziert wird.
Ich finde auch wesentlich besser als Orux und Locus (Wikipedia-POI mit Kurztexten, Offline-Suche in POIs, Einblenden der POI,
vor allem Routing an POI-Ziele, Routing entlang GPX-Strecke, Auto/Rad/Fußgänger-Profile, Offline-Routing).
Die Waypoint-Verwaltung ist vielleicht bei anderen besser ausgereift,
aber über Favoriten doch noch machbar.

Nur wenn man als Radfahrer in der Nacht Routing-Unterstützung braucht und das dumme Teil dann
über die Gipfel steigen will, mangels Höheninformation, dann merkt man, dass noch etwa fehlt.

Und für Locus und Orux nicht vergessen, denen fehlt ja auch das Offline-Routing.

…das verstehe ich nun nicht! Oruxmaps kann doch in Verbindung mit BRouter "Offline-Routing, oder habe ich da was falsch verstanden? Ich nutze das ständig.

BRouter ist doch auch eine Art Server. Was also spricht dagegen den Graphhopper als Server zu starten und dann anzusprechen?

Also BROUTER hat eine entscheidende Schwäche. Er kann gut Fahrradrouting und vielleicht auch für Wanderer. OSMAND hat aber auch Autofahrer als Ziel. von ÖPNV wollen wir mal gar nicht reden. Das macht wahrscheinlich derzeit noch keine offline App.

Meinte ich ja. Ohne BRouter würden die beiden ohne Offline-Routing-Lösung dastehen. OsmAnd hat schon eine eingebaut, mit Sprachansage. BRouter wäre nur eine Verbesserung der Routingfunktionalität für Radfahrer.

Das rd5-format ist ziemlich simpel aufgebaut:

  • Koordinatensystem ist “Mikrograd positiv”

  • keine NodeId’s, sondern stattdessen “unifizierte Geo-IDs”, also 64-Bit Zahlen aus lat-lon,
    die ggf. um jeweils ein oder wenige Mikrograd verschoben wurden, um die Geo-ID eindeutig zu
    machen damit sie als Schlüssel taugt.

    Dreistufiger Index:

    • eine Datei startet mit dem topevel-index (258=200 bytes) mit den start-offsets von
      25 1
      1 Grad Unterdateien

    • eine Unterdatei startet mit dem index von 80804 = 25600 bytes mit den start-offsets
      von 1/80 * 1/80 Grad Kacheln

    • jede dieser Kacheln enthält die Knoten sortiert nach Geo-ID, sodass ein Knoten darin
      über eine binäre Suche effizient gefunden werden kann

  • jeder Knoten codiert Geo-ID, Höhe, Node-Description Bitmap (64 bit) und dann die Liste der “Links”

  • jeder Link codiert die Geo-ID des Target-Knoten, und dann entweder:

    • die Way-Description-Bitmap (64 bit) und ggf. noch eine Liste von
      “Transfer-Knoten” (mit jeweils Geo-ID und Höhe)
    • oder ein Flag, dass anzeigt, dass der “Gegen-Link” am Zielknoten die Weg-Details codiert
  • das ganze noch mit bisschen Pseudo-Kompression, um lat/lons ggf in 16 bit zu kodieren relativ zu irgendeinem
    offset

Da fehlt schon einiges. Insbesondere die 64-Bit “Description-Bitmaps”, die die OSM Tags gemaess
der “lookup.dat” Tabelle codieren, sind eine Limitierung für die Zahl der Tags, und insbesondere
der Relationen, die man da rein codieren kann, und hier müsste ein “ordentlich entwickeltes”
Format dynamischer sein (aber eben trotzdem schnell, also nicht einfach die OSM-Tags als
Text da rein schreiben…)

In OsmAnds obf oder mapsforge steht schon deutlich mehr drin, und sie sind auch kompakter, also müsste eine Neuentwicklung zweifellos auf diesen Erfahrungen aufbauen. Aber ein routingfähiges Format, was (fast) keine OSM Daten wegwirft wäre schon ein interessantes Projekt.

Du kannst das OsmAnd obf Format gerne erweitern, wenn du mehr Tags verarbeiten willst (Straßenbelagsqualität?).
Wenn das Sinn macht ist sicher auch Victor zu Änderungen bereit.
Ist halt praktischer und weniger Arbeit, auf etwas Existierendes aufzubauen.
Datenreduktion an sich halte ich schon für wichtig, um die Kartengröße noch erträglich zu halten.
Wenn da erstmal alle Straßenlaternen gemappt werden, würde es den Datensatz nur unnötig aufblähen.

Natürlich sind auf den Zweck minimierte Datenformate effizienter, aber ist die Frage ob das beim Routing so entscheidend ist.
Die meiste Zeit bei OsmAnd vergeht beim Rendern der Vektorkarte. Die Routenneuberechnung läuft nur sporadisch ab.
Ob man dann eine Sekunde mehr oder weniger warten muss spielt in der Praxis keine Rolle.

…das ist richtig, man kann den BRouter auch als Server benutzen. Das mache ich aber nicht! Wie man ja bei Oruxmaps gesehen hat, ist das Handling von zwei Programmen nicht immer problemlos zu handhaben. Dort haben erst die Intents eine spürbare Vereinfachung gebracht.

Ich rufe bei mir den BRouter nicht via Serverkommunikation auf, sondern rufe die Routingfunktion der Library direkt, unter Umgehung der Serverfunktion, auf. Also nichts mit BRouter-Server starten und dann Programm starten…und irgendwas hängt! BRouter ist somit fester Bestandteil meines Programmes und völlig transparent.
Ich hätte eben gerne eine Library (JAR) in der ich die entsprechenden Funktionen aufrufen kann, unter Umgehung des Servers.

Man kann die Graphhopper-API jederzeit direkt ansprechen. Der Webserver ist da nur zusätzlich oben drauf gebaut.

In einer Java-Applikation kann man direkt ein Graphhopper-Objekt anlegen und benutzen.

bye, Nop

PS: Wenn Du in dieser Richtung weiterdiskutieren willst schlage ich ein eigenes Thema vor, hier geht es um BRouter, nicht um Graphhopper.

Ja doch, es ist entscheidend. Das ist schliesslich der Grund für den “Routing-Zoo” bei OsmAnd aus Java/C++, “precise” oder nicht.

BRouter findet hauptsaechlich deshalb bessere Ergebnisse als OsmAnd-offline, weil er mehr Knoten in der selben Zeit rechnen kann. Und auch die Precise-Alpha Version in OsmAnd rechnet weniger Knoten, weil seine Kostenfunktion in der “routing.xml” eine geringere “Spreizung” (=durchschnittliches Verhältnis Kosten zu Luftlinie, bzw. andersrum in OsmAnds inverser maxspeed-logik) hat als man das vernünftigerweise einstellen würde.

Diese Spreizung bestimmt beim A*-Algortithmus direkt die seitliche Ausdehnung der Elipse des Suchgebiets und damit die Zahl der Knoten, und solange es da eine Rückkopplung gibt zwischen der Definition der Kostenfunktion und technischen Randbedingungen ist das Ergebnis ja auch dann nicht optimal, wenn es aus algorithmischer Sicht präzise ist, also tatsächlich das Kostenminimum gemaess der Kostenfunktion findet.

Und der Höhenterm bei BRouter erhöht die Spreizung zusäzlich, was ja auch anschaulich klar ist, weil wenn man in der Lage sein will, einen Berg zu umfahren, muss man ggf. auch ziemlich weit links oder rechts das rettende Tal suchen, und das alles geht eben nur, wenn man die Knoten genügend schnell durch die Routing-Maschine jagen kann (Oder eben Contraction-Hirachies vorberechnet ala Graphhopper oder OSRM).

Nicht mit Mapsforge, aber ich bin - wie schon länger geplant - an einem Web-Client dran. Vorerst mal nur in Kombination einem Standalone-Server für den Desktop. Die entsprechende Schnittstellen-Erweiterung ist bereits im brouter.jar. Ich habe vor, demnächst mal eine erste Alpha Version zu veröffentlichen.

Überschneidungen gibt es bei unseren beiden Ansätzen aber vermutlich nicht.

Gruß,
Norbert

Ich denke das war gar keine so schlechte Idee mit dem Java/C++ Mix. C++ muss leider relativ Prozessorspezifisch kompiliert werden, so dass es einige Android-Geräte gibt auf denen das nicht läuft (z.B. x86 Tablets). In Sachen Plattformunabhängigkeit des Binärcodes ist Java natürlich Spitze.

Aber Java ist auch i.d.R. langsamer als C++. Oft merkt man es nicht, aber oft eben doch. JIT kann helfen, aber es löst nicht alle Probleme. Schutzfunktionen, z.B. Bereichsprüfung beim Array, ist ja ganz nett, aber kostet Zeit. Ohne Prüfung riskiert man Abstürze, aber die Zugriffe sind dann auch locker doppelt so schnell. Das macht man durchaus wenn man selbst dafür sorgt, dass die Grenzen eingehalten werden. C/C++ kann man deutlich maschinennäher und damit schneller ausnutzen. Automatische Garbage Collection ist praktisch, aber auch nicht immer gut für die Performance. Ich vermute auch die Argumentübergabe in Java ist langsamer. In C/C++ kann man fast alles Überflüssige wegoptimieren, sogar den Funktionsoverhead selbst (inline).

Victor wollte sogar alles komplett auf C++ umstellen.

Ich hatte mal aus Versehen beim Verlinken die native Library-Apps getrasht. OsmAnd hat dann auf Java-Only umgeschaltet. War ganz schön lahm im Vergleich. Vor allem beim Kartenaufbau der Vektorkarten.

Sicher? Ich hatte gehört, dass der Speichermangel das größte Problem wäre. Ist es nicht auch bei Android so, dass wenn das RAM nicht reicht, Speicherseiten auf die SD-Karte geswappt werden? Das wäre dann natürlich superlangsam. RAM ist auf meinem Billig-Samsung recht knapp. Ich habe es noch nicht auf großen Smartphones getestet.

Ich bin kein Router Experte. Aber ich dachte der große Vorteil von BRouter wäre seine Konfigurierbarkeit und die Nutzung des Höhenprofils für die Metrik. Ich hatte nicht den Eindruck, dass OsmAnd zu viele Umwege mangels Optimierung liefert. Probleme hatte ich vor allem da gesehen, wo OsmAnd einfach andere Prioritäten setzt. OsmAnd bevorzugt Fahrradwege entlang viel befahrener Straßen. Kann man machen für die Rennradler unter uns, für sie eine gute Metrik. Ich möchte aber Ruhe und fahre bevorzugt Feldwege und noch lieber Waldwege. Aber wer berücksichtigt den Waldanteil? Ehrlich gesagt hat mir bisher noch kein Router zuverlässig aus meiner Sicht attraktive Routen geliefert. Ich priorisiere auch keine Fernradwege, wenn es ruhigere Alternativen im Wald gibt. Hoch im Kurs stehen bei mir Fluss- und Bachläufe, Mischwald, Fernsicht auf Höhenwegen etc.

Einen Nutzen erhoffte ich mir vom OsmAnd-Routing einmal als es im Wald stockdunkel war, kein Mondlicht, keine Orientierung. Die starke LED-Lampe hatte ich vergessen, konnte dann nicht einmal die Radwegebeschilderung ablesen. Ich dachte, Ok, OsmAnd führt dich nach Hause. Leider wollte es wieder zurück über die Berggipfel. Sehr lustig. Also habe ich dann versucht, mich an der Kartenpeepshow am Handy zu orientieren. Das Display ist leider zu klein, um in der Landschaft einen guten Überblick über das Wegenetz zu bekommen. So hatte ich OsmAnd auch manchmal nur unterstützend zum Routing herangezogen, weil ich keine Papierkarte dabei hatte. Naja, Routing für das Fahrrad ist schon eine sehr komplexe Materie. Da gibt es mehr zu Diskutieren als beim Automobil-Routing.

Diese Annahme ist etwa 10 Jahre veraltet. Sieh z.B. die Benchmarks hier: http://scribblethink.org/Computer/javaCbenchmark.html

Es ist aber in Java zugegebenermaßen leichter, durch ungeschicktes Zusammenstecken der bereitgestellten Klassen ein schlechtes und langsames Programm zu schreiben.

Beispiele für extrem schnelles Java sind z.B. Graphhopper, die IDE IntelliJ oder Star Wolves, ein Spiel a la Homeworld mit 3D Vektorgrafik.

bye, Nop

Nur wenn die SD-Karte eine Swap-Partition hat und diese aktiviert ist (also wie bei einen normalen Linux). Dafür muss man allerdings fast immer das Gerät erst rooten…

Rennrad-Fahrer bevorzugen vermutlich eher radwegfreie Strassen, aber das ist ein anderes Thema…