Implementing Valhalla Graph Tiles for Overture maps

[thehoneymad]

I have initial thoughts and would prefer to initiate a discussion.

Primary Goal: Develop an Overture-powered routing engine utilizing Valhalla, starting with the creation of Valhalla graph tiles from Overture data.

Why?

1. Learning and engaging in a passion project.
2. Enabling the use of Overture's data across different systems.

Why am I here?:

My inquiries mainly revolve around the question, "Can I achieve this with cov-tiles, given my limited knowledge?"

1. I aim to transition Valhalla's tile specification to cov-tiles. Valhalla tiles contain a compact adjacency matrix, and I want to determine if I can generate a similar tileset using cov-tiles specifications.
2. I aspire to create a tileset that supports non-mercator tiles, as Valhalla tiles do. Is this achievable with cov-tiles?
3. Additionally, I seek to include the clipped route geometry in cov-tiles. This would allow fetching the relaxed route from the tiles after route calculation.
4. I wish to incorporate layers with metadata, such as elevation, into the tileset.

Time commitments:

I can do 1 day in a week. I know that is not much. But it's a start.

[nyurik]

Thanks, I am so happy to see you joining this effort! So speaking from a limited knowledge of the COVTiles, the actual projection should not matter much, as long as we keep the fundamental concept of the MVT tile intact -- each tile has no knowledge of its location in the world, zoom, or projection. A tile is simply a square grid, where each point is represented by a pair of integers. The rest of the info (position/zoom/projection) will be stored by the tile packaging, e.g. mbtiles/pmtiles, or described by tilejson and thus known to the renderer before it requests a tile. Note that technically the grid does not have to be integer based, but I suspect it will greatly improve storage requirements.

[mactrem]

Hi Swagata, nice to hear from you again.

Currently COVTiles is mainly optimized for the visualization use case and not for routing.
Theoretically it could be used to store routing information for example based on a adjacency list.
But to minimize the tile size and decoding performance some adaptions would be needed.
In general routing tiles could benefit from the same ideas COVTiles is build on like using lighweight compression schemes for coordiantes or attributes and fast vectorized decoding into a in-meory model which is then used to calculate the route.

Can you give a little background which informations (e.g. for the costing) you want to store and how the structure of the (in-memory) data model could look like?
Based on this information we could figure out if and how COVTiles can be adapted for your needs.

[thehoneymad]

@mactrem, Hey!

Graph tiles have been implemented differently in different open source routing engines. To summarize, the minimum information needed for a route tile is the subgraph associated in that region with that tile. If it's a basic point-to-point route, you don't necessarily need the route geometry, but having reduces the need to fetch the geometry to produce a final route. These routes have an adjacency matrix with all outbound or inbound edges. If the adjacency matrix does not have the desired destination, by default it picks the outbound edges. This is where heuristics gets useful, to select the outbound edges. Usually a haversine or cartesian direction is used based on the final destination to pick the candidate outbound edge.

There are two big cost families: static and dynamic. Valhalla rocks the dynamic costing, calculating costs on the fly during route computation (thanks, A*!). On the flip side, OSRM and Graphhopper prefer the static cost route.

Then there are part static, part dynamic costing. Such as road size, lane count, speed limits can produce a static costing baked in the tile. The dynamic part comes from historical traffic, elevation, nearly anything someone wants to throw in these tiles.

[thehoneymad]

P.S. My knowledge is heavily reliant on watching youtube videos and reading codes. I have not talked to anyone about this outside my head. And I might have wrong concepts due to just reading code. But I am happy to take the journey because I find it cool.

@mactrem I do not know much about encoding. I would love your lectures or some teachings from you to generally get better at encoding data to files.

@nyurik , I am currently scoping existing work that I can learn from and use. I need help on:

1. Getting used to the Rust ecosystem. I predominantly write golang. So, I need to get familiar with Rust's tooling, conventions, and build systems.
2. Rust, the language itself. I am just learning the language. I want to keep writing de that teaches me as I go over reading a large blob of documentations. This means that I will make a lot of mistakes and guidance to do the right thing and pick the right libraries will be useful.

Existing works that I currently am focusing on:

1. https://github.com/hdelva/preprocess_routable_tiles - This was a SOTM 2019 presentation from people associated with the open source route tiling team. The work here is very prototype-y. But it is written in rust. So it is a good start for me.
2. https://github.com/valhalla/valhalla's tile builder named Mjolnir- This one is on C++ and a little messy. But it has everything we need to learn about graph tile building for routes in the first place.

There will be more challenges ahead but right now these are the only two things I care about. I am using Overture over OSM because Overture is still nascent. And that helps me limit my focus too. :)

Would be nice to more more people, have a Github board, write code together. Right now, I am planning to do it alone. But getting a community to do it together would be nice. I do not have any revenue, or monetary goal in mind. I am simply learning now.

I am not at the tiling part just yet. I want to talk to the right people now.

[mactrem]

@thehoneymad sure, i can help you to find efficient encodings of the routing data or to extend COVTiles. We can setup a meeting to discuss on that topic if you want

[thehoneymad]

I will be super grateful for that. Before I meet up with you and use your valuable time @mactrem, I want to keep at my goal for at least four weeks.

I need to build a habit of contributing back again. I think if I get a meeting at the beginning of March, I will have concrete things to talk about.

As a forcing function I will try to keep updates coming to this thread.

[thehoneymad]

Also, RustRover is on preview, want to try that. :D

[ianthetechie]

I've been daily driving it for a few months. Works great :) Few stack traces here and there, but they haven't really affected editing in quite some time.

[thehoneymad]

Speaking specifically about tiles, I think the first productivity blocker is not having something that displays map tiles from Overture data. PMTiles is a natural fit. We probably need to host it somewhere.

Leaving the note here because this is also very close aligned to cov-tiles and its future.