How someware-fr/valhalla works
Based on our analysis of the full file tree and the README, this project is the open source Valhalla routing engine—with a modular, multi-library design that provides routing, map matching, isochrone calculation, elevation sampling, cost-based routing using plugins, and other network analysis features. The code is primarily written in C++ and integrates multiple libraries (e.g., Baldr, Midgard, Sif, Skadi, Mjolnir, Loki, Meili, Thor, Odin, Tyr) that work together to ingest OpenStreetMap data, build tile-based graph structures, and serve route-related queries. There are also bindings (Python, for example) and additional command line tools, benchmarks, CI/CD configurations, test suites, and Docker support.
Core Components
• Module Libraries – Each library has its own well-defined responsibility:
• Midgard: Contains geographic and geometric utility functions.
• Baldr: Manages base data structures, tiled graph access, and caching.
• Sif: Implements cost modeling and dynamic, runtime cost calculations.
• Skadi: Handles elevation data access and sampling.
• Mjolnir: Transforms raw OpenStreetMap (OSM) data into tile-based graphs.
• Loki: Provides the location search and correlation (finding nearest routes, edges, or vertices).
• Meili: Supports map matching operations.
• Thor: Generates the optimal routing path through the graph.
• Odin: Produces maneuvers and narrative instructions.
• Tyr: Exposes the HTTP API and handles incoming routing requests.
• External Tools and Utilities – Command-line tools, benchmarks, and scripts for building and testing.
• Integration/Bindings – Python APIs and Docker deployment support.
• CI/CD/Build: Presence of CMake files, Dockerfiles, .github workflows, and various scripts indicate automated builds and testing.
Out Data Flow and Interactions
• Data Ingestion and Graph Generation Stage:
• Raw OSM data is ingested and processed primarily by Mjolnir (supported by Midgard and Baldr) to generate a tiled graph.
• Query and Routing Execution Stage:
• Loki correlates user-supplied location data with edges/vertices from the graph.
• Thor then calculates the optimal route/path using these correlated points.
• Odin translates the path information into human-friendly directions.
• Tyr serves as the API layer to respond to external queries (HTTP interface) and format output.
• Supplementary Services:
• Meili for map-matching and possible integration with real-time dynamic traffic (via Sif’s cost engine).
• Skadi for elevation data that might be used in both routing and narrative generation.
• Tools and Bindings:
• Extra components in the “src” and “test” directories, along with Python bindings in “src/bindings/python”, are designed for testing, benchmarking, and interacting with the above core modules.
Architectural Patterns and Design Principles
• Modular Design: Each module is responsible for a separate piece of functionality, which are then orchestrated in a pipeline.
• Plugin Architecture: Costing and narrative generation use a plugin-based approach for runtime customization.
• Layered Abstraction: Lower-level libraries (Midgard, Baldr) underpin higher-level components (Loki, Thor, Odin, etc.) to keep responsibilities separated.
• Cross-Compilation and Multi-platform Build: The presence of many CI configurations and CMake-based build scripts supports cross-compiling across Linux, macOS, Windows, and mobile platforms.
Technologies, Frameworks, and Infrastructure
• C++ for core engine implementation.
• CMake for build management.
• Docker and CI/CD scripts (.circleci, .github/workflows) for containerized builds and continuous integration.
• Python for bindings and scripting support.
• Other build-related tools, such as clang-format, clang-tidy, and extensive unit tests in the “test” directory.
• Protocol buffers (seen in the proto directory) for message passing in APIs.
Elements
• Clear Labels: Mark each module/library/component by name.
– From “Raw OSM Data” and “Input Data” to Mjolnir.
– From Mjolnir to Baldr/Graph Tiles.
– From Graph Tiles to Loki (for location search), then to Thor for route path generation.
– From Thor to Odin for maneuvers/narrative generation, and finally to Tyr (HTTP/API service).
– Core routing libraries (e.g., Mjolnir, Loki, Thor, Odin, Tyr)
– Supporting utility libraries (e.g., Midgard, Baldr, Sif, Skadi)
– External integration layers (e.g., bindings, Docker/CI processes, command-line tools)
• Annotations for any key design decisions such as modularity and plugin-based extensions for costing and narrative generation.