"/home/yossef/notes/git/projects/maplibra/decisions/Multi-Candidate A-Star.md"

path: maplibra/decisions/Multi-Candidate A-Star.md

- **fileName**: Multi-Candidate A-Star
- **Created on**: 2026-06-16 00:48:42

Multi-Candidate A-Star

Purpose: Why routing uses multiple start/goal candidates instead of a single nearest-node snap.

Related: ../Home.md, ../modules/Pathfinding.md, ../modules/Snapping.md

Decision

When computing a route, the system generates multiple snap candidates for both start and goal, then evaluates paths between all viable pairs to find the best overall route.

Problem

A user clicks on a room. The "nearest graph node" might be on the wrong side of a wall, through the wrong door, or in a dead-end corridor. Snapping to a single node often gives suboptimal or impossible routes.

Solution: Multi-Candidate Fan-Out

1. Snap phase produces ranked candidates from different strategies:

   • Door-based: nodes near room doors
   • Room-exit: nodes outside the room polygon
   • Nearest walkable: closest graph nodes by distance
   • Nearby doors: doors within configurable radius

2. Routing phase tries A* for each (start, goal) pair:

   • Worker can use FIND_MULTI_CANDIDATE_PATH for efficiency
   • Falls back to NM individual A calls if needed
   • Picks path with lowest total cost (path cost + snap penalties)

3. Component filtering skips pairs where nodes belong to different graph components (disconnected areas).

Snap Candidate Scoring

Each candidate gets a rankScore based on:

• Base cost (distance from user click to snap point + snap point to node)
• Source penalty: door=0.25, room-exit=0.35, walkable=0.4, generic=0.5
• Clearance bonus: wider corridors preferred

Why Not Just Nearest Node

Important Files

• src/pathfinding/snapping.js — Candidate generation + scoring

• src/pathfinding/route-compute.js:1284-1450 — selectBestPath

• native/routing/route_kernel.c:232-320 — WASM multi-candidate A*

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