"/home/yossef/notes/git/projects/maplibra/modules/Route Smoothing.md"

path: maplibra/modules/Route Smoothing.md

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

Route Smoothing

Purpose: How raw A* paths are transformed into human-like walking routes.

Related: ../Home.md, ./Pathfinding.md, ../flows/Wall Detection.md, ../decisions/Post-A-Star Staircase Straightening.md, ../decisions/Safe Direct Route Smoothing.md, ../decisions/Elastic Route Smoothing.md

How The Pipeline Works (End-to-End)

When a user drops a pin and requests a route, this is what happens:

1. A returns graph node IDs* — e.g. ["L1:42", "L1:43", "L1:44", ...]
2. route-features.js looks up coordinates for each node → [[lng, lat], [lng, lat], ...]
3. removeDuplicateCoords strips exact duplicates (can happen at door transitions)
4. straightenVisibleRoute finds farthest direct walkable shortcut across open areas (Stage -1)
5. relaxVisibleRoute pulls remaining interior points toward safe straight chords when direct shortcutting is blocked
6. straightenWalkableStaircase tries to skip shallow grid staircases by taking direct walkable shortcuts
7. straightenCorridorZigzag projects sharp back-and-forth patterns onto straight lines
8. simplifyRouteSegment removes redundant points that barely deviate from a straight line
9. smoothRouteSegment greedily skips intermediate nodes when a direct segment is walkable and saves distance
10. curveRouteSegment replaces sharp corner points with cubic Bezier curve segments
11. smoothRouteHuman applies per-corner Chaikin rounding where each segment validates walkable

Each stage only replaces the working path if the entire new path passes isRouteSegmentWalkable(). If validation fails, the stage is skipped and the previous path is kept. This means safety is the default — a stage only "wins" when it produces a strictly valid, smoother path.

Pipeline

Node IDs → Coords lookup → Visible direct smoothing → Elastic relaxation → Staircase straightening → Corridor zigzag straightening → Simplification → Shortcut smoothing → Bezier curving → Enhanced smoothing

Stage -1: Visible Direct Smoothing (straightenVisibleRoute)

Finds the farthest later route point that can be reached by a fully validated straight segment. This is the main pass that makes open-area routes look direct like Mappedin while still blocking wall crossings.

Safety rules:

• Uses full isRouteSegmentWalkable() validation.
• Preserves start/end and configured protected anchors.
• Falls back to original graph points when direct segment is blocked.

Stage 0: Elastic Route Relaxation (relaxVisibleRoute)

Pulls remaining interior points toward the chord between protected anchors after direct visible shortcuts fail. Each moved point is accepted only when both adjacent segments pass full isSegmentWalkable() validation, and the pipeline still validates the whole candidate route with isRouteSegmentWalkable().

Safety rules:

• Preserves route endpoints.
• Preserves configured protected anchors.
• Keeps original graph points when all tested moves are blocked.
• Emits trace notes containing Elastic route point relaxed when tracing is enabled.

Stage 1: Walkable Staircase Straightening (straightenWalkableStaircase)

Added to reduce screenshot-like shallow grid staircases after A* but before the older smoothing passes.

• Implemented in src/pathfinding/route-smoothing-enhanced.js.
• Integrated in src/pathfinding/route-features.js before corridor zigzag cleanup.
• Greedily scans from the current anchor to the farthest future point.
• Accepts a shortcut only when it saves distance or removes enough intermediate grid points.
• Requires context.isSegmentWalkable(start, end, floorId) === true; missing validation means no straightening.
• The full candidate output is still guarded by isRouteSegmentWalkable() in buildRouteFeatures() before replacing the working route.
• Emits trace notes containing Staircase shortcut rejected when a far shortcut is blocked and tracing is enabled.

This is a conservative post-A* cleanup. It does not change graph generation, WASM routing, binary graph layout, or worker route search.

Stage 1a: Aggressive Straightening (aggressiveWalkableStraightener)

Attempts to remove remaining intermediate points by finding the farthest walkable jump from each current anchor. It runs on the current working route, not the original raw graph route, so it cannot reintroduce zigzags already reduced by visible or elastic smoothing. The pipeline only accepts this stage when it removes points and the full candidate route remains walkable.

Stage 2: Corridor Zigzag Straightening (straightenCorridorZigzag)

Projects sharp zigzag clusters onto the entry-to-exit line when every projected segment remains walkable.

• Detects interior turns over 80 degrees.
• Groups consecutive zigzag points into clusters.
• Projects cluster points onto the cluster entry-to-exit line.
• Returns the original coordinates when validation fails.

This catches sharper back-and-forth patterns, while straightenWalkableStaircase catches shallower grid staircases.

Stage 2b: Local Zigzag Cleanup (removeZigzagPoints)

removeZigzagPoints() detects short dogleg windows after A* and before final curve smoothing. It only removes intermediate points when the direct shortcut stays walkable and the pattern has enough turn/deviation evidence to be a zigzag rather than a real corridor corner.

Safety rules:

• Preserve first and last route points.
• Use walkability validation before accepting a shortcut.
• Keep real corridor turns.
• Avoid noisy console logs during route computation.

Stage 3: Douglas-Peucker Simplification (simplifyRouteSegment)

Removes points that do not deviate enough from the straight line between neighbors. Uses projected meter-space distance with configurable tolerance.

Stage 4: Greedy Shortcut (smoothRouteSegment)

Iterates from anchor to end, tries to skip intermediate nodes:

• For each anchor, scan backward from last coord
• If direct segment is walkable AND saves enough distance → skip to it
• Thresholds: smoothShortcutMinMeters (0.01m) or smoothShortcutMinRatio (0.5%)

Stage 5: Bezier Curving (curveRouteSegment)

Rounds sharp corners with cubic Bezier curves:

• Only applies at corners with turn angle > smoothCurveMinTurnDegrees
• Radius limited by segment lengths and smoothCurveMaxDeviationMeters
• Each curve validated via isSegmentWalkable before acceptance
• Runs on touch devices by default; set smoothCurveOnTouch = false to opt out for performance

Stage 6: Enhanced Smoothing (smoothRouteHuman)

Optional Chaikin/Catmull-Rom smoothing:

• Removes zig-zag patterns near doors (> 100° turn angle)
• Adaptive waypoint reduction (keeps points with turns > 5° or segments > 0.3m)
• Applies per-corner Chaikin-style corner cutting at 0.85/0.15 cut ratios (aggressive rounding)
• Each smoothed segment validated via isSegmentWalkable; falls back to unsmoothed corner when validation fails

Walkability Validation

Every smoothing shortcut and curve is validated by isSegmentWalkable:

• Samples points along the segment at regular intervals
• Each point must be inside a walkable polygon AND not inside a blocker buffer
• JS: samples every 0.2m (was 0.5m, fixed)
• WASM: samples based on distance / 0.5m (was only 2 points, fixed)

Blocker System

Blockers are geometry features buffered outward:

• Runtime smoothing walls: +0.25m buffer by default
• Runtime smoothing objects: +0.2m buffer by default
• Runtime smoothing nonwalkable: +0.2m buffer by default

Indexed via SpatialBlockerIndex (grid cells ~5.5m). Point-in-polygon check against buffered features.

Configuration Parameters

All values live as properties on the controller context (e.g. pathfindingController). Set them before calling buildRouteFeatures().

Tuning Guide

Path looks too jagged / too many sharp corners:

• Increase smoothCurveMaxDeviationMeters (e.g. 2.0)
• Increase smoothCurveFactor (e.g. 0.6)
• Lower smoothCurveMinTurnDegrees (e.g. 5)

Path looks too straight / crosses through narrow gaps it shouldn't:

• Lower smoothCurveMaxDeviationMeters (e.g. 0.8)
• Increase smoothCurveMinTurnDegrees (e.g. 20)
• Increase smoothShortcutMinMeters (e.g. 0.05)

Path takes unnecessary detours instead of direct lines:

• Lower smoothShortcutMinMeters (e.g. 0.005)
• Lower smoothShortcutMinRatio (e.g. 0.002)

Mobile performance is poor:

• Set smoothCurveOnTouch = false to disable touch-device curving
• Or lower smoothCurveSamples (e.g. 6)

Important Files

• src/pathfinding/route-smoothing.js — Main smoothing pipeline

• src/pathfinding/route-smoothing-enhanced.js — Visible/elastic straightening, staircase straightening, corridor zigzag straightening, per-corner human smoothing

• src/pathfinding/route-features.js — Orchestrates per-floor route smoothing before rendering

• src/pathfinding/walkable-areas.js — Walkability queries

• tests/route-smoothing.test.js — Unit tests for straightening helpers

• tests/route-features.test.js — Pipeline tests for smoothing integration

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