Offline routing engine

[HarelM]

I'm passively looking into a solution for my need for an offline routing engine. My research can be read here: https://github.com/IsraelHikingMap/Site/issues/1636 Generally speaking the following are my requirements:

1. I should be able to run this routing engine in Android and iOS, or using Ionic capacitor/webview (pure javascript/WASM)
2. This routing engine should allow profiles, my use case is: Hike, Bike, 4 wheel drive profiles
3. The results from the routing engine should have elevation data
4. The setup time should be minimal - preferably using a pre-process step where the data is saved in a format the routing engine can read fast
5. [Optional] If the routing engine can receive RGB Terrain tiles and MVT tiles and create a route using this input the need for a dedicated file might not be necessary as I have this data available offline/in memory/cached.
6. [Optional] Allow running this on a server using a docker container to allow similar results when doing the routing while offline and while online

My current setup: We are maintaining a docker image of GraphHopper here: https://github.com/IsraelHikingMap/graphhopper-docker-image-push This image can do two things mainly:

1. Download an OSM pbf file and create a directory, this directory has the graph data in a format graphhopper can read fast
2. Serve a routing endpoint on the server

What we do is basically run every hour a build of the graph directory and restart a container to use the newly created graph directory (there is another container that runs in parallel to avoid a time where this service is unavailable).

I thinks this concept is a solid one - you pre-process the data without affecting anyone, once the data is processed you can read it fast and use it fast for the routing engine. If such a directory/file can be made available to download and use on the client device (using fetch, or a native file transfer) it would be great.

I'll be happy to help although I have little to no knowledge in Rust, but after using my app in a two days hike where I needed this offline routing feature I've matured to the point where this is probably the next thing for me to invest in.

As a side note, there's a format I read somewhere called openLR which might be interesting to look into for this package: https://github.com/itinero/OpenLR

This what I can see as a full implementation, having said that, it might be good to start with a "poor man's routing" where things just snap to a route while you are offline (some kind of fallback) and later on make it better, or not. I have the same concept when it comes to search where the search in the backend is using elasticsearch and when offline I use minisearch.

Main project in Github: https://github.com/IsraelHikingMap/Site Website: https://israelhiking.osm.org.il/

[dabreegster]

Sorry for the delay here! This could be a really neat application of the idea, let's see...

I should be able to run this routing engine in Android and iOS, or using Ionic capacitor/webview (pure javascript/WASM)

I've done nothing at all on Android or iOS, but think Rust compiles to them. I've used JS + WASM on an Android in the browser before, so at least that works.

The results from the routing engine should have elevation data

Currently, the pre-built binary graph file contains very little data per edge, just the points really: https://github.com/dabreegster/route_snapper/blob/main/route-snapper-graph/src/lib.rs

For my first use case of this tool, keeping the files small is important (and that's probably true for anyone). Elevation data would be an extra unsigned integer (maybe rounded meters?) or float per node or per edge (rise/fall)? Maybe we can add one arbitrary numeric attribute per node or edge, and skip serializing it for cases where it's unused.

This routing engine should allow profiles, my use case is: Hike, Bike, 4 wheel drive profiles

I can think of a few ways to implement this:

• a separate graph file per profile, which probably triples file/memory requirements
• storing a bunch of attributes per edge (like OSM highway type, surface tags, etc) and evaluating the cost function dynamically off of those. Very very space and time inefficient
• preprocessing edge weights for each profile, using whatever input

I would lean towards the 1st or 3rd option. All of the work happens offline, when you build the graph from whatever source -- probably still using graphhopper. In other words, maybe we should just take whatever graphhopper's output file format is, and make it work here.

Another question/concern: how large are the areas you're routing? If you try the route tool at https://atip.uk/scheme.html?authority=Greater%20London, it's very sluggish. It's just doing A*. I'm considering #6 for larger areas, but there are initial loading tradeoffs here.

[dabreegster]

Also, your website already has the "frontend" logic for dragging points, rendering, etc. The bulk of this codebase is just doing that right now. If you're happy with your current implementation of it, then I would say the spirit of this codebase might help more than the actual code. Maybe some steps would be:

1) Take the current graphhopper graphs you're building (which have elevation data and good weights for the 3 profiles already?) and serialize them in a very compact format -- three weights per edge, and the line-string 2) Wire that up to any pathfinding implementation that can run in the browser. No need for it to be Rust at all; https://github.com/anvaka/ngraph.path might be a good thing to try

[HarelM]

I don't know the internals of the graphhopper format that is saved to a file, so reverse engineer it might take more time to research than writing something that can do the routing, IDK... I'm not very familiar with all the theory around path finding etc...