Enabling Valhalla routing to use pedestrian areas

Have you ever tried to use Valhalla for pedestrian routing? It works well — until it doesn’t.

In a project at DroidSolutions we had to calculate pedestrian routes in a bigger German city. That city has several open pedestrian-only areas mapped in OpenStreetMap, and exactly this mapping caused trouble: Valhalla refused to calculate any route across these areas. It walked users around every square instead of over it, which made some routes much longer than they needed to be.

Why Valhalla skips pedestrian areas

A quick search leads to issue 42 on GitHub — exactly our problem, with the troublesome file already linked. Search for “area” in graph.lua and you find one if-statement that removes all areas from the computation:

--toss actual areas
if kv["area"] == "yes" then
  return 1
end

It is understandable that the Valhalla developers have not solved this properly, because doing it correctly is genuinely hard. You would have to compute virtual ways across each area and pick good ones — for example by rasterizing the polygons and using random walks to find suitable paths.

Then it gets complicated. Valhalla routes on pre-computed routing tiles, so every graph edge has to be known while the tiles are rendered. For ways that is straightforward: they already form something like a graph and only need converting. For areas you would need to invent hypothetical ways inside each polygon and connect them to the surrounding graph. Done naively, that produces a huge number of ways even for small areas.

You could add rules to cut that number down, but there will always be edge cases. And the math is only half of it: you also need to understand how humans map the world in OpenStreetMap — the community’s rules and concepts — and what a human user actually expects a route across a square to look like. POIs and the structure of the area itself would have to feed into it.

The workaround: route along the polygon edges

I had neither the time nor, honestly, the knowledge to build the proper solution. So what is good enough? Treat the polygon edges as ways and feed them into Valhalla’s routing tiles. That means changing the “toss actual areas” snippet (the commit):

--toss actual areas
if kv["area"] == "yes" then
  if kv['pedestrian_forward'] == "true"
  or kv["pedestrian_backward"] == "true"
  or kv["bike_forward"] == "true"
  or kv["bike_backward"] == "true" then

  else
    return 1
  end
end

Put this in your graph.lua, render your tiles, and it works. The routes are not pretty — you get a path that hugs the border of the square instead of crossing it directly — but your users finally get a route through pedestrian areas at all, and the absurd detours are gone.

There is also a docker image you can use for your own experiments. Please do not run it in production: we were still testing this fix ourselves, and it may have unexpected side effects.

Routing along polygon edges is a workaround, not a solution. If you have ideas or working prototypes for the real thing, I would like to hear about them.