Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Future of 'Offline' Routing #1940

Closed
karussell opened this issue Feb 28, 2020 · 33 comments
Closed

Future of 'Offline' Routing #1940

karussell opened this issue Feb 28, 2020 · 33 comments
Milestone

Comments

@karussell
Copy link
Member

karussell commented Feb 28, 2020

The current state of routing on mobile devices (iOS & Android) without internet access (aka "offline routing") is suboptimal:

I am really happy that despite these limitations I know there are apps in the app stores that use GraphHopper for offline routing (Android and iOS).

And still, we are struggling to continue supporting this as we have to limit ourselves and avoid updating dependencies (see e.g. #1803), stick to Java 7 in the core and also many dependency issues when it comes to Jackson and its annotations and many more design decisions that would be less complicates without "Android Java" in mind. Also there will be inline types in Java, which are already available as experimental feature in JDK 14, which it will be hard to avoid in the core. Previously we have accepted this and I've done lots of testing for Android myself and invested time or provided the map data and apks, but this does not make much sense as I have no real Android- or "app store"-experience. Additionally it is effort that I'm no longer willing to invest.

I see the following options:

  1. we abandon offline routing and embrace the latest server side Java version in GraphHopper
  2. we make it worth to limit ourselves in the core (i.e. implement the missing "production" features and update the iOS port and have real community involvement for this like we already have for other things)
  3. make native GraphHopper working for mobile devices too (GraalVM native image likely combined with Gluon tools). For iOS see also Add iOS support to Substrate VM oracle/graal#373. This is currently not usable: even a simple HelloWorld is hard to compile. (could work together with option 1). See update.
  4. a special Android fork of GraphHopper (suggested from @develar; could also work together with option 1)

If no one steps up for contribution in this area in the next months (see for concrete tasks in option 2), then I'm afraid that we'll have to go for option 1 and drop explicit support for Android offline routing (it might still work).

So, if you use GraphHopper for offline routing, now it is the right time to contribute :) ! (@devemux86, @develar, @menion, @johnpercy, @Starcommander)

@develar
Copy link

develar commented Feb 28, 2020 via email

@karussell
Copy link
Member Author

So, I will be interested in contributing at least several years (or maintainting special version of graphhopper)

Ah, yes, it would be also an interesting option to create a fork with the focus for Android.

Maybe I am wrong, but Jackson not required for routing. Anyway, I will contribute ifit will be a problem

We will soon start supporting custom weighting #1841 and already have spatial rules that need jackson. At the moment we found ways and avoided jackson in core, but this makes things complicated and more work. E.g. special "mixin classes" are required as we avoided annotations in the core and more.

My daughter 6 years old.

btw: What did you mean here :) ?

Kotlin already supports inline classes

I think this is something different. The "inline types" (previously called "value types") is a mechanism that will make many data structures more memory-efficient and likely also speed up parts of the system. It is not yet in a stable JVM, but you can try it already - see the link above.

@develar
Copy link

develar commented Feb 29, 2020 via email

@karussell
Copy link
Member Author

It is understandable that GraphHopper organization's focus is now the web platform and API

This is not about the focus of the GraphHopper company, it is about the community. Have a look into the open and merged pull requests for 1.0 to understand that the community is fortunately much bigger than the company now :)

We invite everyone to contribute and shape what the GraphHopper routing engine is able to do.

And even if we abandon "offline routing" for 2.0 it doesn't mean we'll reject future contributions e.g. due to a generous sponsor or a community effort. My personal opinion is still that we want and need this feature, but without a single contributor that has production experience in this area this won't happen.

and Kurviger servers

I appreciate that but this does not really help as it is not open source (there are many closed source offline routing apps)

@menion
Copy link

menion commented Feb 29, 2020

Hello guys,
thanks Peter for bringing this serious question to the public.

We (the tiny team behind Locus) are just now (exactly this month) trying to decide if offline routing integrated directly in the app is doable or not. And to be true, I was, before your post, quite close to say: "Yes, let's go with GraphHopper solution".

The contribution is a problematic question for me. Emux knows very well that I still have a huge unpaid debt to MapsForge library. But because I'm still the only Android dev behind Locus Map, I'm pushing it before me :/. I want to say, that if I finally find time to contribute back, the MapsForge project is a must for me.

The best what we (as Asamm team) do now is using GH as a paid online routing service instead of the self-hosted solution. I can also imagine other financial support, if there will be a chance to work on the offline routing system.

Anyway, I perfectly understand the big limitation that the Android system is, compared to the server environment. Positive for me is

And even if we abandon "offline routing" for 2.0 it doesn't mean we'll reject future contributions e.g. due to a generous sponsor or a community effort. My personal opinion is still that we want and need this feature, but without a single contributor that has production experience in this area, this won't happen.
It may motivate, not just me, to be more Android-active in the future :).

And definitely agree with @develar that Kotlin is a huge improvement in many areas and definitely a good way at least to try it.

Last thing: from a list of options believe that option 1, later combined with 4 is a way to go.
Thanks Peter for this amazing project!

@otbutz
Copy link
Contributor

otbutz commented Mar 2, 2020

My two cents:

  • Option 1: my employer is only using GH as a library, so it would be ok for us. But i think we should keep support for offline routing on Android if it's feasible
  • Option 2: Sticking to Java 7 is an anachronism IMHO
  • Option 3: possible
  • Option 4: Makes sense as Android is slowly moving away from Java

I'd prefer option 3 or 4 to be honest.

Switching to Kotlin would be a complete deal breaker for anyone who is embedding Graphopper into their Java application.

@Starcommander
Copy link

I still prefer to support offline routing.
It is used in our Pocketmaps android-app that I still keep up to date.
(on f-droid and play-store)
We should not abandon offline routing completely, at least for an android fork.

@easbar
Copy link
Member

easbar commented Mar 3, 2020

I asked this question before here #1803 (comment):

Let's say we migrate GH core to Java 8 (this would already be an improvement, because of Jackson and JTS for example, lambdas would also be nice but not as critical). Would it be possible to compile GH to java 6 bytecode (to be able to support older android versions) using the Kotlin compiler? So far the only argument I heard against this was that this requires adding the Kotlin stdlib as runtime dependency to the android app. Has anybody tried this yet? Tbh unless this really causes a critical issue the (imo valid) argument that generally its better to limit the number of dependencies in your app does not really seem to be reason enough not to upgrade GH core to Java 8 to me.

Or maybe to put it the other way around: Let's say GH core upgrades to Java 8 would the GH android devs rather maintain their own GH fork or use the Kotlin compiler (and add the necessary dependencies) (assuming this works)?

Java Value Types might be another story (not sure if the same approach works when upgrading GH core to something > Java 8)?

@menion
Copy link

menion commented Mar 3, 2020

And here comes Kotlin to rescue to bring some nice features of higher Java version directly for older Android devices.

Support for Android 4.x is nice, anyway where here will be some discussion about this, my vote is that 4.x platform is dead and 5+ is way to go. Anyway, it's a little bit offtopic now.

From my perspective: if Peter & HG team search for easier writing & testing with the help of modern language features, I believe that Kontlin is the best choice that also allows to more "easily" keep Android flavor. If there are anyway bigger changes in Java bytecode that has a major impact on performance, it is of course problem, because Android is and will be for a long time, stuck on the older Java version.

So @easbar if you migrate GH to Java 8, it won't be 100% compatible with Android as @devemux86 correctly wrote. There are some limitations, but all are solvable I believe. With Kotlin, it should be 10% compatible ;).

@easbar
Copy link
Member

easbar commented Mar 3, 2020

By the way OkHttp forced some changes in latest versions and several developers didn't like that:
square/okhttp#4481
square/okhttp#4723
Also many Android developers still prefer Java 7 in apps and dependencies for compatibility reasons. Since D8 dexer (until becomes mandatory) leaded to installation problems in older devices.
Personally I still keep the whole Mapsforge ecosystem in Java 7 to be helpful to all developers out there.

I understand that using Java 7 might lead to less compatibility issues and okhttp users for Android would prefer Java 7. But even if Java 7 was less complicated for Android that does not necessarily say Java 8 would be a real blocker (because it can be compiled to Java 6 or 7 using the Kotlin compiler).

So @easbar if you migrate GH to Java 8, it won't be 100% compatible with Android as @devemux86 correctly wrote. There are some limitations, but all are solvable I believe. With Kotlin, it should be 10% compatible ;).

I am not talking about writing Kotlin code in GH core, but I am wondering if its possible to use (say) Java 8 GH core code, compile it with the Kotlin compiler (which can be configured to produce Java 6 bytecode, but also Java 7 if thats preferred) and then use the resulting bytecode on Android. Does this actually work and if yes why would this not be 100% compatible with Android?

Like @otbutz pointed out writing Kotlin code in GH would force every Java project using GH to use the Kotlin compiler (not sure if this is ok or not, what if GH was using the latest Java version? This would be a similar problem).

@otbutz
Copy link
Contributor

otbutz commented Mar 3, 2020

not sure if this is ok or not, what if GH was using the latest Java version? This would be a similar problem

Upgrading Java versions is one thing but changing the programming language is a complete different story.

@develar
Copy link

develar commented Mar 3, 2020

I am wondering if its possible to use (say) Java 8 GH core code, compile it with the Kotlin compiler (which can be configured to produce Java 6 bytecode, but also Java 7 if thats preferred)

No, Kotlin compiler processes only kotlin files and not java.

changing the programming language is a complete different story.

Kotlin doesn't require you to migrate the whole project at once. You can just use modern language in some places where it does make sense. You can easily use java from kotlin and vice versa. (And then compile for different JVM versions, to JS, to native, to WebAssembly).

If you don't want for some non-technical reasons use modern language, then yeach, forking GH it is the only option (since not just some configuration, but source files will be modified).

what if GH was using the latest Java version

Even if you will be not happy to wait several weeks or months when Kotlin will start to produce a new bytecode (new JVM features, which are not just a syntax sugar), it is still will be better to reduce differences in a fork (I mean — use java for such features).

Like @otbutz pointed out writing Kotlin code in GH would force every Java project using GH to use the Kotlin compiler

No. Kotlin produces regular JAR files. So, just use GH as library in a pure java project, Kotlin compiler is not required.

@easbar
Copy link
Member

easbar commented Mar 3, 2020

No, Kotlin compiler processes only kotlin files and not java.

Ah ok so if I have a project with mixed Java and Kotlin sources (like you mentioned its not required to migrate the project at once) and I want to compile the whole thing to Java 7 bytecode, none of the Java files may contain Java 8 code? And I guess its not (for some reason) feasible to use the java-to-kotlin converter for the entire code base to convert a (hypothetical) Java 8 GH core to kotlin and then compiling it to Java 7 bytecode (using the kotlin compiler)?

No. Kotlin produces regular JAR files. So, just use GH as library in a pure java project, Kotlin compiler is not required.

That's certainly interesting.

@develar
Copy link

develar commented Mar 3, 2020

And I guess its not (for some reason) feasible to use the java-to-kotlin converter for the entire code base to convert a (hypothetical) Java 8 GH core to kotlin and then compiling it to Java 7 bytecode (using the kotlin compiler)?

Do you mean some automatic tool? Yes, that's possible. java-to-kotlin produces compilable and correct code nearly always. Sometimes code doesn't conform to kotlin convention, but in most cases because safety first (avoid semantic changes). But in this case maybe will be better to use https://github.com/luontola/retrolambda

@develar
Copy link

develar commented Mar 3, 2020

@devemux86 Yes, if some stdlib function is used, then additional library is required:

kotlin-stdlib-common 
kotlin-stdlib (you can try to avoid any stdlib usage to get rid of it)
kotlin-stdlib-jdk7 (if JDK 7+ stdlib API is used)
kotlin-stdlib-jdk8 (if JDK 8+ stdlib API is used)

source code — https://github.com/JetBrains/kotlin/tree/master/libraries/stdlib

But question was about compiler, mentioned above JARs "is nothing but a set of libraries ( bundled in a jar) which is referred during runtime, just like any other jar in classpath." (from SO question).

You don't have to use max / setOf and any other functions from stdlib if you want to avoid extra dependencies.

@ironjan
Copy link

ironjan commented Mar 23, 2020

JakeWharton's agp-java-support project may be relevant to this discussion. This project "tracks your ability to use new Java language features in an Android app". Also, his two blog posts about Android's Java 8 Support and Android's Java 9, 10, 11, and 12 Support
.

@Zakalicious
Copy link

Zakalicious commented Apr 12, 2020

@karussell to point 2 in your Feb 28 note.
I am new to the routing scene, so maybe my comment is mute, but I came across this ios-Swift port.
Maybe that leaves room for offline routing?

@karussell
Copy link
Member Author

@Zakalicious this is not a port for offline routing, it is a client that connects via http to a GraphHopper server.

@karussell
Copy link
Member Author

make native GraphHopper working for mobile devices too (GraalVM native image likely combined with Gluon tools). This is currently not usable: even a simple HelloWorld is hard to compile.

This works now (still hard):
https://www.graphhopper.com/blog/2020/04/14/experiments-with-graalvm-native-images-2-2/

@HarelM
Copy link
Contributor

HarelM commented May 25, 2020

I'm also looking for an offline routing solution, but my app is cross platform using Cordova - which is basically writing the code in Java for android and objective-c/swift for iOS and wrapping them with a single interface in javascript allowing a webview to use them.
I was wondering if there's someone else doing a similar plugin?
If this will be available, and upgrading the underlying iOS/Java libraries would not be too hard I can integrate it in my app and make sure this keeps working.

michaz added a commit that referenced this issue Jul 3, 2020
@karussell
Copy link
Member Author

karussell commented Jul 5, 2020

With your input and after some discussion the Android demo app was now removed (see 60a50a9). For me it is a bit heartbreaking as Android support was a nice feature since 0.1 until 1.0, but when I'm honest it never had the highest priority.

Some incompatible changes will follow e.g. moving the core to Java 8 or including certain dependencies (#1803). This means that the latest GraphHopper might no longer work on some older Android devices. We invite everyone who is interested to embrace GraphHopper also for mobile usage to fix these problems and e.g. create a mobile-ready fork (i.e. option 4). Also contributions like tile-based storage or similar would be really nice to have. But without contributions and actual usage & feedback from mobile developers we cannot continue to have these restrictions in the core.

@karussell
Copy link
Member Author

As indicated above I won't further maintain Android compatibility (even if it would break on the latest Android version). This needs to come from someone else that really uses, tests and pushes GraphHopper on Android. Maybe you or you know someone who can push it forward :) ?

Maybe a fork is required, but if changes are needed towards the core like a new DataAccess type or algorithms or similar, then I will try to help to get this merged.

@vshcherb
Copy link

@karussell Sorry if I missed something, we (OsmAnd) still consider some kind of integration and work investment as well.
I would like to know if you made any progress on:

  • Splitting routing into several files and possibly hints which regions are missing.
    Imagine we will generate 1 planet file and we would like to split it by boundaries, so user can download several countries and try to build a route and get an error if something is missing. I think it's not only related to offline routing but could be also a feature for online routing.
  • Make update files somehow compatible.
    It might be even bigger problem, users want to download Europe maps as whole but they don't want to spend each month a lot of traffic, they would like to update only their region.

I believe every offline usage will encounter these 2 main issues. So, I think it's good to see the vision of web online version whether they are going to support these features in order to make right decision how the engine would be usable on Android / iOS.
Please correct me if I'm wrong.

@easbar
Copy link
Member

easbar commented Jan 10, 2021

and get an error if something is missing

Under which circumstances do you expect an error?

  1. in case the origin or destination of the route is located outside of the downloaded regions? Or also
  2. in case origin and destination are within the downloaded area, but the best route would require leaving (and entering again) the downloaded area?

The first case 1) is already possible more or less, because if the points are two far away from the road network of the downloaded area there will either be an error already or if not you could simply throw an error depending on the snapping distance. 2) is not possible and I also do not think this can be done at all. How would you know there is such a route without knowing the roads outside of the downloaded area? Unless of course you do an online request, but this defeats the purpose of offline routing.

Your other requirement seems to be adding additional data to or updating the existing graph. Neither of these two things are implemented at the moment, but in principle this is possible I think.

@vshcherb
Copy link

Well, I think 1 requirement could be simplified.
If we have offline files for 1 December and neighbor region for 1st January, obviously we can't build a route between these regions. We can obviously request user to redownload regions to make them consistent though we need to know for which route which offline files are needed.
Obviously we need to determine only that routing is not possible and in that case we can make an online route anyway to understand which files are required to be updated.

So main requirement I think only one, be able to split 1 world folder to multiple folders by list of *.poly files. So graphhopper engine could work on collection of graphs (which are simple cuts of the main world graph)

@boldtrn
Copy link
Member

boldtrn commented Jan 11, 2021

@vshcherb routing across multiple graphs is currently not supported, see: #293

@HarelM
Copy link
Contributor

HarelM commented Mar 1, 2021

@andreddosantos Do you have a plugin that can be tested? Can you share a link?

@andreddosantos
Copy link

@HarelM Unfortunately it's not public yet. It might be in the future.

But all we did was a simple encapsulation of the sample apps examples within a cordova plugin. For android was easier than iOS, cause all depencies are installed with the plugin automatically, regarding iOS, we included some manual steps like the ones described in the ios example branch.

We then added some parameters that the plugin receives for both platforms:

  • Start and end point;
  • Route optimization flag (functionality achieved using jspirit - only for android);
  • Blocked areas;
  • Vehicle;

Once the route is obtain, the navigation functionality was developed using JS and the device GPS.

@HarelM
Copy link
Contributor

HarelM commented Mar 1, 2021

Thanks for the quick response! If you happen to make this effort public it would be great :-) I think we see it the same - i.e. use the plugin to get a route into the js code and from then on use js code to present it.
I might be able to contribute if this code is public, if not coding then at least testing.

@karussell
Copy link
Member Author

karussell commented Jun 5, 2023

I recently discovered a rather simple possibility to install GraphHopper for offline routing on Android:

  • install the UserLAnd app. From my understanding an advanced termux setup so probably the following is also possible with termux.
  • install and start Alpine Linux
  • inside a new Alpine Linux session install a real JDK for Linux and ARM. In my case I had to slightly tweak the installation command: apk add --no-cache openjdk8. Or download&extract the JDK for Linux and ARM (or better use the JRE as it is smaller)
  • follow the normal GraphHopper installation. If the import process is too heavy for your device you can still copy over the graph folder created on your desktop.
  • access the GraphHopper server via any Android browser at localhost:8989!

grafik

grafik

The following was surprising / impressive to me:

  • the simplicity of the entire process (everything was up and running within ~10 minutes and no rooting required)
  • you can even do the import right on the device (and it import was only 50% slower than my laptop)
  • you can use this for any other Java or even Linux application!
  • and probably most importantly: there are no RAM limits like with the normal Android VM! I was able to easily use all the RAM my phone gives :)

There are only 2 downsides: 1. UserLAnd does not seem to be active anymore but as I said there is termux and then there is also andronix.app which might solve this. 2. You will need additional storage for UserLAnd, Alpine Linux and the JDK. But if you use this for other applications then the ~150MB should be acceptable.

@chexo3
Copy link

chexo3 commented Oct 10, 2023

I recently discovered a rather simple possibility to install GraphHopper for offline routing on Android:

  • install the UserLAnd app. From my understanding an advanced termux setup so probably the following is also possible with termux.
  • install and start Alpine Linux
  • inside a new Alpine Linux session install a real JDK for Linux and ARM. In my case I had to slightly tweak the installation command: apk add --no-cache openjdk8. Or download&extract the JDK for Linux and ARM (or better use the JRE as it is smaller)
  • follow the normal GraphHopper installation. If the import process is too heavy for your device you can still copy over the graph folder created on your desktop.
  • access the GraphHopper server via any Android browser at localhost:8989!

grafik

grafik

The following was surprising / impressive to me:

  • the simplicity of the entire process (everything was up and running within ~10 minutes and no rooting required)
  • you can even do the import right on the device (and it import was only 50% slower than my laptop)
  • you can use this for any other Java or even Linux application!
  • and probably most importantly: there are no RAM limits like with the normal Android VM! I was able to easily use all the RAM my phone gives :)

There are only 2 downsides: 1. UserLAnd does not seem to be active anymore but as I said there is termux and then there is also andronix.app which might solve this. 1. You will need additional storage for UserLAnd, Alpine Linux and the JDK. But if you use this for other applications then the ~150MB should be acceptable.

Wait, so just to be clear, I can set up GraphHopper to use graphs generated on a more powerful device, and then import the relevant sections of those graphs in order to do routing on a lower power device?

I was thinking about using GraphHopper in the context of e.g. a custom car head unit, or on a Linux phone with very limited memory. What’s the memory usage like for routing (assuming you have the graphs from somewhere else already)?

@karussell
Copy link
Member Author

I can set up GraphHopper to use graphs generated on a more powerful device, and then import the relevant sections of those graphs in order to do routing on a lower power device?

Yes, this is the idea. Although my comment was about doing the full import on the (rather powerful) phone too. UserLand allows you to use a Linux distribution on an Android phone, which makes it possible to use a real JVM and not the heavily trimmed Android JVM. And with a real JVM every function is available and you can do the import.

I was thinking about using GraphHopper in the context of e.g. a custom car head unit, or on a Linux phone with very limited memory. What’s the memory usage like for routing (assuming you have the graphs from somewhere else already)?

You can use memory mapping and contraction hierarchy. The memory usage then still depends on the route length. You'll have to try this out if it fits your use case. But the tricky thing is often to get a JVM for the Linux phone, although these days there are some ARM packaged JVMs or even the possibility to use a native package GraphHopper with GraalVM.

@lalebarde
Copy link

lalebarde commented Nov 9, 2024

I have been successfull too installing GH locally under Termux and link it to Osmand~ as an on-line router. As my smartphone has a very small screen and low resources, I prepare the graph-cache, config.yml and custom profiles on my PC and transfer them to the smartphone with scp after having launched sshd under Termux.

On the smartphone:

  • Install F-Droid from the store
  • From F-Droid, install Termux and Osmand~
  • Then from Termux:
pkg update && pkg upgrade
pkg install git openssh termux-auth openjdk-17
sshd
whoami
ip addr show wlan0

From the PC terminal, just ssh and after it is like going on on the smartphone (replace 'your password', xxx, and yyy) by yours (xxx obtained with whoami, yyy with ip addr show wlan0:

sshpass -p 'your password' ssh -p 8022 [email protected]
mkdir graphhopper && cd graphhopper
mkdir custom_models
mkdir -p your_continent/your_country

Then from the PC itself, after having prapared the graph_cache with the same version of GH:

sshpass -p 'your password' scp -r -P 8022 graphhopper-web-9.1.jar [email protected]:~/graphhopper/
sshpass -p 'your password' scp -r -P 8022 graph-cache [email protected]:~/graphhopper/
sshpass -p 'your password' scp -r -P 8022 config.yml [email protected]:~/graphhopper/
sshpass -p 'your password' scp -r -P 8022 custom_models/euc.json [email protected]:~/graphhopper/custom_models/
sshpass -p 'your password' scp -r -P 8022 your_continent/your_country/my_area-latest.osm.pbf [email protected]:~/graphhopper/your_continent/your_country/

Then on the smartphone or via ssh (Xms and Xmx are RAM allocations to GH, min & max):

java -Xms512m -Xmx1024m -jar *.jar server config.yml

Last step is to add your customed GH profile in Osmand~, select on-line, select custom, input your GH profile (name of your json), set the URL to http://localhost:8989 corresponding to my config.yml (the one included as example):

server:
  application_connectors:
  - type: http
    port: 8989
    bind_host: localhost

The specific part is here (my use case is EUC):

  profiles:
    - name: euc
      weighting: custom
      custom_model_files: [euc.json] 
      hints:
        vehicle: bike 

For my customed profile, here are my attempts.

Kudos to mistral.ai for its great help.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests