Middle Earth: Getting directions (without passing through Mordor)

Google Maps has satellites and traffic data. I had a hand-drawn map and 4,119 road segments traced by hand.

First, you need roads

The road network was traced by hand in QGIS on top of Fenlon’s map and stored in the roads table as GEOMETRY(LineString, 4326). It ended up being 4,119 segments, sorted into a small medieval road hierarchy:

Road type	Segments	Notes
Royal Road	90	Imperial highways. Fast and rare.
Main Road	667	Solid inter-regional routes.
Regular Road	1,059	The everyday connecting road, and the baseline.
Trail	2,303	Paths and tracks. Most of the map.
off-road	—	No road at all.

The core idea: cost is time, not distance

This is what makes the routes feel real: the weight of every graph edge is not distance, it is travel time. And time depends on your speed, which depends on everything around you:

speed = base_speed × road_mult × biome_mult × altitude_mult
cost  = segment_length / speed        // seconds

Those multipliers are where the behaviour comes from. The real numbers, taken from TRANSPORT_CONFIGS:

Base speed — On foot: 5 km/h (1.39 m/s); on horseback: 12 km/h (3.33 m/s).

Road multiplier (walk / horse)

Road	Walk	Horse
Royal Road	×1.2	×1.4
Main Road	×1.1	×1.3
Regular Road	×1.0	×1.0
Trail	×0.8	×0.6
off-road	×0.6	×0.4

Biome multiplier (walk / horse)

Biome	Walk	Horse
Plain	×1.00	×1.00
Forest	×0.85	×0.75
Desert	×0.70	×0.60
Marsh	×0.55	×0.35

Altitude multiplier (walk / horse)

Terrain	Walk	Horse
Plain	×1.00	×1.00
Hills	×0.80	×0.70
Low mountains	×0.65	×0.50
Mid mountains	×0.50	×0.30
High mountains	×0.35	×0.15

Notice the difference between the two: a horse gains a lot on a Royal Road (×1.4) and loses much more than a walker in a marsh (×0.35 against ×0.55). Horses are fast but demanding, and that is why the best route on foot and the best route on horseback can be different roads.

Teaching each road what it crosses

A road segment doesn’t know its own biome or altitude — those are separate PostGIS layers. So when the roads are loaded, each one is enriched on the fly using LATERAL joins with ST_Intersects:

SELECT r.id, r.name, ST_AsGeoJSON(r.geom)::json AS geometry,
       ST_Length(r.geom::geography)             AS segment_length,
       COALESCE(b.type, 'plain')                AS biome_type,
       COALESCE(al.altitude_type, 'plain')      AS altitude_type
FROM roads r
LEFT JOIN LATERAL (
  SELECT type FROM biomes
  WHERE ST_Intersects(r.geom, geom) LIMIT 1
) b ON true
LEFT JOIN LATERAL (
  SELECT altitude_type FROM altitude_layers
  WHERE ST_Intersects(r.geom, geom)
  ORDER BY priority DESC LIMIT 1
) al ON true;

Now every road knows whether it runs through forest, over hills or across a swamp, and can price itself accordingly.

Building the graph (and why “everywhere is a node”)

Each road is a LineString of many points. The graph is built from every consecutive pair of vertices of every road, in both directions:

roads.forEach(road => {
  const coords = road.geometry.coordinates;
  for (let i = 0; i < coords.length - 1; i++) {
    addEdge(coords[i], coords[i + 1], road, getDistance(coords[i], coords[i + 1]));
  }
});

Vertices are keyed by rounded coordinates (lng.toFixed(5),lat.toFixed(5)), so roads that touch snap together into one connected network. Then it’s textbook Dijkstra: a distance table, a previous map for reconstruction, and a queue that always expands the cheapest node next.

The “last mile” problem: off-road legs

Real destinations aren’t sitting on a road vertex. A ruin in the wilds might be kilometres from the nearest track. So the router finds the closest road vertex to your start and end, runs Dijkstra between them, and adds two off-road legs — start→first-vertex and last-vertex→end — penalised at the off-road multiplier and measured precisely with ST_Length over geography (true metres on a sphere, not degrees on a flat plane).

The final answer comes back as GeoJSON with a tidy summary:

total_distance_km, on_road_distance_km, off_road_distance_km,
total_time_hours

Which answers the only question that really matters here: how many days is this going to take?

Lessons from routing a fantasy world

• Weight by time, not distance. The moment cost became “travel time,” terrain stopped being decoration and started making decisions.
• Let the data enforce the story. There is no hardcoded “avoid the volcano”. Expensive terrain does that work on its own.
• LATERAL + ST_Intersects is the glue. Keeping roads, biomes and altitude as separate layers and joining them at query time kept everything editable without re-baking the network.
• Writing it yourself is sometimes worth it. A hundred lines of Dijkstra that I understand completely were better than an extension I would have had to fight with.

Next: the roads were ready, but the world was empty. Time to fill it with things that watch you from the treeline. → Giving life to the map: entities and encounters