AI 요약
OsmAnd는 오랫동안 강력한 오프라인 지도 기능을 제공해 왔으나, 지도가 상세해짐에 따라 기존 A* 알고리즘의 탐색 속도가 저하되는 문제에 직면했습니다. 이를 해결하기 위해 OsmAnd는 고성능과 유연성을 동시에 갖춘 'Highway Hierarchy(HH) 라우팅' 엔진을 처음부터 새롭게 설계했습니다. 기존에 수백 GB의 용량을 요구하던 표준 알고리즘(CH)과 달리, HH 방식은 전 세계 자동차 데이터를 800MB 수준으로 압축하여 모바일 환경에 최적화했습니다. 이 기술을 통해 사용자는 수백 킬로미터의 긴 경로도 단 몇 초 만에 계산할 수 있게 되었으며, 도로 유형 회피 등 OsmAnd 특유의 세밀한 사용자 설정 기능도 그대로 유지할 수 있게 되었습니다. 결과적으로 OsmAnd는 오프라인 지도 앱의 강점인 데이터 효율성과 데스크톱 수준의 빠른 계산 속도를 모두 확보하게 되었습니다.
핵심 인사이트
- 100배 속도 향상: 새로운 HH 라우팅은 양방향 A* 알고리즘 대비 최대 100배, 기존 2단계 A* 대비 5~10배 빠른 경로 계산 속도를 제공합니다.
- 초경량 데이터 크기: 전 세계 자동차용 HH 라우팅 데이터 크기를 단 800MB로 최적화했으며, 전체 프로필을 합쳐도 20GB 미만을 유지하는 것이 목표입니다.
- 극대화된 유연성: 10개 이상의 라우팅 파라미터를 지원하여, 사용자 설정에 따라 1,024개 이상의 조합으로 맞춤형 경로 탐색이 가능합니다.
- 실시간 업데이트 대응: 대규모 사전 연산이 필요한 기존 방식과 달리, OsmAnd의 시간 단위(hourly) 지도 업데이트 시스템과 호환되도록 설계되었습니다.
주요 디테일
- 기존 방식의 한계: 과거 200~300km 경로 계산 시 100만 개 이상의 도로 세그먼트를 탐색해야 했으며, 이 과정에서 10~20초 이상의 대기 시간이 발생했습니다.
- 표준 솔루션(CH)의 거부 이유: OSRM의 전 세계 CH 데이터는 약 200GB에 달하며, 이는 OsmAnd의 오프라인 최적화 철학 및 지역별 지도 다운로드 모델과 맞지 않았습니다.
- 성능 실측 예시: 특정 경로(시작점 48.73829, 13.41383 / 종료점 47.94505, 7.73573) 테스트에서 HH x C++ 기반 라우팅은 복잡한 연산 과정을 획기적으로 단축했습니다.
- 구성의 정밀함:
routing.xml을 통한 세밀한 프로필 정의를 그대로 유지하면서 성능을 개선하여, 자전거 및 보행자 등 복잡한 경로 탐색 시에도 효율성을 보장합니다. - 압축 효율: 경쟁 모델인 CH 방식이 유럽 지역 데이터만으로도 수십 GB를 차지하는 데 반해, OsmAnd는 이를 혁신적으로 줄여 모바일 저장 공간 부담을 최소화했습니다.
향후 전망
- 다양한 이동 수단 확장: 자동차뿐만 아니라 자전거, 보행자 등 더 복잡한 알고리즘이 필요한 경로 탐색에서도 HH 라우팅의 효율성이 점진적으로 적용될 예정입니다.
- 오프라인 내비게이션 시장의 경쟁력 강화: 데이터 통신이 불가능한 지역에서의 내비게이션 성능이 비약적으로 높아짐에 따라 여행자 및 모험가 시장에서의 점유율이 더욱 확대될 것으로 보입니다.
출처:hackernews