https://osmand.net/blog/fast-routing/
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.
(Score: 3, Informative) by VLM on Saturday February 28, @07:05PM (4 children)
Its a legit article although the cut and paste make it look like marketing.
Should I spoiler it? Why not... With a disclaimer I've probably messed some stuff up.
A* has no "more equal than others" nodes. So their first secret sauce is make routing faster by getting you to zones first then fine tune it. So you're routing to ... Chicago, not the parking lot at the museum of science and industry. They use a variant of Ford algo like RIP routing on networks to find weird borders; pretty cool.
I'm not entirely clear on their secret sauce #2... I think it summarizes to if a user is doing extreme customization it solves for plain old routing first then applies the extreme customizing and resolves to make it faster.
A* is cool and its still cool but its not optimized. For #1, most destinations are near most roads means if you're going there there's usually rich connectivity. For #2 if you're doing weird requirements its usually cheaper to "fit it in post production" because most demands have pretty obvious workarounds (like if you demand no toll roads there's usually a slow parallel farm road)
A* is one of those "leetcode" type interview questions or similar. Most folks with most languages can squirt out a tolerable one in maybe 100-200 LoC in an hour? Probably a lot easier to do it in a new language if you've ever done it before and it kinda demands an OO language paradigm to hold yer nodes although I assume you could do it in MSBASIC.EXE if you wanted to.
(Score: 2) by VLM on Saturday February 28, @07:11PM
I can summarize my summary:
At some cost in algo complexity and complicated data storage it can solve most routes faster most of the time by doing a two tier sort and by adding weirdo criteria at the end of the algo not at the start, which is not overly intuitive but I guess is makes sense.
What makes it an interesting story is you'd think in 2026 routing GPS would be boring but here's a new idea. Also this could NEVER have been invented by an AI because someone vibe coding would either have no idea what A* is so the LLM would toss it at em, or they'd ONLY know A* so they'd demand it by name. This was surely invented by a human as its got some creativity...
(Score: 2) by corey on Saturday February 28, @11:30PM (1 child)
Is there an iOS version? I’m using Organic Maps which is good but navigation is very mediocre.
(Score: 5, Interesting) by namefags_are_jerks on Sunday March 01, @12:43AM
I think it's a good option to just buy a cheap Android phone exclusively for OsmAnd.
I was traveling around Australia on a small motorbike, and loss and damage of equipment was a factor -- and there a $50 phone, running a (free) app (and Fdroid..) with offline maps for the entire country and backups to a microsd was the choice.
And as it happened, one time the phone was in the jacket pocket instead of in its box on the handlebars, it fell out at speed, and 12 caravans drove over the top of it -- at the next major town, I bought another cheap phone, backed-up and had everything restored within 20 minutes -- without needing a SIM, without internet access, without a phoneplan.
(Score: 1, Interesting) by Anonymous Coward on Sunday March 01, @10:20AM
I use the HERE WeGo app for offline stuff: https://play.google.com/store/apps/details?id=com.here.app.maps&hl=en [google.com]
It used to be better. It used to still work when I'm flying in an airplane (in airplane mode of course 😉). It was kind of cool to see the app still get the correct location on the map, presumably correct altitude and speed (800-900+kph).
But now it doesn't work for such stuff. Not sure why they removed that ability. There are apps for flying of course.