The Indoor Routing Engine (Technical Reference)

Scope

The companion to "Getting Indoor Directions": what a route is allowed to cross, how the graph is built, and how to read a quality score. For everyday use, read the other article instead.

One barrier definition, shared

Every pass that touches the graph now asks the same question of the same view. There is exactly one definition of what stops a person:

Six copies of this rule used to exist, only one of them elevation aware, which is how a soffit could sever the corridor beneath it in one pass and not in another. Consolidating them is what makes the measure and the passes agree.

A route through a doorway is not a wall crossing. The old check measured proximity to the door leaf, and a wall has thickness, so a non-perpendicular hop through an opening exited the cut slightly offset from the leaf and was scored as walking through the wall beside it. Crossings are now judged against the doorway rather than the leaf.

What connects to what

Nothing else grants passage. A room with no door in the source model has no access point, and it is honestly unreachable rather than quietly bridged.

A completed route on RQT-CLINIC: the plan, the Directions panel with From and To set, and the turn-by-turn steps crossing one floor to the next by stair.

Where pathfinding runs

nav_route() (migration 20260727050000_pgrouting_nav_route.sql) runs pgr_dijkstra in Postgres, next to the data, returning one row per traversal step.

sql
nav_route(
  p_facility_id uuid,
  p_from        uuid,
  p_to          uuid,
  p_accessible  boolean default false
) returns table (
  step integer, node_id uuid, mode text,
  source text, level_change integer, cost double precision
)

It replaced an in-process Dijkstra that fetched the whole facility graph per request: 225,260 edges over 226 sequential round trips on the reference facility, around 22 MB of edge rows, 5.7 s in Postgres before any pathfinding started. In the UI that read as a long hang followed by a failure. Sending 26 MB to find a path of a few dozen nodes was the design error, not the algorithm.

pgr_dijkstra needs bigint ids, so nav_nodes and nav_edges each carry a seq bigint generated once per row and never reused. Existing uuid keys are untouched.

A room destination is trimmed to its door

nav_route() ends a room-bound journey at the last door or entrance in the path, and starts it at the first one when the journey begins in a room. The untrimmed path is preserved as nav_route_untrimmed() for when you need the raw walk (migrations 20260823170000_a_route_ends_at_the_door_not_the_room_centre.sql and 20260824150000_trim_to_the_last_door_not_only_the_adjacent_one.sql).

It is a trim rather than a re-route: the path already passes through the door on its way to the centroid. No new nodes, no new edges, no change to the cost function.

The first implementation looked only at the step immediately before the room, so a path that came through the doorway and then took two or three more steps toward the centroid slipped past the guard. On one floor of a nine-storey office that was 8 of 20 routes still ending in the middle of the room, each having passed a door around step 41 of 44.

That last leg is not cosmetic, it manufactures defects. Of 30 final hops from a doorway to a room centre, 7 crossed wall or railing fabric over an average of 2.25 m: on a room with no interior mesh there is nothing between the door and the centroid, so the hop is drawn as one straight line through whatever stands in the way. Correcting the trim alone moved that building from 72% to 92%, with wall crossings down from 13 to 3 and unreachable pairs unchanged at 1. The unchanged figure is the one that matters: crossings fell because the leg is gone, not because journeys got shorter and stopped meeting anything.

Two consequences worth holding on to. It removes the argument for meshing small rooms, because a cupboard's centroid no longer needs anything to attach to. And it removes none of the argument for crossing an atrium or a parking deck, where things live in the space and you have to reach them.

An asset is reached through its room

Every asset now resolves to the room its centrepoint sits in (migration 20260824130000_an_asset_belongs_to_the_room_its_centrepoint_is_in.sql). Across every demo building, 95% of assets carry a room.

This matters because an asset is often unreachable in its own right. On the same nine-storey building, 1,362 of 5,122 asset nodes had no walkable edge at all, and of those close enough to reach a corridor, 360 were behind genuinely real wall fabric. They are behind walls, correctly. Routing via the room made 1,160 of them reachable, taking unreachable assets from 26.6% to 3.9%.

Resolving by centrepoint rather than by whole-outline containment is what makes the coverage: anything mounted on a wall (a radiator, a socket, a door closer) has an outline straddling the wall line, so it is contained by nothing.

Directions still lists assets as destinations, but asking for one now routes you to its room and marks the asset on the plan when you arrive. Routing at the asset itself was measurably harder: over 50 sampled journeys, room destinations ran 92% clean against 71.4% for asset destinations, because the final hop into an asset cannot be trimmed to a doorway and crosses fabric about a quarter of the time.

An asset with no room, or whose room has no node in the graph, still routes to the asset directly. A worse route beats no route, and something in the middle of a 350 m2 plant hall is better reached at the thing itself.

Cost function

A literal transcription of the previous loadSubgraph(), because the constraint was that accuracy be preserved exactly:

Edges are bidirectional with reverse_cost = cost, and level_change is negated when walked against its stored orientation. One quirk is reproduced rather than fixed: the penalties were an else if chain, so a virtual stair edge takes +8 and not +40. If that is ever corrected it must change in both places at once.

The weighting is read from route_cost, a stored generated column, computed at write time rather than 262,000 times per request. Asset-incident edges are dropped unless that asset is this request's own endpoint, reproducing the old noTransit rule.

Accuracy evidence is one 53-step cross-building route matching the previous implementation's node count and total cost of 130.58. That is a single check, not a suite.

Build order

mermaid
flowchart TD
    A[build_nav_graph_base] --> B[buildRoomWaypointMesh<br/>or network overlay]
    B --> C[buildStairAccessPoints]
    C --> D[apply_nav_mesh_passes<br/>door portals, thresholds, room interiors, lift landings]
    D --> E[prune_nav_edges_preserving_connectivity]
    E --> F[reattach_isolated_nav_nodes]
    F --> G[penalise_nav_edges_across_roofs]
    G --> H[connect_components_through_real_doorways]
    H --> H2[cut_openings_for_repair_doorways]
    H2 --> H2b[thin_nav_lattice_fast<br/>keep only what routes use]
    H2b --> H2c[prune_asset_incident_edges<br/>an asset is reached via its room]
    H2c --> H3[connect_routable_components]
    H3 --> I[ensureConnected<br/>virtual bridges, last resort]
    I --> J[nav_conformance_check]

Order is load bearing. The mesh passes need the base build's nodes, the prune needs the mesh's detour polylines rather than a straight line, and both repairs run before ensureConnected so a cheap fabric-aware fix claims a node before the expensive bridge does.

The graph is built dense and then thinned, not built lean. That is deliberate rather than a shortcut: thinning keeps the edges that solved routes actually traverse, and you cannot know which edges routes use until there are edges to route on. So the base build lays a proximity lattice, and thin_nav_lattice_fast removes what no room-to-room route needed. It runs inside the same build, so what lands in the database is the lean graph.

Two things make it cheap enough to run every time. It issues one pgr_dijkstra call per SOURCE rather than one per pair, because a single traversal from a room already reaches every other room; and rooms are the only destinations, since an asset is reached through its room. On a nine-storey office that is roughly 100 traversals where the per-pair form needed 20,896.

Thinning itself never touches an asset edge, whatever its source. No room-to-room route traverses one, so every asset edge looks unused; removing them as unused once orphaned 5,021 of 7,135 assets on a facility whose quality score did not move at all. They are removed by a separate pass with its own reason, below.

prune_asset_incident_edges then removes them deliberately. Once an asset is reached through its room, its attachment edges carry nothing: on RQT-CLINIC they were 7,135 of 14,007 edges, half the graph, loaded and skipped on every solve. Removing them is an accuracy fix before it is a size one, because nav_route re-enables an asset's own edges when that asset is an endpoint, and those edges were laid by proximity, so they can offer a shortcut through fabric. Over 50 journeys on RQT-DCR, room destinations scored 92 percent clean against 71.4 percent for asset destinations. An asset that resolves to no room keeps its edges, since a poor route still beats no route.

Latency is the mean of 40 room-to-room solves; RQT-CLINIC was 38.8 ms on the full lattice. Neither facility's quality score moved when the asset edges went, which is the point: the edges were carrying no route.

Five passes worth knowing:

Importing a surveyed network

build_nav_graph_network_overlay nodes an imported wayfinding pathway at every vertex, not only its two ends, because the source network's own connectivity rule can join two pathways at a shared interior point (migration 20260824100000_a_pathway_connects_at_every_vertex_not_just_its_ends.sql). Reading endpoints only left one reference import at 2,688 disconnected components; reading every vertex, 196.

Doors and entrances then re-attach to the nearest waypoint they have line of sight to, replacing a straight link that would otherwise cut through wall fabric (relink_places_by_visibility, migration 20260824110000_a_place_links_to_the_nearest_visible_waypoint.sql). Rooms and vertical nodes are excluded from this pass on purpose: a room node sits at its own centroid, inside its own enclosure, so a straight line from there almost never threads its doorway. It reaches the network through its own door instead, per the room-to-door rule above.

Reading a quality score

Two different things go wrong, they need different fixes, and a facility can be strong on one and weak on the other.

They pull against each other, which is why one number alone is dangerous. On RQT-CLINIC, deleting every wall-crossing edge produced a perfect 25 of 25 clean routes while pushing unreachable rooms from 8 to 31. Accuracy improved precisely because rooms stopped being sampled. A clean score rising while rooms-outside rises is the metric describing a smaller building.

Sampling caveat. routes_clean samples only rooms already in the main component. On RQT-CLINIC that reads 25 of 25 (100%), against 96.7% when every room is attempted and a no-route counts as a failure. Prefer the second reading.

What actually fixes it

A rebuild re-derives everything, and is not guaranteed to match an incrementally repaired graph. The passes are order dependent, and a from-scratch build can score lower than the graph it replaces.

Limitations