OsmAnd's Faster Offline Navigation

2026-02-26T21:34:57.000Z·★ 97·13 min read

Offline navigation is a lifeline for travelers, adventurers, and everyday commuters. We demand speed, accuracy, and the flexibility to tailor routes to our specific needs. For years, OsmAnd has...

Offline navigation is a lifeline for travelers, adventurers, and everyday commuters. We demand speed, accuracy, and the flexibility to tailor routes to our specific needs. For years, OsmAnd has championed powerful, feature-rich offline maps that fit in your pocket. But as maps grew more detailed and user demands for complex routing increased, our trusty A algorithm, despite its flexibility, started hitting a performance wall. How could we deliver a 100x speed boost without bloating map sizes or sacrificing the deep customization our users love?

The answer: OsmAnd's custom-built Highway Hierarchy (HH) Routing. This isn't your standard routing engine; it's a ground-up redesign, meticulously engineered to overcome the unique challenges of providing advanced navigation on compact, offline-first map data.

Start:48.73829, 13.41383
Finish:47.94505, 7.73573
OsmAnd Web Preview:View Route

HH x C++ Fast Routing	Traditional Routing A*2-phase
Calculation time: 13 sec	Calculation time: 36 sec

100x speedup is achieved by comparing HH with bidirectional A. 2-phase A already uses many heuristics which don't always create an optimal route and still 5-10x slower.

Why Standard Solutions Failed[](https://osmand.net/blog/fast-routing/#why-standard-solutions-failed "Direct link to Why Standard Solutions Failed")

OsmAnd has always been about putting you in control. Our original A routing engine, configurable via [routing.xml](https://github.com/osmandapp/OsmAnd-resources/blob/master/routing/routing.xml), offered immense power. You could define intricate profiles, avoid specific road types, and truly personalize your journey. With maps optimized for minimal storage (the entire planet's car data for our new HH-routing is around a mere 800MB!), OsmAnd was a lean, mean navigating machine.

However, this flexibility came at a cost for complex routes:

_\_The A\_ Wall:_* Calculating a 200-300km car route (or even shorter bicycle/pedestrian paths) could mean visiting over a million road segments, taking 10-20 seconds. For longer trips, this wait could become frustrating.

We explored standard advanced algorithms like Contraction Hierarchies (CH), known for their speed. But they presented their own set of deal-breakers for OsmAnd:

Flexibility Clash: CH typically pre-calculates optimal paths. Supporting OsmAnd's 10+ routing parameters (leading to over 1024 combinations per profile!) would be impossible with standard CH.
Storage Nightmare: A CH car profile for a region can be massive (e.g., OSRM's Europe is tens of GBs, their global car profile around 200GB for just one profile). Our goal was to keep _all_ profiles and parameters for the _entire planet_ well under 20GB.
Regional Map Dilemma: Users download individual countries or regions. CH usually requires processing the entire road network globally, which doesn't align with OsmAnd's flexible map management.
Update Impracticality: The extensive pre-processing for CH makes it unsuitable for frequent updates, let alone OsmAnd's goal of supporting near real-time changes through hourly map updates.

The challenge was clear: achieve a quantum leap in speed while preserving extreme flexibility, minimal storage, regional map support, and dynamic update capabilities. Standard Highway Hierarchies were a starting point, but we needed something more - a uniquely OsmAnd solution.

Secret Sauce #1: Two-Level Routing[](https://osmand.net/blog/fast-routing/#secret-sauce-1-two-level-routing "Direct link to Secret Sauce #1: Two-Level Routing")

The core of OsmAnd's HH-Routing is an elegant two-level hierarchy built upon "area clusters."

Area Clusters: The map is intelligently segmented into numerous small regions or clusters.
Border Points: Each cluster has a limited number of defined "border points" - these are the gateways in and out of the cluster.
Shortcuts: For common scenarios, we pre-calculate the travel time/distance (the "shortcut") between border points _within the same cluster_ and also to border points of _immediately adjacent_ clusters.

This map illustrates the OsmAnd routing concept. The route starts in the Start Area Cluster (221558), moves to the nearest Border Point, and continues through precomputed Shortcuts across intermediate clusters. It then enters the Finish Area Cluster (221536) via another border point and finishes using local roads. This method speeds up routing by combining local search with efficient inter-cluster shortcuts.

The real magic, our Secret Sauce #1, lies in _how_ these border points are selected. Naive approaches quickly fail:

Randomly selecting border points or using simple geometric divisions (squares/hexagons) results in too many border points per cluster (50-80). This leads to a shortcut explosion (N*(N-1)/2 shortcuts), making the files large and and calculations slow.
We even tried building hierarchies with 2-3 levels, but the number of shortcuts grew too fast for higher levels if we generated a full graph inside each cluster.

The "Parking Lot" Insight: Imagine a vast shopping mall parking lot with thousands of individual parking spots and internal lanes (representing road segments within a cluster). No matter how complex it is inside, there are usually only a few key exits to the main roads. Our goal was to identify these natural "exits" for each map cluster. For instance, the complex road network around Amsterdam Airport Schiphol (see on OpenStreetMap) has many internal roads but limited primary access points.

We wanted a scenario where, say, 5 well-placed border points could efficiently represent an area with 5,000 internal points and 10,000 road edges. This would reduce those 10,000 edges to just 5*4/2 = 10 shortcuts for routing _through_ that cluster at a high level - an incredible 1:1000 point ratio and a 30x reduction in edges to consider for the high-level path!

The Algorithm: Ford-Fulkerson to Find the Bottlenecks To find these crucial border points, we employed a clever technique based on the Ford-Fulkerson algorithm. By simulating "flooding" roads with traffic from random start/end points, we could identify the natural bottlenecks - the "minimum cut" in graph theory terms. These bottlenecks became our border points.

Universality is Key: Crucially, this distribution of border points is agnostic of routing speed profiles. It's based only on whether a road is _passable_ or not. This means the _same set of clusters and border points_ can be used for all car routing profiles (default, shortest, fuel-efficient) and all bicycle profiles (default, prefer flat terrain, etc.). Only the _travel time/cost values_ of the shortcuts between these points change based on the profile. This is a massive factor in keeping storage down - map data only increased by about 0.5% per profile to store this HH-Routing structure!

Just look at the numbers for processing the entire planet for a car profile:

Original OSM: ~2.07 billion points, ~2.42 billion edges
Resulting HH structure: ~3 million border points, ~541,000 clusters
Estimated shortcuts: ~91 million (a manageable number for global routing)

How OsmAnd Builds Routes[](https://osmand.net/blog/fast-routing/#how-osmand-builds-routes "Direct link to How OsmAnd Builds Routes")

So, how does OsmAnd use this structure to calculate your route at lightning speed? It's a multi-step process:

A. Preprocessing (Done by OsmAnd when new maps are prepared):

Cluster & Border Point Definition: The map is divided into clusters, and border points are identified using the Ford-Fulkerson based method.
Shortcut Pre-calculation: For the most commonly used speed profiles, the travel costs (time/distance) for shortcuts between border points within each cluster are pre-calculated and stored. (Each border point effectively has an "entry" and "exit" aspect for directed travel).

B. User Route Request (Query Time - this is what happens on your device):

Step 1: Connect to the Hierarchy (Your Local Area):

* OsmAnd identifies the clusters containing your start and target points.

* It then uses the standard Dijkstra algorithm on the _detailed local map_ within your start cluster to find the best paths from your actual start location to _all_ border points of that starting cluster.

* The same is done for your target point within its own cluster (finding paths from all its border points to your actual destination).

* This is quick because it's operating on a very small, localized part of the map.

Step 2: Route on the Abstract Graph (The "Highway" Part):

* Now, OsmAnd performs another Dijkstra search, but this time on the much smaller "base graph." This graph consists _only_ of the border points and the pre-calculated shortcut values between them.

* This step rapidly finds the optimal sequence of border points and shortcuts to get from your start cluster's periphery to your target cluster's periphery. It's incredibly fast because it's ignoring all the tiny roads _within_ intermediate clusters.

Step 3: Refine with Detailed Shortcuts (Applying Secret Sauce #2):

* The result from Step 2 is a high-level route - a sequence of shortcuts connecting border points.

Now, for _each_ shortcut in this sequence, OsmAnd runs its highly optimized A algorithm on the _detailed map_, but strictly limited to the small area of the cluster that shortcut belongs to.

For example, a 500km route might be broken down into ~100 such shortcuts. If each A shortcut calculation explores 100-1000 detailed road segments, the total detailed segments visited by A might be around 10,000-50,000. Compare this to the 1,000,000+ segments the old A might have needed for the entire route!

This combination - localized Dijkstra, super-fast abstract graph traversal, and highly localized A* refinement - is what delivers the 100x speedup.

Secret Sauce #2: Adaptive Routing[](https://osmand.net/blog/fast-routing/#secret-sauce-2-adaptive-routing "Direct link to Secret Sauce #2: Adaptive Routing")

Speed is fantastic, but not if it means sacrificing the features OsmAnd users rely on. This is where our Secret Sauce #2 comes into play - ensuring HH-Routing remains incredibly flexible and dynamic:

Full Parameter Support: Because the final shortcut refinement (Step 3 above) uses A* on detailed maps _within each cluster_, all your specified parameters are naturally incorporated:

* Avoiding specific road types or toll roads.

* Adding penalties or preferences for certain roads.

* Following all the nuanced rules in your custom [routing.xml](https://github.com/osmandapp/OsmAnd-resources/blob/master/routing/routing.xml) profiles.

Handling Live Updates & Dynamic Changes: What if a bridge is closed due to a live map update you just downloaded?

If the A calculation for a shortcut (in Step 3) finds it's now impassable, or if its actual detailed cost is significantly different (e.g., >20%) from the pre-calculated shortcut value:

* Option 1: The system can update the cost of that specific shortcut in the base graph and quickly re-run the Dijkstra search (Step 2) on the abstract graph to find an alternative high-level path.

* Option 2: For very localized changes, it might even re-evaluate all shortcuts within that one affected cluster.

* Minor road updates (like those in map data that might be a few months old if you're using maps from different regions) usually result in negligible cost differences for shortcuts, so the pre-calculated values remain effective.

Graceful Fallback for Extreme Customization:

What if you create a truly unique routing profile that's wildly different from the common ones for which shortcuts were pre-calculated? The system is smart. If it detects that too many shortcuts (~50, for example) need on-the-fly recalculation and deviate significantly, it might determine that falling back to the original, comprehensive A algorithm for the _entire route_ would actually be faster than doing many small, heavily modified A* calculations.

Users can also manually switch to the "A" routing engine in settings if they know their profile is highly experimental or unique.

Real Benefits for OsmAnd Users[](https://osmand.net/blog/fast-routing/#real-benefits-for-osmand-users "Direct link to Real Benefits for OsmAnd Users")

This complex engineering translates into tangible benefits:

Blazing Speed: The 100x average improvement means route calculations, especially for longer journeys, are now dramatically faster.
Tiny Footprint: Our HH-Routing data adds only 0.5% to 1% to OsmAnd's already incredibly compact map sizes. The entire planet's car routing data is around 800MB!
Full Customization Power: All the beloved flexibility of [routing.xml](https://github.com/osmandapp/OsmAnd-resources/blob/master/routing/routing.xml) and detailed routing parameters is retained.
Works with Regional Maps: Download only the countries you need. HH-Routing seamlessly calculates routes across the borders of your downloaded map files (as long as they are compatible, see limitations). Clusters that overlap a region's boundary are included within that region's data.
Supports Frequent Updates: The architecture is designed to work with OsmAnd's hourly map updates, allowing routing to adapt to fresh road information.
Future-Proof: This structure makes it much easier to implement features like alternative route suggestions based on these key border points.

Important Routing Notes[](https://osmand.net/blog/fast-routing/#important-routing-notes "Direct link to Important Routing Notes")

No system is perfect, and OsmAnd's HH-Routing has a few considerations:

Highly Divergent Profiles: For routing configurations that are not pre-calculated as common scenarios and whose costs vary too much from default configurations, the original A algorithm might still be faster (and is often used as an automatic fallback).
Map Version Synchronicity (Important!): For HH-Routing to work correctly when a route crosses multiple map files (e.g., different countries or regions), all those map files MUST be from the same generation date (i.e., downloaded from OsmAnd around the same time, based on the same underlying OpenStreetMap data version and pre-calculation run).

* If you try to route from a map of France updated in May with a map of Germany updated in April, HH-Routing may not be compatible across the border. You would need to update all relevant maps to the same version.

* This doesn't mean all maps must be _brand new_, just _from the same batch/pre-calculation period_.

Map Release Schedule: The intensive preprocessing required to generate all these routing profiles for the entire planet takes about 2-3 days. This means new map updates are now typically released around the 5th of each month, instead of the 2nd.

Smart Engineering Delivers[](https://osmand.net/blog/fast-routing/#smart-engineering-delivers "Direct link to Smart Engineering Delivers")

OsmAnd's HH-Routing is more than just an algorithm; it's a testament to innovative problem-solving. It's a carefully engineered system born from the need to overcome specific, demanding constraints: the desire for blazing speed, minimal storage, complete routing flexibility, regional map support, and adaptability to fresh data.

By cleverly identifying crucial "bottleneck" border points, creating a universal two-level hierarchy, and dynamically refining routes with our optimized A* engine, we've managed to deliver a vastly superior navigation experience. It's a win for every OsmAnd user who relies on fast, dependable, and customizable offline navigation.