Tile Format

Calculon reads Valhalla's binary graph tile format. This page describes how tiles are structured, loaded, and cached.

Hierarchy levels

The road network is split into three hierarchy levels:

Higher-level tiles (0, 1) duplicate important roads from lower levels, creating shortcuts that let the router skip over local streets during long-distance searches.

GraphId

Every node, edge, and tile is addressed by a GraphId — a single u64 packing:

Edge IDs are formatted as level/tileid/id in API responses (e.g., 2/751073/456).

Tile structure

Each tile is a binary file containing, in order:

┌─────────────────────────┐
│ TileHeader              │  Fixed size: tile metadata, counts, offsets
├─────────────────────────┤
│ NodeInfo[]              │  40 bytes each: position, edge index, access, density
├─────────────────────────┤
│ NodeTransition[]        │  Transitions to other hierarchy levels
├─────────────────────────┤
│ DirectedEdge[]          │  24 bytes each: endnode, speed, classification, access
├─────────────────────────┤
│ EdgeInfo[]              │  Variable length: street names + encoded shape
├─────────────────────────┤
│ Spatial bins            │  5×5 grid for fast candidate edge lookup
└─────────────────────────┘

NodeInfo (40 bytes)

• Latitude/longitude (encoded as offsets from tile base)
• Edge index and count (which directed edges start here)
• Access mask (which travel modes can traverse)
• Density (0-15, traffic density for turn cost scaling)
• Admin index, traffic signal flag, drive-on-right flag
• Per-edge headings (compressed, for turn angle computation)
• Transition count (number of edges crossing to other levels)

DirectedEdge (24 bytes)

Bit-packed fields across 6 words:

• End node GraphId
• Speed (kph), length (meters)
• Road classification, surface type, use type
• Forward/reverse access masks
• Shortcut flag, internal flag, toll, destination-only
• Turn type, stop impact, name consistency (per pair with predecessor)
• Opposing edge index (for traversal and per-pair data lookup)

EdgeInfo (variable)

• Encoded polyline shape (the geometry of the road segment)
• Street name list (zero or more null-terminated strings)

Spatial binning

Each tile contains a 5×5 grid of spatial bins (25 bins total). When snapping a coordinate to the nearest edge, the router:

1. Determines which bin the coordinate falls in
2. Checks edges in that bin and neighboring bins
3. Projects the point onto each candidate edge
4. Returns the closest match with snap fraction

This avoids scanning all edges in a tile.

Tile loading and caching

GraphReader manages tile loading with a three-level cache:

Tiles are memory-mapped using memmap2. The OS page cache handles eviction. The --cache-size option controls the shared cache capacity (default: 200 tiles).

Binary parsing safety

Tile parsing uses unsafe for zero-copy pointer access. Every unsafe block is:

• Bounds-checked against the tile header's declared sizes
• Validated that offsets don't exceed file length
• Documented with safety comments
• Only used on little-endian platforms (compile-time check)

Obtaining tiles

Calculon uses standard Valhalla tiles. To generate tiles from OpenStreetMap data:

# Using the included script (requires Docker)
make tiles

# Or manually with Valhalla
docker run -v /path/to/osm:/data ghcr.io/valhalla/valhalla:latest \
  valhalla_build_tiles -c /data/valhalla.json /data/extract.osm.pbf

Tiles are written to the configured tile directory, organized in subdirectories by level and tile ID.