Building Tiles

Calculon reads Valhalla's tiles, and can now build its own from an OSM extract. This page covers how an OSM way becomes a directed edge, and how to measure the result against the tiles Valhalla builds from the same data.

The aim of the first stage is parity: produce what Valhalla produces. Divergence comes after, once there is a yardstick to diverge from.

The pipeline

An extract becomes a graph:

flowchart LR
    PBF[("extract.osm.pbf")] --> READ[calculon-osm<br/>ways and nodes]
    READ --> LUA{{"vendored graph.lua"}}
    LUA -->|filtered| DROP[dropped]
    LUA -->|kept| GRAPH[graph<br/>cut ways at junctions]

The graph is then described, each pass answering one question about it:

flowchart LR
    GRAPH[graph] --> DENS[density<br/>road km per km²]
    DENS --> ATTR[attributes<br/>speed, surface, access]
    GRAPH --> CLASS[links · internal · loops<br/>reclassify, mark, cut]
    GRAPH --> ENH[enhance · turns<br/>angles, turn types]
    GRAPH --> TEXT[signs · lanes<br/>what a driver is told]

And the answers are numbered, written and compared:

flowchart LR
    ANS[the passes above] --> SC[shortcuts<br/>chains above local level]
    SC --> TILES[tiles<br/>number nodes and edges]
    TILES --> WRITE[calculon-tiles::writer]
    WRITE --> OUT[("tiles/2/000/769/709.gph")]
    OUT --> DIFF{{"calculon-tilediff"}}
    REF[("Valhalla's tiles")] --> DIFF

Density feeds attributes because speed depends on it: the same tertiary road is driven at 80 kph through fields and 40 kph through a town.

Tag interpretation ships with us

The rules that turn OSM tags into routing attributes are 2,500 lines of accumulated answers to questions like what access=destination means on a service road. Calculon does not port them: it runs the script in an embedded Lua interpreter, so the interpretation is identical to Valhalla's by construction.

The script lives in this repository at crates/calculon-osm/lua/graph.lua and is compiled into the binary, so building tiles needs nothing installed alongside Calculon. It started as Valhalla's (MIT, vendored with its licence and provenance); changing it is how the two will stop agreeing, deliberately.

flowchart TD
    W["way tags<br/>highway=residential<br/>oneway=yes<br/>maxspeed=30<br/>name=Rue Grimaldi"] --> P["ways_proc(kv, nokeys)"]
    P --> F{filter?}
    F -->|"1: nothing interesting"| X[dropped]
    F -->|0| KV["rewritten kv"]
    KV --> A1["auto_forward = true<br/>auto_backward = false"]
    KV --> A2["road_class = 6<br/>default_speed = 30"]
    KV --> A3["max_speed = 30<br/>lanes = 1"]
    KV --> A4["use = 0<br/>surface = (untagged)"]
    KV --> A5["name = Rue Grimaldi"]

The script answers per mode and per direction, with auto_forward, truck_backward, bike_forward and so on for eleven modes. Calculon folds those answers into the edge's access mask rather than deciding anything itself.

Ways become edges

An OSM way is as long as the mapper drew it. A graph edge runs from one junction to the next, so each way is cut wherever it shares a node with another way; the nodes in between are kept as shape.

flowchart LR
    subgraph OSM
        direction LR
        n1((1)) --- n6((6)) --- n2((2)) --- n3((3))
        n4((4)) --- n2
        n2 --- n5((5))
    end

Node 2 is shared by two ways, so it becomes a graph node and both ways are cut there. Node 6 belongs to one way only and stays as a shape point: a bend in the road, not a place to turn. Both ends of a way are junctions whatever their degree, which is what makes a cul-de-sac an edge rather than a dangling half of one.

How an edge gets its speed

Speeds follow Valhalla's SpeedAssigner::UpdateSpeed. The order matters: a signed speed is nearly final, while an inferred one is rewritten by where and what the edge is.

A slip road is decided first, and nothing else applies to it:

flowchart LR
    LINK{"link?"} -->|turn channel| TCF["× 1.25"]
    LINK -->|"ramp, signed"| KEEP1["keep the signed speed"]
    LINK -->|"ramp, urban motorway to primary"| RD["× 0.8"]
    LINK -->|"ramp, otherwise"| RF["× 0.85"]

An ordinary road takes a signed speed nearly as it stands:

flowchart LR
    T{"maxspeed signed?"} -->|"yes, rough surface"| TRIM["−10 above 50 kph<br/>−5 above 15"]
    T -->|"yes, smooth"| KEEP["keep as signed"]
    T -->|no| INF["inferred, see below"]

An inferred one is rewritten by where it is and what it is:

flowchart TD
    URBAN{"density > 8?"} -->|yes| CITY["urban table by road class<br/>89 / 73 / 57 / 49 / 40 / 35 / 30 / 20"]
    URBAN -->|no| DEF["class default_speed"]
    CITY --> RA{roundabout?}
    DEF --> RA
    RA -->|yes| HALF["× 0.5"]
    RA -->|no| USE{use}
    HALF --> USE
    USE -->|parking aisle| PA["15 kph"]
    USE -->|driveway or drive-thru| DW["10 kph"]
    USE -->|"other, rough surface"| HALVE["÷ 2"]
    USE -->|"other, smooth"| FINAL["final speed"]

How an edge gets its surface

OSM's surface values are open-ended, so they are matched on substrings the way Valhalla's parser does: fine_gravel is gravel, concrete:plates is smooth paving. Order matters, because unpaved contains paved.

flowchart LR
    S{"surface tag"} -->|"contains unpaved"| G1[Gravel]
    S -->|"paved / asphalt / concrete / cement / chipseal / metal"| PS[PavedSmooth]
    S -->|"sett / paving_stones / grass_paver / tartan"| P[Paved]
    S -->|"cobblestone / brick"| PR[PavedRough]
    S -->|"compacted / wood / boardwalk"| C[Compacted]
    S -->|"dirt / earth / ground / mud / natural"| D[Dirt]
    S -->|"gravel / pebblestone / sand"| G2[Gravel]
    S -->|"grass / stepping_stones"| PATH[Path]

With no tag, or one nobody recognises, the road class and use answer instead:

flowchart LR
    DEF{"road class"} -->|"residential and above"| PS2[PavedSmooth]
    DEF -->|"service or other"| U{use}
    U -->|track| D2[Dirt]
    U -->|"footway / path / bridleway"| C2[Compacted]
    U -->|"road / service / driveway / alley"| PS3[PavedSmooth]
    U -->|other| P2[Paved]

Density

Density decides urban speeds, and is measured as kilometres of road per square kilometre within a 2 km radius, squashed to 0–15. Doing that per node against every other node would be quadratic, so road length is accumulated into a grid of ~180 m cells and each cell sums its neighbours.

flowchart LR
    E[road edges<br/>excluding footways,<br/>ferries, car parks] --> CELL["accumulate length<br/>into 180 m cells"]
    CELL --> SUM["each cell sums its<br/>neighbourhood of cells"]
    SUM --> NORM["km of road ÷ km² of ground"]
    NORM --> REL["× 0.7, rounded, capped at 15"]
    REL --> SPEED["> 8 gives urban speeds"]

Every cell holding a node gets a value, not only the cells that hold road length themselves: a junction can fall in a cell whose roads are all next door, and reading zero there would call a city centre empty.

The neighbourhood has its corners cut. Valhalla keeps the cells satisfying nx² + ny² <= x_reach · y_reach (DensityCellId::neighbors in graphenhancer.cc), which at Monaco's latitude is 575 cells where the bounding rectangle holds 825:

flowchart LR
    R["bounding rectangle<br/>33 × 25 = 825 cells"] -->|"divide road length by this"| W["every density 1.44× too low<br/>a town reads as countryside"]
    N["cells with nx² + ny² ≤ 192<br/>575 cells"] -->|"divide by this"| C["matches Valhalla exactly"]

That factor was the whole density gap: the node-by-node scale implied by Valhalla's values against our raw measurement had a median of 1.443, and the ratio of the two cell counts is 1.435. Using the right neighbourhood took density from 5,362 differing edges to zero.

Measuring parity

# Build from the committed Monaco extract
cargo run -p calculon-build --bin calculon-build-tiles -- \
  test_data/monaco_custom_files/monaco-latest.osm.pbf /tmp/ours

# Compare against the tiles Valhalla built from the same extract
cargo run -p calculon-tiles --bin calculon-tilediff -- \
  --by-way --quiet test_data/monaco_tiles /tmp/ours

Where the totals say something differs, these examples say what:

# every edge's compared fields, sorted, for a set-wise diff
cargo run -p calculon-tiles --example edgedump -- <tiles>
# stored geometry, node angles, the spatial index, transitions
cargo run -p calculon-tiles --example shapedump -- <tiles>
cargo run -p calculon-tiles --example nodeheadings -- <tiles>
cargo run -p calculon-tiles --example binlist -- <tiles>
cargo run -p calculon-tiles --example transdump -- <tiles>
# one way, one name, one junction
cargo run -p calculon-tiles --example findway -- <tiles> 4229893
cargo run -p calculon-tiles --example findname -- <tiles> "Tunnel Rocher"
cargo run -p calculon-build --example whyinternal -- <extract.pbf> 423632259
# every edge's end node and opposing index agree with its shape
cargo run -p calculon-tiles --example checkends -- <tiles>
# the records beside the edges, and where each section starts
cargo run -p calculon-tiles --example signdump -- <tiles>
cargo run -p calculon-tiles --example accessrecs -- <tiles> --all
cargo run -p calculon-tiles --example headerdump -- <tiles>

headerdump is the one to reach for when two builds disagree on size rather than on content: it prints the counts and the offset of every section, so a missing run of records shows up as a shifted offset instead of thousands of differing bytes.

--by-way matches edges by OSM way id and the endpoints of their shape rather than by index, and this matters more than it sounds:

flowchart TB
    subgraph "by index, misleading"
        L1["ours edge 0<br/>Avenue d'Ostende, 50 kph"] -.compares with.-> R1["valhalla edge 0<br/>Rue Grimaldi, 25 kph"]
    end
    subgraph "by way, comparable"
        L2["ours way 4224972<br/>35 kph"] --> R2["valhalla way 4224972<br/>35 kph"]
    end

Two builders can describe the same graph and number it differently; every edge then looks wrong. By-way mode also leaves out the fields that are indexes into a particular numbering (endnode, localedgeidx, opp_index, opp_local_idx, name consistency), because those cannot agree until the ordering does.

Where the build stands

On Monaco, 5,379 nodes and 13,044 directed edges across 4 tiles. Against the tiles Valhalla built from the same extract, the bytes match: every one of the four tiles is identical apart from the stamps a build leaves on the header, which are the version string, the dataset id, the checksum and the date it was written. calculon-tilediff reports nothing differing, by index or by way.

Getting there meant matching the reference on things that are not in any tag:

Two rules decide the numbering everything else is counted against. A junction's place on the levels above local follows its place in the local tile it came from, because that is the order Valhalla walks when it builds a level. And a junction lists its shortcuts before the roads they stand for, because AddShortcutEdges runs before the rest of the node's edges are copied.

Still not built: complex (multi-via) restrictions, lane connectivity, predicted speeds, elevation, and the linguistic records that carry pronunciations. The single admin record is the nameless one Valhalla writes without an admin database, not real boundaries.

The index a search looks in

Bins are the grid that turns a coordinate into candidate edges. They are not part of any edge or node, so a tile can read correctly field by field and still route down the wrong road.

flowchart LR
    subgraph L2["local level tiles"]
        B["25 bins per tile<br/>every edge of every level"]
    end
    M["motorway edge<br/>level 0"] --> B
    S["street edge<br/>level 2"] --> B
    B --> Q["a point becomes<br/>the edges near it"]

Each edge is listed once, in the tile it starts in and any it crosses, but not in the one it ends in, and the two directions of one edge share a listing. Within a bin the order is fixed: the local roads first, then the levels above, each run by tile and then by place in it, which is how Valhalla sorts them so two builds of one extract come out the same. Binning per level instead, which is the obvious thing to do, hides every trunk road from snapping: a route out of Monaco started on a service road and took a kilometre and a half longer, while every field of both tile sets compared equal.

Links are filed by where they arrive

OSM tags a slip road with the class of the road it leaves, so the ramp off a motorway is motorway_link whether it drops onto another motorway or onto a village street. Taken at face value that files a supermarket entrance on the motorway level, where a long search will happily drive through it.

flowchart LR
    M["Motorway"] -->|"motorway_link<br/>tagged class 0"| L["link chain"]
    L --> R["Residential"]
    L -.->|reclassified| T["class: tertiary<br/>the lesser of the two, floored at tertiary"]

The same walk decides which links are turn channels rather than ramps: one direction only, no exit signs, no fork along the way, an ordinary road at both ends, and either under 200 m or shaped like a triangle with the junction it cuts the corner of. Monaco has 22 ramps and 66 turn channels, and we now agree with Valhalla on every one.

What stops a chain

A shortcut stops wherever a driver would notice the junction. The list is longer than it looks:

flowchart LR
    N["node with exactly two<br/>edges on this level"] --> Q{"any of these?"}
    Q --> A["class, use, surface, access,<br/>toll or destination-only differs"]
    Q --> B["conditional restrictions differ"]
    Q --> C["gate, toll booth or forbidden turn"]
    Q --> D["exit signs either side"]
    Q --> E["the node reaches a more important level"]
    Q --> F["three or more drivable roads<br/>and the chain turns"]

Any one of them stops the chain; none of them and it carries on.

The conditional restriction is the one that is easy to miss. Avenue Pasteur in Monaco carries motorcycle:conditional = no @ (22:00-07:00) on one of its three pieces, and that single tag splits what would otherwise be one 716 m chain into two of 313 m and 279 m.

Edges inside a junction

Where a dual carriageway crosses another, the stub joining the two halves is a road with a length and a name that nobody drives along: it is part of the turn. Marked as internal, narrative steps over it instead of announcing two left turns ten metres apart.

flowchart LR
    A["one-way in"] --> B(("·")) --> S["short stub"] --> C(("·")) --> D["one-way out"]
    S -.->|"under 32 m, one-way either side,<br/>turns that do not contradict"| I["internal"]

Valhalla decides this per direction and then copies the answer onto the opposing edge, so a stub that looks internal only one way round is internal both ways. Half of them keep their manoeuvre without that.

Shortcuts

Above the local level most junctions are not junctions: a motorway runs for kilometres through nodes where nothing joins it, split only because the mapper drew it in pieces. Each such chain gets a second edge laid over it, and the edges underneath are marked superseded so a search takes one or the other, never both.

flowchart LR
    A((junction)) -->|edge| B((pass-through)) -->|edge| C((pass-through)) -->|edge| D((junction))
    A -.->|"shortcut: one edge, whole chain"| D

A chain stops at any node a driver would notice: where a side road joins, where the classification or surface or access changes, at a roundabout, or where the node also exists on a more important level, since that is where a search changes levels. Two details matter for matching Valhalla: a shortcut carries no way id (it is not any one way), and its opposite is the shortcut over the same chain walked the other way, not the reverse of any single edge. A shortcut is also measured on the shape the tile keeps rather than on the coordinates it was built from, because that is what Valhalla reads back when it works out the length, the weighted density and the speed.

Hierarchy

A road is filed by its class, and the levels hold different roads rather than copies of the same ones:

flowchart TB
    subgraph L0["level 0, tile 4°"]
        P["Primary: 442 edges"]
    end
    subgraph L1["level 1, tile 1°"]
        S["Secondary and Tertiary: 1560 edges"]
    end
    subgraph L2["level 2, tile 0.25°"]
        R["Residential, Unclassified, Service: 11,042 edges"]
    end
    L0 <-->|transitions| L1
    L1 <-->|transitions| L2

A junction where a residential street meets a secondary road exists as a node on both levels, each carrying that level's edges, with a transition joining them. That is what lets a long search stay on level 1 and skip the streets underneath, and it is why a node count is larger than the number of junctions: Monaco has 4,931 junctions and 5,379 nodes.

Flags that come from the shape of the graph

not_thru and deadend cannot be read off a way; they are found by walking the built graph, and both now match Valhalla exactly.

flowchart TD
    E["edge, below tertiary"] --> W["walk outward from its far end<br/>never back through this edge"]
    W --> C1{"reach a road above tertiary?"}
    C1 -->|yes| T1["thru"]
    C1 -->|no| C2{"arrive back at the start node?"}
    C2 -->|yes| T2["thru"]
    C2 -->|no| C3{"nodes left to try?"}
    C3 -->|"yes, up to 256"| W
    C3 -->|no| NT["not thru: the region has no other exit"]

A dead end is simpler: the node an edge arrives at has exactly one drivable edge. An edge counts as drivable when either direction allows a car, so a one-way counts at both its ends. Counting only the leaving direction instead marked 1,361 edges wrongly where the right rule marks none.

Traps worth remembering

Edge info records are padded to 4 bytes. Valhalla's EdgeInfoBuilder::SizeOf rounds each record up, and the reader casts the record header straight out of the tile. An unpadded record is a misaligned dereference, which aborts rather than reads slowly.

Turn costs live on the edge a driver arrives on. Every edge carries, for each road they might leave by, the shape of that turn and a stop impact standing for the wait. Leaving them at zero costs every turn the same, which on a two kilometre route through Monaco came to 110 seconds of difference. They are indexed by the local edge index, which is why the order of a junction's edges has to match Valhalla's before any of it can be compared.

Angles and lengths are measured on the stored shape, not on the raw coordinates. A tile keeps its geometry in millionths of a degree, and Valhalla's enhancer reads it back out before it measures anything. Measuring a heading on the raw coordinates instead puts it a degree out, which is enough to move a turn across the boundary between a right turn and a slight one, and that changed which edges came out internal. Taking the angles off the rounded shape took node headings from 1,999 differing to 145.

A coordinate that lands exactly halfway is decided by a fused multiply-add. OSM stores ten-millionths, a tile stores millionths, so a coordinate ending in a 5 is an exact tie, and the reference tiles round about 83% of them down and the rest up. The rule is not in the rounding at all: Valhalla's OSMNode::latlng() computes lat7 * 1e-7 - 90 and the compiler contracts that into one fused multiply-add, which keeps the intermediate at full width. The tie a plain multiply would produce is therefore not quite a tie by the time it is rounded, and which side it falls depends on bits a separate multiply has already thrown away. Computing it as stored.mul_add(1e-7, -offset) reproduces every one of them: 0 wrong of 36,616 points, against 196 for rounding ties toward zero. A C++ probe with -ffp-contract=on and off settles it either way.

A running total kept in float decides a rounded speed. A shortcut's speed is its length over the time the chain takes, and Valhalla accumulates that time in single precision while working each term out in double. Keeping the total in double instead put one Monaco shortcut at 74 kph where the reference says 73: the sum came to 2.3999999 rather than the 2.4000001 a float lands on, and the rounding fell the other way. Shortcut::duration_for adds each term as (total as f64 + term) as f32, which is what C++ does to a float when a double is added to it.

A tile ends on an eight byte boundary, and the offset past the end is not zero. Valhalla pads the file up and sets lane_connectivity_offset to where the next thing would start, which for a tile with no lane connectivity is the padded end. Leaving both out is invisible field by field and shows up only as a handful of bytes at the tail.

encoded_shape::encode7 takes the scale factor 1e6; decode7 takes 1e-6. Passing the reader's 1e-6 to both rounds every coordinate to zero. The tiles still parse and still report the right number of shape points; they just all sit at null island, and snapping quietly finds nothing. The every_edge_has_geometry_a_router_can_use test asserts no shape decodes near (0,0) for exactly this reason: the failure looks healthy from the outside.