WASM Routing

"/home/yossef/notes/git/projects/maplibra/modules/WASM Routing.md"

path: maplibra/modules/WASM Routing.md

- **fileName**: WASM Routing
- **Created on**: 2026-06-16 00:48:42

WASM Routing

Purpose: Documents the native C routing kernel compiled to WebAssembly.

Overview

The WASM kernel is an optional accelerator that replicates the JS pathfinding logic in C for performance. It handles:

A* pathfinding (routing_find_multi_candidate_path)
Nearest-node spatial queries (routing_find_nearest_nodes)
Point walkability checks (routing_is_point_blocked)
Segment walkability sampling (routing_is_segment_walkable)
Point clearance measurement (routing_get_point_clearance)
Shortcut vertex finding (routing_find_shortcut_vertex)

Architecture

JS (route-kernel-bridge.js)
  ↓ copies graph buffers into WASM memory
  ↓ packs options into 48-byte struct
  ↓ calls exported C functions
  ↓ reads result buffer back
C (route_kernel.c + route_smoothing.c + route_spatial.c)
  ↓ operates on linear memory
  ↓ uses pre-allocated scratch buffers
  ↓ writes results to shared output buffer

Memory Layout

Graph lives in WASM linear memory as flat typed arrays:

Nodes: GraphNode = { x:f32, y:f32, floor_index:u32, first_edge_index:u32, edge_count:u32, clearance:f32 } = 24 bytes
Edges: GraphEdge = { to_index:u32, cost:f32, flags:u32 } = 12 bytes
Spatial floors: walkable polygons + blocker polygons as flat coordinate arrays with META_RECORD_STRIDE=7 metadata

Spatial Floor Bundle

Uploaded per floor via routing_upload_spatial_floor. Contains:

walkable_meta — Uint32Array, 7 values per polygon: [firstCoord, coordCount, bboxMinX, bboxMinY, bboxMaxX, bboxMaxY, flags]
walkable_coords — Float32Array, flat [lng, lat, lng, lat, ...] pairs
blocker_meta — same format for wall/object buffers
blocker_coords — flat coordinate pairs for blockers

Key Functions

Export	Purpose
`routing_init_graph`	Load graph into WASM memory
`routing_find_multi_candidate_path`	A* with multiple start/goal candidates
`routing_is_point_blocked`	Check if point is outside walkable or inside blocker
`routing_is_segment_walkable`	Sample N points along segment, check each
`routing_get_point_clearance`	Distance to nearest blocker edge
`routing_find_shortcut_vertex`	Greedy shortcut search for smoothing
`routing_upload_spatial_floor`	Upload walkable/blocker polygons for a floor

Known Issues (Fixed/In Progress)

Bug: isSegmentWalkable defaulted to 0 samples → C used only 2 (start+end)
Fix: Bridge now computes distance-based sample count (1 per 0.3m, min 4)
Bug: routing_get_point_clearance BBox uses 1.0 degrees (~111km) instead of meters

Important Files

src/pathfinding/wasm/route-kernel-bridge.js — JS bridge class
src/pathfinding/wasm/route-kernel-options.js — Options struct packing
src/pathfinding/wasm/route-kernel-loader.js — Emscripten module loader
src/pathfinding/wasm/spatial-floor-bundle.js — Polygon serializer
native/routing/route_kernel.c — A* core
native/routing/route_smoothing.c — Walkability + shortcut
native/routing/route_geometry.c — Point-in-polygon
native/routing/route_spatial.c — Nearest-node scan

continue:[[]]
before:[[]]