makepad/gps.md

GPS layer: search, current position, routing

Status 2026-07-27 — basic navigator SHIPPED (M0 + M1 + M3 + sim-M2/M4)

Built and verified end-to-end (search "centraal" → route → simulated drive → "You have arrived" banner):

• libs/map_nav — geo, region.search (builder+query, prefix/category/proximity), region.graph (CSR, per-mode speeds, oneway, turn restrictions, snap grid, A*), maneuver generation, NavSession (map-matching, off-route → reroute). 26 unit tests.
• tools/map_tiles nav-build <pbf> <basename> [--bbox] — one scan → both artifacts (Noord-Holland: 7.8s, 89MB graph / 107MB search, 1.39M directed edges, 1.8M docs incl. full addresses). nav-probe for CLI search/route checks. NH pbf at local/maps/noord-holland-latest.osm.pbf, artifacts local/maps/noord-holland.*.
• MapView M0: MapViewAction (ViewportChanged/Tapped/LongPressed/MarkerClicked), camera API + fly_to (zoom-out-in arc), overlay.rs (route casing+fill with traveled dim, pin markers, position puck w/ accuracy + heading), mbtiles_path DSL property (per-app tile archive override). Map now respects the handled flag so floating panels win hits (EventOrder::Up).
• examples/map is the navigator app: debounced worker-thread search, result list, long-press / "Set position here" → puck, route bar (Drive/Bike/Walk), Start → simulated turn-by-turn with banner + follow cam + recenter.

Not yet: real GPS (CoreLocation), heading-up camera, voice, CH scaling, v2 pbf index extras (opening hours, admin hierarchy), typo tolerance. Plan below is the original roadmap.

Plan for the interaction layer on top of the local map stack: a search engine over the map data (places, shops, streets, addresses), a live "current position" puck, and turn-by-turn routing — a proper offline GPS app. This work sits between the renderer (being improved in widgets/src/map/) and the OSM import pipeline (tools/map_tiles/), and deliberately touches both only through small, agreed contracts so all three tracks can proceed in parallel.

Current state (what we build on)

• Renderer: MapView (widgets/src/map/view.rs) renders Shortbread vector tiles from a local mbtiles file. Camera = center_norm (normalized web mercator Vec2d)
  • fractional zoom. No rotation. Pan/scroll-zoom gestures work. There is no public camera API, no widget actions, no tap reporting, no fly-to animation — the widget is render-only today. examples/map is a bare demo with an empty handle_actions.
• Data: noord-holland-shortbread-1.0.mbtiles, z0–14. The z14 layers carry real search fodder: pois (name, amenity, shop, cuisine, tourism…), addresses (housenumber/housename — no street name), street_labels (street names), place_labels (cities/towns + population), public_transport (stations), buildings, sites, land. The streets layer has kind, oneway, oneway_reverse, bridge, tunnel, link — enough for a stopgap routing graph, but no turn restrictions and no stable node ids.
• Import pipeline: tools/map_tiles already parses raw .osm.pbf (osmpbf dep) and builds a full-tag "detail archive" that retains OSM ids + complete tag maps. This is the natural source of truth for search v2 and the routing graph.
• Reusable primitives:
  • Zoom-constant screen-space symbols: ICON_SHAPE_ID path in the map vertex shader
    • append_icon_mesh (tile.rs) — exactly what markers and the position puck need.
  • DrawVector immediate-mode path API (move_to/line_to/stroke) — route overlay.
  • DrawRotatedText + the label collision machinery — overlay labels.
  • Background work pattern: TagThreadPool + ToUIReceiver (used for tile decode) — reuse for search queries, index build, and route computation.
  • MbtilesReader (libs/mbtile_reader): sync, cheap to open, direct tile lookup.
  • Overlay injection point: end of MapView::draw_walk, after place_and_draw_labels.

Architecture

One new pure-logic crate plus additions to the widget and the import tool:

libs/map_nav/            NEW — no UI deps, fully unit-testable
  src/search/            index format, builder, query engine, ranking
  src/graph/             routing graph format, builder helpers, A* query
  src/nav/               NavSession state machine (map-matching, instructions, reroute)
  src/geo.rs             shared: fixed-point coords, mercator helpers, haversine

tools/map_tiles/         import pipeline (other agent) gains two subcommands:
  search-index           pbf (or tiles) -> region.search
  route-graph            pbf -> region.graph

widgets/src/map/
  view.rs                camera API, actions, fly-to, overlay draw hook
  overlay.rs             NEW — markers, route polyline, position puck
  (search UI + nav HUD live in the example app first, promoted to widgets later)

examples/map/            grows into the actual GPS app (search box, nav HUD)

Rationale: libs/map_nav mirrors what libs/mbtile_reader is for tiles — a dependency shared by the import tool (which builds artifacts) and the app/widget (which queries them). File formats live in one place; the import agent and we only need to agree on the artifact contracts (below).

All heavy work (index build, search queries, route computation, reroutes) runs on the existing thread-pool pattern and posts results back over ToUIReceiver. The UI thread never blocks on any of this.

Coordinate conventions: f64 lon/lat at every public API boundary; normalized web mercator internally (matches center_norm); u32 fixed-point (norm-mercator × 2³²) in file formats.

Milestone 0 — MapView interaction API (prerequisite for everything)

The widget must become programmable before search or nav can exist. Small, mechanical, should land first and unblocks all later milestones. Coordinate with the renderer agent since it touches view.rs, but it's additive.

1. Actions: add MapViewAction and emit via cx.widget_action:
   • ViewportChanged { center_lon, center_lat, zoom } (end of gesture + end of fly-to)
   • Tapped { lon, lat, abs } (finger up without drag)
   • LongPressed { lon, lat, abs } (for "set position here" / "route to here")
2. Camera API on MapView/MapViewRef:
   • set_center(lon, lat), set_zoom(z), center() -> (f64, f64), zoom() -> f64
   • screen_to_lonlat(abs) -> (f64, f64) and inverse (the math already exists privately in geometry.rs)
   • write center_lon/center_lat/zoom back after gestures (today they're stale input-only seeds)
3. fly_to(lon, lat, zoom): animated camera. Copy the existing timer pattern (zoom_settle_timer / tile-fade). Ease center in mercator space + zoom with a zoom-out-then-in arc when the target is far (keeps tiles loadable mid-flight and reads like every mapping app). ~150 lines including easing.
4. Marker layer (overlay.rs): set_markers(Vec<MapMarker { lon, lat, icon, color, id }>), drawn with the zoom-constant symbol path; hit-test markers before the map's finger grab and emit MarkerClicked { id }. Add a pin SVG to ICON_SVGS.
5. Overlay draw hook: draw order = tiles → labels → route polyline → markers → position puck (puck always on top).

Deliverable: examples/map can tap the map, log lon/lat, drop a pin, and fly_to it.

Milestone 1 — Search

Two data stages (don't block on the import agent)

• v1 — index built from the tiles we already ship. Scan all z14 tiles (Noord-Holland: 5,780 tiles ≤ ~400 KB — a seconds-scale, one-time background job on first launch, cached to disk). Extract named/categorized features from pois, place_labels, street_labels, public_transport, buildings, sites, land. The MVT decoder already produces per-feature tag maps at tile-build time; v1 adds an MvtSink that collects (name, tags, centroid) instead of tessellating. Known v1 limits: no full addresses (Shortbread addresses lacks street names), features can appear in multiple tiles (dedupe by name_key + quantized location), no house-number interpolation.
• v2 — index emitted by the import pipeline from the pbf. Full addr:street + addr:housenumber + addr:city + postcode geocoding, OSM ids, opening hours / website / phone in result details, admin hierarchy for display names ("Albert Heijn — Zaandam"). Same file format, better builder. This is the contract to agree with the import agent; v1 exists so the search UI, ranking, and UX are finished before v2 data arrives.

Index format (region.search, owned by libs/map_nav)

Design goals: mmap/stream-friendly (match the disk-streamable ethos of the tile store), zero-copy query, no runtime deps. Layout:

• Doc table: fixed-size records — coord (2×u32 fixed-point), category (u16 enum: city, town, street, supermarket, restaurant, cafe, station, …), static rank (u8: population for places, category weight for POIs), offsets into a string pool (display name, secondary line).
• Token index: all names normalized (reuse/extend normalize_label_key in label.rs: lowercase, unaccent, strip punctuation) and tokenized. Sorted token table → binary search gives exact and prefix ranges for free. Each token has a postings list of doc ids, pre-sorted by static rank so top-k short-circuits.
• Category synonyms: small static table in code mapping query words to categories ("supermarkt"/"supermarket"/"groceries" → shop=supermarket; "pizza" → amenity=restaurant|fast_food + cuisine=pizza), so category queries return nearby instances rather than name matches. NL + EN synonyms first.
• Typo tolerance (trigram fallback) is a later add — the format reserves a section id for it; v1 is prefix-only, which covers the autocomplete-style UX.

Query pipeline (background thread, debounced ~150 ms)

1. Normalize + tokenize; last token treated as a prefix.
2. Intersect postings (rarest token first); or category expansion when a token hits the synonym table.
3. Score: match quality (exact > prefix, full-name > partial) + static rank + proximity boost (distance to current position if set, else viewport center) — log2(distance) penalty so "pizza" means "pizza near me".
4. Top 10 → SearchResults action to the UI thread.

Search UI (examples/map first)

Floating panel over the map: TextInput + results list (name, category icon, secondary line, distance). Enter/click → fly_to + drop marker; category queries can pin all top-N results. Escape/map-tap dismisses. Promote to a reusable MapSearchPanel widget once the UX settles.

Deliverable: type "centraal", get Amsterdam Centraal ranked above street matches, fly there. Type "supermarkt", get the nearest ten with pins.

Milestone 2 — Current position

Position provider

PositionSample { lon, lat, accuracy_m, heading_deg: Option, speed_mps: Option, time } behind a PositionSource abstraction with three implementations, in build order:

1. Manual — long-press → "set my position here". Trivial, immediately useful.
2. Simulated — plays back a polyline (later: a computed route) at a given speed with synthetic heading + configurable GPS noise. This is the workhorse: it's how nav (M4) gets developed and tested on a desk, and it feeds the same code path a real receiver would.
3. Platform — real location services. Makepad's platform layer has no geolocation API yet, so this is a new Cx service: cx.start_location_updates() → Event::LocationUpdate. macOS (CoreLocation via the existing objc bindings) first since that's the dev machine; iOS shares CoreLocation; Android (FusedLocation via JNI), web (navigator.geolocation) after. Permission plumbing per platform. Schedule late — everything above it works against Manual/Simulated.

Rendering + camera behavior

• Puck: accuracy circle drawn in map space (scales with zoom), blue dot + white ring + heading wedge drawn zoom-constant (ICON_SHAPE_ID path). Interpolate between 1 Hz fixes at frame rate (short lerp, mild dead-reckoning by speed/heading) so the puck glides instead of teleporting.
• Follow mode: camera tracks the puck. Any user pan/zoom breaks follow; a recenter button (standard GPS UX) re-engages it. Follow state lives in the app, driven via the M0 camera API — the widget stays dumb.

Deliverable: simulated drive around Amsterdam with a gliding puck, follow mode, and working recenter button.

Milestone 3 — Routing

Graph build (import pipeline, contract with the import agent)

Go straight to the pbf-derived graph — osmpbf is already a dependency of tools/map_tiles, and the tile-derived alternative (stitching clipped z14 streets geometry) has no turn restrictions, lossy connectivity at tile borders, and crossing-vs-junction ambiguity. Not worth building twice. (If the interaction track ever gets far ahead of the import track, a tile-stitched graph behind the same file format is the documented fallback — bridge/tunnel/layer disambiguate most crossings — but it's plan B, not the path.)

Builder (route-graph subcommand, logic in libs/map_nav::graph::build):

1. Pass 1 over ways: keep highway=* filtered by access profile; count node usage.
2. Vertices = nodes used ≥2× + way endpoints. Edges = way segments between vertices, carrying: length (m), speed class (from highway kind, maxspeed when present), oneway, access flags per profile (car / bike / foot — Netherlands, so bike is not optional), and the full segment geometry for drawing.
3. Turn restrictions from relations (no_left_turn, only_straight_on, …) stored as (via-node, from-edge, to-edge) ban/only lists.
4. Serialize region.graph: CSR adjacency, u32 vertex ids, fixed-point coords, packed edge attrs, geometry pool, plus a uniform grid spatial index over edges for nearest-edge snapping.

Scale check: Noord-Holland is on the order of a million edges — plain in-memory graph, loads in well under a second.

Query engine (libs/map_nav::graph::query)

• Snap start/goal: grid lookup → project point onto candidate edges → virtual split.
• Bidirectional A* with a per-profile cost function (time-based; distance mode as a flag). Province-scale queries land in tens of ms on a worker thread — no preprocessing needed at this size. When we go country/Europe scale, add Contraction Hierarchies in the builder (query side barely changes); the file format reserves a section for shortcut edges now so the format doesn't break later.
• Turn restrictions handled by edge-based expansion at restricted via-nodes only (cheap, standard trick — avoids paying edge-based-graph cost everywhere).
• Output Route { polyline, length_m, duration_s, legs: Vec<Maneuver> }.

Route rendering

Route polyline via DrawVector in the overlay hook: casing + fill in a distinct color, simplified by zoom (geometry.rs already has simplification helpers), the already-traveled portion dimmed once nav is active. Start/end markers from M0.

Deliverable: long-press → "route here" from current position; route line + distance and time appear.

Milestone 4 — Turn-by-turn navigation

Instruction generation (libs/map_nav::nav)

Walk the route's vertices: where bearing delta + road-class change warrant it, emit Maneuver { kind, at: coord, street_name, distance_from_start } with kinds Depart / Continue / TurnSlightLeft…SharpRight / Roundabout { exit_n } / Uturn / Arrive. Roundabout exit counting from the graph topology. Street names come from way tags (already in the graph edges).

NavSession state machine

Owned by the app, fed PositionSamples, emits actions:

• Map-matching: project position onto route polyline near last known progress, gated by heading agreement; monotonic progress (never snaps backward on noise).
• Progress: distance to next maneuver, remaining distance/time, ETA (recomputed from live speed with per-class fallback speeds).
• Off-route: > ~30 m from route (accuracy-scaled) for > ~5 s → Rerouting state, fire a background route query from current position, swap route on arrival. The simulated source with noise (M2) is the test harness for exactly this.
• Maneuver announcements at distance thresholds (e.g. 500 m / 100 m / now) → actions the UI turns into banner changes. Optional later: voice via libs/tts (kokoro) — the announcement action is designed so a TTS consumer just subscribes.

Nav UI (examples/map)

• Top banner: maneuver arrow icon + "300 m — turn left onto Prinsengracht".
• Bottom bar: ETA, remaining km/min, end-navigation button.
• Camera: follow mode centered ahead of the puck (position ~1/3 from bottom), zoom scaled by speed. North-up in v1. Heading-up requires camera rotation, which the renderer doesn't have — the transform is affine so it's feasible, but it's the renderer agent's call; flagged as a coordinated stretch goal, not a v1 dependency.

Deliverable: simulated drive follows a computed route with live banner instructions, and going off-route visibly triggers a reroute.

Milestone 5 — Real-world hardening (post-MVP, ordered by value)

1. macOS CoreLocation backend (first real-GPS platform), then iOS/Android/web.
2. Search v2 index from pbf (full addresses, postcodes, admin hierarchy, details).
3. Camera rotation + heading-up nav (with renderer agent).
4. Voice guidance via libs/tts.
5. Typo tolerance (trigram section), multi-stop routes, avoid-motorway/ferry flags.
6. Europe scale: CH preprocessing, sharded search index, both keyed by region files.

Artifact contracts (the import-agent interface, agree early)

Artifact	Producer	Consumer	Contents
region.mbtiles	import pipeline	renderer	exists today (Shortbread tiles)
region.search	map_tiles search-index (v1: app self-builds from tiles)	search engine	doc table + token index + string pool, format owned by libs/map_nav
region.graph	map_tiles route-graph	router	CSR graph + turn restrictions + edge geometry + snap grid, format owned by libs/map_nav

Formats versioned with a magic + version header; builders and readers live in the same crate so they can't drift.

Testing

• Unit (libs/map_nav, no UI): tokenizer/normalizer, ranking ("dam" must rank Dam square over side streets), postings intersection; graph snap edge cases (near junctions, dual carriageways); A* against hand-verified routes (a handful of Noord-Holland pairs sanity-checked against an online router, asserted within a tolerance); turn-restriction respect; maneuver generation on synthetic geometries (roundabout exit counts).
• NavSession sim tests: drive a noisy simulated position along a route, assert instruction sequence, ETA monotonicity, and that a forced detour triggers exactly one reroute.
• Headless render tests (existing MAKEPAD=headless PNG harness + examples/*/tests pattern): marker/route/puck overlay snapshots, search panel open-with-results snapshot.

Suggested execution order

M0 is small and unblocks everything — do it first. After M0, search (M1) and position (M2) are independent and can proceed in parallel; both are pure-add. M3 starts with the region.graph contract conversation with the import agent, then builder + A* (testable entirely without UI), then the overlay. M4 builds strictly on M2+M3. The riskiest unknowns are deliberately early: the MapView API touch (renderer-agent coordination) is M0, and the graph contract conversation opens at the start of M3.