BRouter: offline Fahrrad-Routing für Android

BRouter hat seine eigenen Routing-Daten in Form von 5°x5° Quadraten, die ca. 250-300MB groß sind. Normalerweise kommt man in seiner weiteren Heimatregion mit 2, maximal 4 davon aus. In Locus kann man mittlerweile für eine geführte Navigation BRouter genauso auswählen wie andere Navigationsdienste. In OSMAND kommt das hoffentlich noch, ein Pull-Request dafür wurde vom Autor jedenfalls gemacht.
Bei OSMAND steht das natürlich in einer gewissen Konkurrenz zum eingebauten Offline-Routing, aber im Vergleich wird speziell das Fahrradrouting in OSMAND eher stiefmütterlich behandelt, Einbahnstraßen mit erlaubter Gegenrichtung werden z.B. immer noch nicht berücksichtigt.

Hi,

hier mal gebündelt Antworten zu den letzten 3 Beiträgen:

Ja, also hellsehen kann ich nicht, und der “Sinn des Erfinders” ist tatsächlich, nach der aktuellsten Wegpunkte-Datenbank zu suchen und relativ von da das Tracks-Directory zu vermuten. Wenn in Oruxmaps was anderes konfiguriert ist, komme ich da nicht ran.

Werde aber in der nächsten Version als Workaround eine Weiterleitungs-Mechanismus hizufügen, so dass man dan im “falschen” Zielverzeichnis ein redirect-file ablegen kann, in dem der Pfad zum “richtigen” Zielverzeichnis steht.

Nein. Aber seit 0.95 liegen diese Konfigurations-Dateien auf der SD-Karte (brouter/modes) so dass man sich die Dateien anschauen könnte, wäre aber bisschen mühselig.

Ich werde in der nächsten Version nach dem Speichern der Service-Konfiguration noch einen Feedback-Dialog nachschalten, in dem die gesamte Konfig als Übersicht gezeigt wird (nur Profil-Name und Zahl der Nogos)

Meinst Du Mehrsprachigkeit der App oder meinst Du Sprachausgabe?

Nein, die App weiter aufzubohren in Richtung Mehrsprachigkeit hab’ ich keine Ambitionen. Deutsche Doku steht aber schon weit oben auf der Liste.

Thema Sprachausgabe ist aber spannend. Wie openzzz schon schreib, macht OsmAnd das ja schon recht ordentlich, aber auch OsmAnd kann zusätzliche Informationen vom Router verwenden, um bessere Ansagen zu machen, und Locus ist ohne solche Infos ziemlich sprachlos, also das ist natüclich Thema, diese Information zu liefern, also Sprach-Hinweise, die nicht nur aus dem Verlauf der Route abeleitet werden (“jetzt rechts”), sondern tatsächlich aud dem Netztwerk (“an der nächsten Kreuzung geradeaus”).

“Hemdentaschen-Navigation”, also SPrachhinweise, die so gut sind, dass man die Karte nicht mehr braucht, wäre ein coole Sache.

Nein, BRouter braucht immer seine eigenen (*.rd5) Dateien

Nein, mit sowas wird man nicht froh.

Naja, bei < 1Euro/GB hat der eine oder andere den einen Euro für Deutschland-Abdeckung mit RD5-Files schon übrig.

Meine 32 GB µSD ist voll. Die 64’er kostet 44€. Kaufe ich erst wenn es unbedingt notwendig ist, also nicht diesen Winter.
Einige Gigabytes gehen schon für die Wikipedia EN+DE drauf. Das ist offline im Urlaub ganz praktisch.
Luftbildkarten und Raster-Topo-Karten schlucken auch recht viel.

Leider brauchen die meisten Routing- und Kartenapps jeweils eigene spezielle Karten.
mapsforge können sich noch Locus und Orux teilen, aber der “MapFactor Navigator” braucht
wieder eigene. OsmAnd hat auch ein eigenes Format.

Ich hatte es schonmal angesprochen: kann man sich nicht irgendwie auf ein Vektorformat einigen,
damit man die Länder nicht doppelt und dreifach installieren muss?
Hat RD5 einen Vorteil gegenüber dem OsmAnd-Kartenformat?
Zumindest ist OsmAnd OpenSource, d.h. das Format und der Code zum Lesen und Schreiben ist publik.
Es gibt auch noch ein PC-Programm für OsmAnd zum Erzeugen der OSM-Karten.
Falls die Unterschiede zu RD5 nicht groß sind könnte man das bestimmt irgendwie verheiraten.
Vor allem brauchst du dann nicht einen eigenen Distributionszweig für RD5-Karten aufbauen.
Die OsmAnd-Karten liegen für viele Länder auf dem Downloadsever bereit (http://new.osmand.net/list.php)

Für die Höhenkarte, Ok, das ist ein anderer Fall. Die Höhenprofilkarte (Höhenlinien) kann man so nicht nehmen.

Naja beim navigieren kommt es immer darauf an, dass die verfügbaren Tags richtig interpretiert und dann gewichtet werden. Beim navigieren kommt es ja nicht immer darauf an den kürzesten zulässigen Weg zu finden. Manchmal möchte man auch den schnellsten/schönsten Weg haben.
Und OSMAND wie auch andere Vektorkarten werten einfach nur den für sie relavanten Teilbereich der Keys aus. Möglicherweise wird dann auch gleich noch ein “Mittelwert” berechnet, um dann nicht die “ganze Arbeit” im Mobildevice zu machen.
Daher wird es schon grundlegende Unterschiede geben. Zumal sich rd5 eben gerade nicht um Darstellbarkeit und aussehen kümmert.

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).