Back Original

OsmAnd's Faster Offline Navigation (2025)

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.

HH x C++ Fast RoutingTraditional Routing A*2-phase
Calculation time: 13 secCalculation time: 36 sec
HH exampleA2 example

Note

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​

OsmAnd has always been about putting you in control. Our original A* routing engine, configurable via 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:

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

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​

The core of OsmAnd's HH-Routing is an elegant two-level hierarchy built upon "area 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.

OsmAnd HH

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

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.

OsmAnd Schiphol

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:

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):

  1. Cluster & Border Point Definition: The map is divided into clusters, and border points are identified using the Ford-Fulkerson based method.
  2. 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):

  1. 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.

  2. 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.

  3. 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​

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:

Real Benefits for OsmAnd Users​

This complex engineering translates into tangible benefits:

Important Routing Notes​

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

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.

Join the Conversation!​

We're excited about what HH-Routing brings to OsmAnd!

For additional guidance: