Weighting Indoor Routing Edges by Distance and Turn Cost

The cost model behind Indoor Routing Graph Construction. Shortest-by-distance is rarely the route a person would choose indoors, and the gap is almost entirely turns and vertical transitions — both of which can be priced in metres.

Why Distance Alone Produces Bad Routes

Two routes between the same points, with and without a turn cost Two routes drawn between the same origin and destination. The first, in orange, is the shortest by pure distance at 21 metres, but staircases through four right-angle turns. The second, in teal, includes a turn cost and is 22 metres — one metre longer — with a single turn. A caption notes that users prefer the second route consistently despite its extra metre. One metre longer, three fewer instructions distance only: 21 m, 4 turns with turn cost: 22 m, 1 turn one metre longer, three fewer instructions — users prefer the second every time shortest by distance shortest by distance + turns

Pure distance produces staircase routes. On a grid-like floor plate many paths are within a metre of each other, so the solver picks arbitrarily among them — and a turn cost is what makes the choice match what a person would do.

Indoor floor plates are close to grid-like, which means many distinct paths between two points have almost identical length. A solver minimising distance alone picks among them arbitrarily, and the one it picks is frequently a staircase of short segments and right-angle turns that is a metre shorter and considerably worse to follow.

The fix is to price the things that make a route hard to follow, in the same unit as the thing being minimised. A turn costs roughly four metres of walking in perceived effort; a level change costs roughly twelve. Once every term is metres-equivalent, one ordinary shortest-path solve trades them against each other correctly, and the weights remain explainable — “this turn costs about four metres” is a sentence anyone in the building can argue with.

The Cost Terms

The cost terms that make up an indoor edge weight A table of six cost terms. Distance is the edge length in metres and expresses the walk itself; without it routes ignore geometry. Turn cost adds about four metres-equivalent per ninety degrees and expresses the cognitive load of a turn; without it routes zig-zag. A level change costs about twelve metres per storey and expresses the effort of a vertical transition; without it routes hop between floors gratuitously. A door penalty of about 1.5 metres expresses the cost of opening a door. A crowding multiplier between one and 1.8 reflects measured congestion. A preference multiplier of about 0.9 on main signposted routes keeps traffic off back corridors. Six terms, one unit, one solve Cost term Typical What it expresses If omitted distance length in m the walk itself △ routes ignore geometry turn cost ● 4 m per 90° cognitive load of a turn △ zig-zag routes level change 12 m / storey effort of a transition △ gratuitous floor hopping door penalty 1.5 m opening a door routes prefer many small rooms crowding x1.0-1.8 measured congestion peak-time routes feel wrong preference x0.9 main routes signposted circulation routes use back corridors Every term is expressed in metres-equivalent so one shortest-path solve handles all of them.

Everything is converted to metres-equivalent. That keeps one shortest-path solve able to trade a turn against a detour, and it makes every term explainable to a non-engineer: “this turn costs about four metres of walking”.

Two of these terms need care.

Turn cost is a property of a node, not of an edge. The turn happens where two edges meet, so the cost depends on the pair. networkx weight functions receive (u, v, data) and cannot see the previous edge, which means turn costs need either a line graph (nodes become edges, edges become turns) or a custom search that carries the incoming bearing in its state. The line-graph transform is the simpler of the two and is what the example below uses.

Crowding is measured, not assumed. A multiplier applied from a schedule — “the atrium is busy at 12:30” — ages badly and is usually wrong on the day it matters. Where crowding is worth modelling at all, it should come from the same telemetry that feeds wayfinding API observability, and it belongs as a time-varying attribute rather than as a baked weight.

Minimal Working Example 

import logging
import math

import networkx as nx

logging.basicConfig(level=logging.INFO, format="%(asctime)s [%(levelname)s] %(message)s")
logger = logging.getLogger(__name__)

LEVEL_COST_M = {"stair": 14.0, "elevator": 20.0, "escalator": 10.0, "ramp": 16.0}


def bearing(g: nx.Graph, u: str, v: str) -> float:
    """Bearing of edge u->v in degrees."""
    a, b = g.nodes[u], g.nodes[v]
    return math.degrees(math.atan2(b["y"] - a["y"], b["x"] - a["x"]))


def turn_penalty(g: nx.Graph, prev: str, node: str, nxt: str,
                 per_90: float = 4.0, dead_zone: float = 20.0) -> float:
    """Metres-equivalent cost of changing direction at `node`."""
    delta = abs(bearing(g, node, nxt) - bearing(g, prev, node))
    delta = min(delta, 360.0 - delta)
    if delta <= dead_zone:                       # a gentle bend is not a turn
        return 0.0
    return per_90 * (delta - dead_zone) / 90.0


def weighted_route(g: nx.Graph, src: str, dst: str, profile: dict[str, float],
                   per_90: float = 4.0) -> list[str]:
    """Shortest path over a line graph, so turns can be priced between edge pairs."""
    if src not in g or dst not in g:
        raise KeyError(f"endpoint not in graph: {src if src not in g else dst}")

    lg = nx.line_graph(g)
    for (a, b) in lg.nodes():
        data = g.edges[a, b]
        base = data.get("length", 0.0)
        if data.get("cls") in LEVEL_COST_M:
            base += LEVEL_COST_M[data["cls"]]
        elif data.get("cls") == "door":
            base += 1.5
        lg.nodes[(a, b)]["cost"] = base * profile.get(data.get("cls", "corridor"), 1.0)

    def edge_cost(x, y, _):
        shared = set(x) & set(y)
        if not shared:
            return None
        node = shared.pop()
        prev = (set(x) - {node}).pop()
        nxt = (set(y) - {node}).pop()
        return lg.nodes[y]["cost"] + turn_penalty(g, prev, node, nxt, per_90)

    try:
        edges = nx.shortest_path(lg, _incident(lg, src), _incident(lg, dst), weight=edge_cost)
    except nx.NetworkXNoPath:
        logger.warning("no weighted path from %s to %s", src, dst)
        raise
    return _edges_to_nodes(edges, src)

The dead_zone is worth noting: a 12° bend where a corridor curves is not a turn a person perceives, and charging for it makes the solver prefer sharp corners over gentle curves, which is backwards. Only deviations beyond about 20° are priced.

Tuning the Turn Cost

Tester preference and distance penalty against the turn cost Two curves against the turn cost in metres-equivalent per ninety degrees. The share of routes testers preferred over the pure-distance route rises from 18 percent at zero turn cost to a peak of 78 percent at four metres, then falls to 61 percent at nine and 39 percent at fourteen as routes become noticeably long. The mean route length penalty rises steadily from zero to 2.6 percent at four metres and 15 percent at fourteen. Preference peaks near 4 m per 90°, then falls away 0 20 40 60 80 0 4 8 12 turn cost (metres-equivalent per 90°) preference (%) / penalty (%) routes preferred by testers (%) mean route length penalty (%) 4 m/90°: 78% preference for 2.6% extra distance

The preference curve has a peak, which is the whole finding. Too little turn cost gives staircase routes; too much sends people the long way round a building to avoid a corner.

The turn cost is the one parameter worth tuning against people rather than against a metric, and the method is straightforward: generate route pairs — one minimising distance, one minimising the weighted cost — for a sample of origin-destination pairs, show both to testers who know the building, and ask which they would walk.

The preference curve has a clear peak, which is the useful finding. At zero turn cost the weighted route is the distance route, so preference sits at chance. Preference rises steeply as staircase routes are eliminated, peaks around 4 m per 90°, and then falls as the solver starts sending people noticeably further to avoid corners — at 14 m per 90° routes are 15% longer and testers reject them.

Buildings differ. A long-corridor office peaks lower (turns are rare, so a large cost distorts little and helps little); a dense hospital ward peaks higher (many possible turns, more value in suppressing them). Running the study once per building type and carrying the value in configuration is proportionate; running it per building is not.

Common Errors & Fixes

Routes avoid lifts even for step-free users. The level-change cost is being applied on top of a profile multiplier that already prefers lifts, so the two compound. Level costs express physical effort and belong in the base weight; profile multipliers express permission and preference and belong at query time. Keeping them separate — as accessible routing profiles does — stops them multiplying.

Turn costs have no effect. They are being applied to the graph rather than to the line graph, so every edge is charged a fixed amount regardless of the turn at its end, which is just a uniform penalty on edge count. The tell is that route shape does not change as the cost rises, only total reported cost.

Weights are baked into the stored graph. This works until the first profile is added, at which point you need a second graph, and until the first corridor closure, at which point you need to apply it to both. Store length and cls; compute everything else at query time.

Escalator routes go the wrong way. Directionality is not a weight problem and cannot be fixed with one. Escalators need directed edges, applied as a constraint in the search rather than as a large cost — a sufficiently desperate solver will happily send someone up a down escalator if the alternative is expensive enough.

Integration Point

Weighting is the last stage of graph construction and the first thing the routing API touches. The graph produced by node placement carries length and cls on every edge and nothing else; this stage defines the function that turns those into a cost, and accessible routing profiles supplies the per-class multipliers layered on top.

Because the cost function lives beside the router rather than inside the graph, tuning the turn cost is a configuration change rather than a rebuild — which matters, since it is a parameter you will revisit after every round of user testing.

Frequently Asked Questions

Is a turn cost the same as preferring main corridors?

No, and conflating them produces odd routes. A turn cost prices the act of changing direction, wherever it happens; a corridor preference prices which corridor is used, independent of turns. They interact — main corridors tend to be long and straight, so preferring them incidentally reduces turns — but they fail differently. Turn cost alone will happily route someone down a straight service corridor; corridor preference alone will send them along the main route with six turns in it. Most buildings want both, at modest strength.

How do I price a lift against stairs fairly?

By measuring time, not effort, and then converting. A flight of stairs takes a typical walker about 20 seconds per storey; a lift takes 15 seconds of walking to reach plus a wait that varies from 5 to 90 seconds depending on the building and the hour. At a walking speed of 1.3 m/s those become roughly 26 and 26-135 metres-equivalent respectively, which explains why the default lift cost is higher than the stair cost and why measured wait times are worth feeding in where the telemetry exists. For step-free profiles none of this arithmetic applies, because the stair edge is blocked outright rather than priced.

Should crowding really change routes?

Only where it is measured and only where the alternative is genuinely comparable. Rerouting around a busy concourse is helpful when a parallel corridor exists and costs a few metres; it is unhelpful when it sends someone a hundred metres out of their way, and actively confusing when two people standing together get different routes because the crowding estimate changed between their requests. Cap the crowding multiplier — 1.8 is a reasonable ceiling — and make it a slowly varying signal rather than a per-request one, so routes stay stable enough to trust.

This page is a companion to Indoor Routing Graph Construction, part of the Indoor Mapping Architecture & Standards section.