"/home/yossef/notes/git/projects/maplibra/decisions/Post-A-Star Staircase Straightening.md"

path: maplibra/decisions/Post-A-Star Staircase Straightening.md

- **fileName**: Post-A-Star Staircase Straightening
- **Created on**: 2026-06-16 00:48:42

Post-A-Star Staircase Straightening

Purpose: Documents the decision to improve visible route quality with a conservative post-A* straightening pass.

Related: ../Home.md, ../modules/Route Smoothing.md, ../modules/Pathfinding.md, ../flows/Route Computation.md

Decision

Use a post-A* walkable straightener before the existing smoothing pipeline to reduce shallow grid staircases.

Context

Graph generation samples walkable polygons on a local grid and connects nearby nodes. A* can therefore return a valid but stair-stepped route, especially across angled or open walkable areas.

The route in the browser screenshot was a good example: the path was valid, but not how a person would naturally walk through the open area.

Why This First

Long visibility edges or Theta* would likely produce better native paths, but they affect graph size, worker routing, binary routing, WASM parity, and startup behavior.

The first implementation intentionally avoids changing graph generation or route search. It only rewrites the rendered per-floor coordinate sequence when the direct segment is explicitly validated as walkable.

Implementation

The helper is straightenWalkableStaircase() in src/pathfinding/route-smoothing-enhanced.js.

It:

• Computes cumulative route distance once for O(n^2) candidate scanning.
• Starts from an anchor point and tries the farthest future point first.
• Accepts a shortcut only when it is beneficial and isSegmentWalkable() returns exactly true.
• Returns the original coordinates when no safe shortcut is found.
• Records trace notes for blocked far shortcuts when tracing is enabled.

src/pathfinding/route-features.js then validates the full straightened route with isRouteSegmentWalkable() before replacing the working segment.

Tradeoffs

Benefits:

• Improves visual and user-followable routes without changing A*.
• Keeps wall/object/nonwalkable safety checks in place.
• Works for shallow staircases that angle-threshold zigzag logic misses.

Costs:

• Greedy straightening may not find the globally best simplified line.
• Diagnostics still only identify blocked shortcut candidates at a coarse level.
• Visual validation remains important because the algorithm is intentionally conservative.

Tests

• tests/route-smoothing.test.js covers direct helper behavior.
• tests/route-features.test.js covers route pipeline integration before simplification.

Future Work

• Add visibility edges during graph build.

• Evaluate Theta* or Lazy Theta* for true any-angle search.

• Add richer shortcut rejection diagnostics for blocker type and sample location.

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