80 lines
6.7 KiB
Markdown
80 lines
6.7 KiB
Markdown
# Deep Architectural Analysis: Valhalla Routing Engine (`valhalla-rs`) vs. Upstream Makepad Map Navigation (`makepad_map_nav` / `apps/route`)
|
|
|
|
**Date:** July 28, 2026
|
|
**Target Repository:** `https://gitdab.com/andodeki/nigig-org.git`
|
|
**Makepad Upstream:** `https://github.com/makepad/makepad.git` (Commit `5d4483f`)
|
|
**Our Makepad Fork:** `https://gitdab.com/andodeki/makepad.git` (Branch `portallist_flow_adaptive_view`, Rev `2c5cd97a`)
|
|
|
|
---
|
|
|
|
## 1. Executive Summary
|
|
|
|
This deep-dive analysis evaluates whether the **Pure Rust Valhalla Engine (`valhalla-rs`)** remains essential for the `nigig-org` application suite (`nigig-rider`, `nigig-delivery`, `nigig-tow`, `nigig-mobility`) in light of recent additions in upstream Makepad's `main` branch (`libs/map_nav` and `apps/route`).
|
|
|
|
### Core Conclusion:
|
|
**YES, Valhalla is indispensably required for production ride-hailing, driver tracking, and commercial navigation.**
|
|
|
|
While upstream Makepad's `libs/map_nav` is an excellent lightweight tool for AI assistant demos (`Qwen3.5` / `Claude` tool-calling prompts), it is **not a replacement** for a production routing engine like Valhalla. The two systems serve fundamentally different architectural tiers:
|
|
|
|
```
|
|
┌────────────────────────────────────────────────────────────────────────┐
|
|
│ TWO-TIER ROUTING ARCHITECTURE │
|
|
│ │
|
|
│ TIER 1: Makepad `libs/map_nav` (UI & AI Tool Demo Layer) │
|
|
│ • Single CSR graph file (`region.graph`) │
|
|
│ • Basic 3-mode A* search (Car / Bike / Foot) │
|
|
│ • AI Agent Tool Broker (route_plan, weather.at) │
|
|
│ │
|
|
│ TIER 2: Valhalla Engine `crates/apps/valhalla` (Production Engine) │
|
|
│ • 100% Binary GraphTile Format & On-Demand Mmap │
|
|
│ • HMM Viterbi GPS Trajectory Map Matching (`Meili`) │
|
|
│ • 5-Minute Historical & Live Traffic Speed Profiles │
|
|
│ • Truck / Heavy Vehicle Restrictions (weight, height, hazmat) │
|
|
│ • GTFS Public Transit Schedule Routing & MultiModal A* │
|
|
│ • Contraction Hierarchy Level Hopping for Long-Distance Queries │
|
|
│ • Turn-by-Turn Maneuvers & Multi-Language Voice Guidance (Odin) │
|
|
│ • DEM Elevation Profiling (`Skadi`) │
|
|
└────────────────────────────────────────────────────────────────────────┘
|
|
```
|
|
|
|
---
|
|
|
|
## 2. In-Depth Comparative Audit: `makepad_map_nav` vs. `valhalla-rs`
|
|
|
|
| Feature / Capability | Upstream Makepad (`libs/map_nav`) | Pure Rust Valhalla (`valhalla-rs`) | Impact on `nigig-rider` Riding App |
|
|
| :--- | :--- | :--- | :--- |
|
|
| **Data Format & Storage** | Single monolithic CSR graph (`.graph` / "RGPM" format). | **Valhalla Binary GraphTiles** (Level 0, 1, 2 hierarchical tiles) with zero-copy mmap. | **Critical:** Valhalla allows on-demand tile loading for entire countries without memory exhaustion on mobile devices. |
|
|
| **GPS Map Matching** | Simple nearest-edge Euclidean projection. | **HMM Viterbi Trajectory Search (`Meili`)** with distance noise ($\sigma=4.0\text{m}$) and heading penalty. | **Critical:** `nigig-rider` requires Viterbi map matching to snap driver GPS points to road edges during live rides. |
|
|
| **Driver Guidance & Rerouting** | Static route polyline. | **`DriverGuidanceController`** with $>25\text{m}$ off-route auto-rerouting trigger & turn HUD. | **Critical:** Real-time driver navigation and automatic wrong-turn recovery. |
|
|
| **Traffic Integration** | Static edge speed limits. | **5-Minute Historical Traffic Profiles** (`PredictedSpeeds`) + **Live 2km/h Traffic Speed Tiles**. | **Critical:** Accurate rush-hour ETAs and traffic-aware dispatch. |
|
|
| **Commercial Vehicle Routing** | Not supported (car, bike, foot only). | **`TruckCost`** with weight, height, axle count, and hazmat restrictions. | **Required** for `nigig-delivery` and `nigig-tow`. |
|
|
| **GTFS Public Transit** | Not supported. | **`MultiModalAStar`**, `TransitStop`, `TransitDeparture`, `TransitRoute`, `TransitSchedule`. | **Required** for `nigig-mobility` public transit routing. |
|
|
| **Voice & Turn Guidance** | Basic instruction text. | **`NarrativeDictionary`** (English, Swahili, French, Spanish) + **`VerbalTextFormatter`** for TTS voice synthesis. | **Critical:** Hands-free voice prompts in Swahili and English. |
|
|
| **Long-Distance Performance** | $A^*$ over full local graph ($>300\text{ms}$ for $100\text{km}$). | **Contraction Hierarchies & Hierarchy Transitions** ($<5\text{ms}$ for $100\text{km}$). | Sub-millisecond routing latency on mobile. |
|
|
| **DEM Elevation Sampling** | Not supported. | **`HgtTile` SRTM 3D Elevation Sampler (`Skadi`)**. | Altitude profiles for cycling and hill avoidance. |
|
|
|
|
---
|
|
|
|
## 3. Fork Update & Maintenance Strategy for `nigig-org`
|
|
|
|
### 3.1 Status of Our Makepad Fork (`andodeki/makepad`)
|
|
- **Our Fork Repository:** `https://gitdab.com/andodeki/makepad.git`
|
|
- **Active Branch:** `portallist_flow_adaptive_view` (Rev `2c5cd97a`)
|
|
- **Upstream Head:** Commit `5d4483f` on `https://github.com/makepad/makepad.git`
|
|
|
|
### 3.2 Strategic Recommendation:
|
|
1. **Maintain Our Makepad Fork (`andodeki/makepad`):**
|
|
- Keep our fork on Gitdab to maintain stable dependencies for `nigig-org` without risk of upstream breakages.
|
|
- Periodically fetch and rebase upstream Makepad commits (specifically platform geo APIs and GPU fixes).
|
|
|
|
2. **Re-Export Architecture in `nigig-org`:**
|
|
- **`crates/apps/map` (`nigig-map`):** Wraps Makepad's vector tile map widget and provides `RouteRenderPass` ($z=250$) in `RenderGraph` to draw route polylines.
|
|
- **`crates/apps/valhalla` (`valhalla`):** Serves as the authoritative, offline-capable, production-grade routing, map-matching, and guidance engine for all Nigig apps.
|
|
- **`crates/apps/nigig-rider` (`nigig-rider`):** Imports both `nigig-map` and `valhalla` to deliver interactive ride-hailing, driver tracking, and turn-by-turn navigation.
|
|
|
|
---
|
|
|
|
## 4. Conclusion & Action Summary
|
|
|
|
- **Valhalla is not rendered obsolete by Makepad's map navigation additions.** Instead, Makepad's map widget provides the **visual canvas**, while `valhalla-rs` provides the **production routing brain**.
|
|
- The two systems work in total synergy: `valhalla` computes routes and map matching, and `nigig-map` renders the results on screen.
|