Finding hills in a flat country with Phoenix and a Rust NIF

Most people who know me through my code don't know I'm a runner. I train a lot, mostly for mountain trail races: 50 km or more, with at least 2,000 m of climbing. I write about that at Ren met Kracht. I also live in the Netherlands, which is flat.

Where do the metres come from, then? A flat 20 km run gives you about 100 m of climb. That's not a mountain.

What does work is running a short, steep loop over and over. Twenty laps of 1 km with 40 m of climb each is 800 m. The hard part is knowing where those loops are. Route planners optimise distance or follow existing routes, and a 30 m global elevation model flattens exactly the ski hill or the dike you're looking for.

I built Heuvelradar for that. You pick where you want to start, how much you want to climb and how far you're willing to go. It finds the short, steep loops nearby and tells you how many laps you need.

A 680 m loop over a landfill hill in Zoetermeer's Buytenpark, drawn on the tilted relief map, with its highest point at NAP +14 m and its lowest at NAP −5 m. — Loop 2 of a search in Zoetermeer: 680 m a lap, 22 m of climb.

Twenty-three laps of a landfill hill

Take a real search. Drop the search point on Buytenparklaan in Zoetermeer, ask for 500 m of climb within 2 km, laps between 0.5 and 2 km, and you get seven loops. The second one, "Meerpad, Zoetermeer", runs 680 m over the landfill hill in the Buytenpark, from NAP −5 m to NAP +14 m and back (NAP is the Dutch sea-level datum). Each lap climbs 22 m.

That's 32 m of climb per kilometre, which the map calls pittig (tough). Twenty-three laps get you to 500 m, in 15.7 km. You download it as GPX, load one lap onto your watch, and run it 23 times.

The lap count is the least clever line in the codebase:

pub fn laps(&self, target: f64) -> u32 {
    (target / self.climb).ceil() as u32
}

Paths and a climb you can trust

The search reads the paths a runner may use from an OpenStreetMap extract of the whole country, follows the Dutch access defaults, and leaves out theme parks, golf courses, military land and paid nature reserves.

The heights come from the AHN, the national elevation model of the Netherlands, measured from the air in 0.5 m pixels. The search samples every path every 2 m on the ground model and smooths the result, because raw samples pick up centimetre noise and the flanks beside the path, and summing every wiggle inflates the climb.

I got that wrong first. My first settings, a 10 m smoothing window and a 0.5 m threshold, measured 17 to 26% more climb than Strava along the GPS tracks of three of my own hilly runs. These are the settings that survived:

/// Calibrated against Strava: see docs/spike.md.
pub const DEFAULT_PROFILE: Profile = Profile {
    spacing: 2.0,
    window: 20.0,
    threshold: 1.0,
};

A 20 m moving average, and a swing only counts once it rises or falls at least a metre. The lap is scored from its lowest point, so the place where the loop happens to start can't split a climb in two. On those same three runs it now comes out 5 to 13% above Strava: 204, 218 and 270 m where Strava said 187, 208 and 239 m.

Searching without trying every loop

A loop is a closed path the runner can repeat: back where it started, no junction visited twice, and a lap within the length range you asked for. A dense path network holds far too many of those to try them all.

The search is a beam search over simple paths. From each starting junction it grows paths edge by edge, and at each step keeps only the 32 most promising. Promising means: the climb density the path would have if it turned around and went home right now.

score: vert / (length + self.dist[w]),

vert is the climb collected so far, length the distance run, and dist[w] the shortest way back to the start from the junction the path just reached. A path that wanders off for a long, flat way back scores poorly long before it gets there.

Does a beam of 32 miss the best loop? On a real path network, a brute-force enumeration of every loop up to 1.2 km took 2.5 minutes. The beam search found the same best loop in 0.2 seconds, and wider beams found nothing better up to 2 km.

The bigger win came from noticing where the time went. In the towns I measured, 73 to 93% of the junctions the search started from found no loop of the 8 m per kilometre it needs, and they took most of its time. In those measurements a loop was never steeper than its steepest stretch, so the search now starts only next to a stretch of at least 8 m per km. That halves a search on one CPU, and at six of the seven places I compared it returns the same ten loops.

Ten hills, or fewer

Different hills, not variants. A loop is skipped when more than 40% of it runs within 75 m of a better result, so ten results aren't ten ways round the same mound.
Steepest and nearest, by turns. The list alternates between the steepest loop and the nearest one, so the hill right next to you isn't crowded out by steeper ones further away.
No flat filler. Loops under 8 m of climb per km are never offered. A loop under 15 m per km is dropped when it would take more than twice the distance of the best option to reach your target.

Where not one loop reaches 15 m per km, the map shows only the three steepest and says "Weinig heuvels hier" (not many hills here), with a way to search wider or climb less.

Why the search is Rust inside a Phoenix app

The web app is Phoenix, laid out the way mix phx.new does it, minus the database, mail, Gettext, LiveDashboard and LiveView pages. It serves the landing page, the map, and a small JSON API the map's plain JavaScript talks to.

The search is Rust. I ported the beam search and its scoring to Elixir to check: it found the same loops, to the digit, and took 8.5 to 12 times as long, on one core and on eight: 17 seconds instead of 1.6 for a 3 km search in a town centre, at the time.

The Rust stays, then, loaded into the BEAM as NIFs (native implemented functions, see erl_nif) with Rustler. That keeps everything in one process. When the app starts, before the endpoint listens, it loads the OpenStreetMap extract of the whole Netherlands (1.4 GB) into a NIF resource that lives outside the BEAM's heaps. That takes about 8 seconds.

A search doesn't run on the BEAM's schedulers at all. The NIF spawns a thread, searches there, and sends the loops back as an ordinary message:

#[rustler::nif]
fn start(map: ResourceArc<Map>, s: Settings, pid: LocalPid) -> NifResult<ResourceArc<Search>> {
    // ...
    std::thread::spawn(move || {
        // ... search the map, then:
        send(&|env| (&running, atoms::result(), &loops, &avoided, &shared).encode(env));
        send(&|env| (&running, atoms::done()).encode(env));
    });
    Ok(search)
}

On the Elixir side, the request's process waits for its mail:

defp await(running, search, timeout, outcome) do
  receive do
    {^running, :result, loops, avoided, shared} ->
      # ...
      await(running, search, timeout, outcome || {:ok, result(loops, avoided, shared)})

    {^running, :done} ->
      outcome
  after
    timeout ->
      Native.cancel(running)
      await(running, search, :infinity, outcome || :timeout)
  end
end

The real one also handles a link whose loop can't be read, a search that needs height sheets it hasn't cached yet, and one that failed.

Every request still runs in a BEAM process of its own, so a page or the health check never waits for a search, and Elixir checks the settings and writes the JSON the page gets. {running, :done} always comes last, also after a cancel or a panic, so nobody waits forever.

Why half a metre matters

You could take your heights from ready-made terrain tiles instead. I tried. Searched on a 5 m model, served in pixels of about 2.9 m, the same searches offered loops that hardly climb as if they did. In Zoetermeer, one showed 17.6 m of climb per km where the AHN at 0.5 m measures 10.3. Short steep hills read lower instead: Zoetermeer's steepest loop came out at 26.2 m per km against 28.7.

The fine model has problems of its own:

Pits. AHN6, the newest flight, measured the pit of Rotterdam Blaak's station 13 m under the square, and the footways beside and over it read its floor. Without care, a 512 m loop climbed out of the station at 29.6 m per km. The search now leaves out the floor of a pit no path runs on.
Bridges. The ground model leaves bridge decks out, so on longer bridges the search samples AHN's surface model, and only believes a deck that lands on measured ground at its ends.

Drawing the map the search sees

The map is MapLibre on OpenFreeMap's OpenStreetMap style, tilted 50° over the terrain with the heights raised two and a half times, so a low Dutch hill stands out without looking like a mountain.

What the map shows should be what the search uses. Ready-made terrain tiles stand on average 9 to 10 m above the ground in the woods of the Utrechtse Heuvelrug, and up to 30 m, because they include the trees. A wood drew as a range of hills and the real hills drowned in it.

Close in, the server draws the terrain tiles itself, from the 5 m AHN ground sheets of the same release the search measures that place on. The loops lie on the ground their climb was measured on.

Searched when you ask, kept in the link

The map doesn't serve precomputed results. Every search runs when you ask for it, and the first search in a new area downloads the AHN sheets it needs on the way. That can take a while: a search gets 30 seconds, and each sheet's samples are cached as soon as they're read, so trying again picks up where the last search stopped.

There are no accounts either. Your search lives in the URL, and so does the loop you have open. Links were harder: on two OpenStreetMap extracts ten months apart, 29% of the loops had left the results, so a link that says "result number 2" could open the wrong loop. A link carries the loop's own path instead, and opening it lays that path onto today's paths and measures it again, with today's access and today's heights.

What it doesn't do

It only finds loops. I measured an out-and-back hill repeat search at 13 places, and it beat the best loop by a quarter or more at only 3 of them. There it shortened the training on a hill the loops already showed, from 12.4 to 9.9 km at the Buytenpark. Where the loops were weak, a repeat didn't help either.

Access is only as good as OSM, so the app tells you to follow the signs on the spot. And it's the Netherlands only, with a search radius of at most 3 km.

Try it

Open heuvelradar.nl, drop the pin where you run, and set a climb target. It's free and there's nothing to sign up for. The site is in Dutch, but the numbers aren't.

Closing thoughts

Most of the effort went into making a number honest: deciding when a metre of climb is real and when it's a station pit, a bridge cable or a tree. I judge every ranking change by dropping the pin at places I know and asking whether a runner from there would agree.

If you try it near you, I'd like to know which climb it found. I'd like it even more when it finds nothing and you know there's a hill.