BRouter: offline Fahrrad-Routing für Android

…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…

Nein, gilt eigentlich immer noch, auch wenn die VMs besser geworden sind.

“There are lies, damn lies and Benchmarks”
http://www.freewebs.com/godaves/javabench_revisited/

Bei NestedLoop ist C++ dort 50x so schnell, aber auch sonst
bis auf eine Ausnahme immer führend.

Sicherlich gibt es auch flotte Java-Programme. Manchmal überraschend schnell.
OsmAnd fand ich aber extrem langsam, wenn es mangels Native-Libraries
auf Java zurückfällt.

In C lässt sich eben der Prozessor am besten kontrollieren, fast wie in Assembler.
Auch die neuen Prozessor-Features sind über Intrinsics bzw. Inline-Assembler ohne
Overhead nutzbar (SSE, AVX). Wichtig ist das in der schnellen Signalverarbeitung.

Du solltest nochmal aufmerksam lesen in dem Test lese ich sun Java 1.4 und 1.5
zu Java 1.4: http://www.oracle.com/technetwork/java/javase/index-jsp-138567.html
und Java 1.5 entspricht wohl Java 5 welches laut Wikipedia auch schon im Jahr 2004 das Licht der Welt erblickte:
http://de.wikipedia.org/wiki/Java-Technologie#Version_5.0

Das entspricht dann in etwa den 10 Jahren die Nop hier ansprach.
Ach wenn man ganz ans Ende scrollt sieht man ja auch das Jahr 2004. Übrigens wenn du genau schaust unterscheiden sich g++ und Intel und es gibt Disziplinen das ist Java beiden überlegen.

Wenn Du 2km zum Bäcker fährst merkst Du das normalerweise auch nicht, aber bei längeren Strecken siehst Du schon den Effekt zwischen OsmAnds “ab durch die Mitte” und BRouters “vielleicht doch besser aussen rum”. Obwohl ich auch bei kurzen Strecken bei OsmAnd offline oft Effekte sehe, wo man sich denkt, warum, jetzt dieser Zacken durch die Wohngebiete, der direkte Weg geht eindeutig da lang.

Zu der C++ ↔ Java Diskussion, Die du da angestossen hast, äussere ich mich nicht als jemand, der mit Java sein Geld verdient, weil die Diskussion ist einfach sinnlos, in der Praxis machen die Daten-Modelle und die Algorithmen den Unterschied, die Technologie kann das nicht reissen, und insofern ist Victors Ansatz mit den nativen libs aus meiner Sicht ein Irrweg.

Nahmd,

Danke, oder auf neudeutsch: +1

Du hast mir die Worte aus dem Mund genommen.

Gruß Wolf

Frei nach Churchill: Ich glaube nur den Benchmarks, die ich selber gefälscht habe.
Es lassen sich immer Probleme finden, die sich mit einer Sprache besser lösen lassen wie in einer anderen.
Auf die Spitze treiben das die Grafikkarten-Hersteller, die den Micrcode für ihre Grafikprozessoren auf die momentan gängigen Benchmarks hin optimieren, auch wenn das im Normalbetrieb eher Nachteile bringt.

Generell ist Java eine interpretierte, C/C++ eine compilierte Sprache. Daher rührten die Laufzeitunterschiede zu Beginn vor allem her. Heute gibt es JIT-Compiler zu Java, die den Code zur Laufzeit zumindest lokal auch optimieren können. Da der meiste Rechenaufwand üblicherweise in engen Schleifen verbraten wird, hat sich der Unterschied damit drastisch verringert.
Global kann aber nur eine compilierte Sprache optimieren. Welchen Anteil das an der Rechenzeit hat und ob der C+±Compiler das auch tut, ist wieder eine andere Frage.
Wenn es um Bitfieseleien geht, ist Java klar unterlegen (dafür wurde es aber auch nicht entworfen).

Die meiste Zeit drehen die üblichen Anwendungen aber sowieso Däumchen und warten auf eine Reaktion des Benutzers. Der kann dann auch nicht unterscheiden, ob die Reaktion auf einen Klick in einer Hunderstel oder Tausendstel Sekunde erfolgt.

Zusatz: Einen lausigen Algorithmus rettet auch eine “schnellere” Sprache nicht. Beim selben Algorithmus kann es aber sehr wohl Unterschiede geben. Ob die aber so groß sind, dass sich der erheblich größere Aufwand für eine “Mischtechnologie” (Einbinden von native code) lohnt, ist fraglich.
Am schnellsten wäre sicher Assembler, aber das tut sich doch wohl keiner an.

Nop hatte halt den 2004er Benchmark zitiert, und der “revisited” Benchmark war die Antwort darauf.

Es ist halt schwierig mit Benchmarks zu argumentieren. In der Praxis kommt es noch auf viele andere Dinge an.
Der Android-Kernel ist nicht umsonst in C geschrieben. Jede Sprache hat eben so ihre Anwendungsdomäne.
Java ist für bestimmte Anwendungen auch gut geeignet, z.B. da wo es auf Betriebssicherheit ankommt.
Mit C sind viele systemnahe Tricks möglich, wird gerne mit Pointern operiert und der Speicher selbst
verwaltet. Das ist gut für die Performance (wenn man es richtig macht), birgt aber das Risiko bösartiger
Crashes. Man kann in C++ auch gut ohne Pointer sauber programmieren.
Es lässt einem die totale Freiheit, entweder systemnah mit Assembler-Inlines, Intrinsics
für SSE/AVX, oder ganz abstrakt mit Objekten und Templates.

Schön in C++ ist das Overloading der mathematischen Operatoren + - *, so dass man auch
mit komplexen Zahlen, Matrizen und Vektoren einfach rechnen kann. Komplizierte Formeln
sehen dann im Programmcode so übersichtlich aus wie im Lehrbuch. Der Code wird dadurch sehr
viel leserlicher als in Java oder C. Das hat mich bisher davon abgehalten, auf Java oder Python
umzusteigen, obwohl die natürlich auch viele Vorteile bieten.
Früher waren sie immer bei ihrer mächtigen Systembibliothek überlegen. Mit
BOOST hat C++ mittlerweile gut aufgeholt. Das ist schon eine sehr komfortable
Unterstützung für viele Dinge, die man früher noch mühsam selbst programmieren musste.

Aber natürlich kann der beste Compiler oder die beste Sprache nicht helfen, wenn der
Algorithmus oder die Programmlogik nicht optimiert wird.
Das wichtigste Optimierungsorgan ist immer noch das Gehirn des Programmierers.

Meinst du damit den Linux-Kernel? Klar ist der nicht in Java geschrieben, weil es Java damals noch nicht gab (1991 vs. 1995). Ausserdem bräuchte man für eine Java-VM erstmal ein Betriebssystem darunter…
Oder meinst du Dalvik? Die lässt sich auch schlecht in Java schreiben, weil sie notwendig ist um Java-Anwendungen auszuführen. Wenn sie selbst eine Java-VM bräuchte bräuchte man sie ja nicht mehr.

Und ob C++, C, Java, Assembler oder Brainfuck “lesbarer” ist hängt ja wohl von den Wünschen des Lesenden ab.

BTT: Könnte jemand dazu eine Seite im OSM-Wiki mit ein paar Infos und einer Kurzanleitung anlegen?

Dann probiere OsmAnd mal ohne die native Libs. Bei mir lief das elendig langsam.

Warum kein Assembler? In C++ kannst du in einer Hochsprache schreiben und für ein paar kritische
Dinge Inline-Assembler einschieben. Hab ich schon öfters gemacht. Nur so lassen sich inkompatible
Aufrufkonventionen fremder C++ DLLs handhaben. Besonders aufwendig ist das auch nicht.
Einige Bitschubsereien sind in Hochsprachen extrem ineffizient, selbst in C.
Außerdem, wozu hat man so tolle Prozessoren mit AVX und SSE-Vektoreinheiten, wenn
man sie brach liegen lässt? Was meinst du was da für Speedups verschenkt werden.
Das ist locker mal Faktor 10-20 drin für die schnelle Bildverarbeitung.
In C++ lässt sich das ad-hoc mit intrinsic functions einbetten. Die Möglichkeiten bietet Java nicht.

Nein, es geht auch ohne VM:
http://de.wikipedia.org/wiki/Java-Prozessor

Aber ich denke auch heute würde man den Kernel wieder in C schreiben, einfach weil die Sprache
dafür wie geschaffen ist. Es geht teilweise um sehr harte Echtzeitanforderungen, volle Kontrolle
über Speicher und System, Inline-Assembler. Womit soll denn das sonst gehen?

Wenn auf einen System-Interrupt in wenigen Taktzyklen geantwortet werden soll,
kann eine VM nicht zwischendurch gemütlich noch eine Garbage Collection machen.

So, ich glaube wird sind jetzt zu off-topic … für BRouter ist Java natürlich eine exzellente Wahl :slight_smile:

Zugegeben, auf längeren Touren (z.B. 70 km), habe ich noch keinen automatischen Router benutzt. Da stecken einfach zu viele persönliche Vorlieben drin, die eine Software nicht kennt und auch schlecht durch OSM-Tags ausgedrückt werden können. Nicht zu vergessen in der Routing-Metrik sind auch die Einkehrmöglichkeiten. Bisher hat mich noch keine Routing-App gefragt, ob ich lieber zum indischen Restaurant gehe oder doch zum Italiener (beide als OSM-POI im Kartenmaterial). Dazu kommen noch dynamische Probleme. Die Route und Einkehrmöglichkeiten werden soweit mit dem Regenradar verknüpft, dass man pünktlich zur großen Regenschauer im Lieblingsrestaurant sitzt und danach wieder trocken weiterfahren kann. Erstaunlich, aber es hatte im ersten Versuch funktioniert (auch dank der guten Regenradar-App von wetteronline). Als Routing-Engine habe ich dazu ein größeres neuronales Netz am laufen.

Meine längste geführte Radstrecke mit OsmAnd war ca. 30 km. An sich wäre die Strecke Ok gewesen, wenn es nicht wieder über die Berge gehen würde, die ich auf der Rücktour übers Tal vermeiden wollte.

Die von dir beschriebenen Zacken sind mir noch nicht aufgefallen. Aber manchmal kam es vor, dass partout ein bestimmter Weg verweigert wurde, auch als ich schon kurz davor stand. Einmal (pedestrian mode) habe ich versucht, in JOSM dafür eine Erklärung zu finden, aber es war alles richtig vernetzt, die Nodes verknüpft, der Weg als begehbarer Pfad getaggt. Keine Ahnung. Vielleicht habe ich die Verbots-Schemata nicht verstanden oder es war ein Bug in OsmAnd.

Kommt der Eindruck “vielleicht doch besser aussen rum” vielleicht durch eine andere Metrik zustande? Indem bestimmte Wege einfach bevorzugt werden? In BRouter war mir positiv aufgefallen, dass es einen langen ehemaligen Bahntrassenweg bevorzugt hatte, obwohl es ein tolerierbarer Umweg war. Eigentlich genau das, was man sich als Fahrradfahrer wünscht (wird doch in der Metrik stärker gewichtet, oder?).

Ich hab Dir auch drei konkrete Positiv-Beispiele genannt - die hast Du bloß untern Tisch fallen lassen. :slight_smile:

Bei der Grundgeschwindigkeit gibt es keinen nennenswerten Unterschied mehr. Das Problem sind nur die Programmierer, die es sich leicht machen und die teuersten Luxusklassen ohne Nachzudenken einsetzen. Java macht das einem leicht, weil es so viele schöne libs gibt. Aber in C kriegt man dasselbe z.B. mit Boost auch locker hin. Letztendlich entscheidet ob sich der Autor was dabei gedacht hat.

bye, Nop

So etwas hätte ich auch gerne.

Erst kürzlich gab es einen Blogeintrag zu externen Datenquellen in OSRM mit ähnlicher Thematik: Biking Directions With OSRM’s New External Data Support. Im Beispiel wird eine zusätzliche PostGIS Datenbank mit Imposm Schema verwendet, um Wege innerhalb oder in der Nähe eines Industriegebiets schlechter zu bewerten.

Dann noch Routing über Flächen und Arndt wird es im Winter nicht langweilig :wink:

Gruß,
Norbert

Ruhige Industriegebiete sind mir aber noch lieber als stark befahrene Hauptstraßen,
auch wenn da noch so ein toller “Radfernwanderweg” durch geht oder der Fahrradweg super ausgebaut ist.
Der Straßenlärm geht mir am meisten auf die Nerven.

Weiterhin mag ich ampelfreie Routen, z.B. am Fluß entlang, wo man mal so richtig
Gas geben kann und durch nichts aufgehalten wird.

Ein Rad-Router ist deutlich komplexer als ein Automobil-Router.

Eigentlich geht es nur mit “Persönlichkeitsprofilen”, also ein langes Interview
zu Beginn "fährst du gerne durch Wälder?, “wäre ein bisschen Matsch ein Problem für den Sonntagsrad?”,
“brauchst du Asphalt oder hast du richtige Reifen?”, “lieber die Strecke mit den hübschen Joggerinnen?” …

Und für jede Person kann man weiter differenzieren
Profil “will schnell nach Hause”, “habe Zeit für die Natur”, “heute mal sportlicher” …

Aber bei all den Fortschritten: es ist auch schön, mal ohne Karte und Navi rauszufahren
und sich überraschen zu lassen.