"/home/yossef/notes/git/projects/maplibra/modules/Pathfinding.md"

path: maplibra/modules/Pathfinding.md

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

Pathfinding

Purpose: Overview of the A* pathfinding system and graph structure.

Related: ../Home.md, ../Architecture.md, ./WASM Routing.md, ./Route Smoothing.md

Graph Structure

The navigation graph is a pre-built network of walkable nodes connected by edges.

Nodes have:

• id — unique string like "L1:42"
• floorId — which floor this node belongs to
• coords — [lng, lat] position
• neighbors — array of edge objects
• clearance — meters to nearest wall (computed at runtime)
• componentId — connected component for reachability checks

Edges have:

• id — target node ID
• cost — traversal cost in meters
• type — "walk" | "stairs" | "elevator" | "ramp" | "escalator"
• connectionId — link to connection record for floor transitions

A* Algorithm

Implemented in src/pathfinder.js (JS) and native/routing/route_kernel.c (WASM).

Key features:

• Multi-candidate start/goal — snapping produces multiple candidates, A* tries them all
• Haversine heuristic — admissible, straight-line distance to nearest goal
• Lazy deletion — stale heap entries skipped via closed set (no decrease-key)
• Custom edge cost — accessibility constraints, center-bias, floor-transition penalties

Route Shape After A*

A* returns graph node IDs, not the final user-facing line. Because graph nodes are sampled on a local grid, the raw path can contain shallow stair-step patterns across open or angled walkable spaces.

src/pathfinding/route-features.js converts node IDs to per-floor coordinate segments and then runs ./Route Smoothing.md. The newer straightenWalkableStaircase() pass is deliberately post-A*: it improves the displayed and followed route while leaving graph generation, worker routing, binary routing, and WASM route search unchanged.

See ../decisions/Post-A-Star Staircase Straightening.md.

Edge Cost Model

From src/pathfinding/routing-cost.js:

Graph Formats

JSON (routing/graph.json)

Full graph with nodes array. Each node has neighbors inline.

Binary (routing/graph.*.bin)

Split into separate typed-array files:

• graph.header.json — metadata, node IDs, floor list
• graph.nodes.bin — packed GraphNode structs (x, y, floorIndex, firstEdge, edgeCount, clearance)
• graph.edges.bin — packed GraphEdge structs (toIndex, cost, flags)
• graph.spatial.bin — spatial index data
• graph.anchors.bin — named anchor points

Important Files

• src/pathfinder.js — JS A* + MinHeap + haversine

• src/pathfinder-graph.js — Graph data structure with findNearestNode

• src/pathfinding/unified-graph.js — Indoor+outdoor graph wrapper

• native/routing/route_kernel.c — WASM A* implementation

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