Привет, Хабр! Меня зовут Вадим.
Однажды вечером я сидел и думал: «А что если взять геопространственную индексацию , которую Uber и другие компании использует для своих сервисов, написать алгоритм генерации лабиринта, а потом искать путь через этот лабиринт прямо на реальной карте?» Звучит как что-то бесполезное? Возможно. Но разве это когда-нибудь останавливало?
Так родился проект qHexWalker — приложение на Qt 6, которое визуализирует гексагональные ячейки H3 на карте через MapLibre Native Qt, генерирует в них лабиринт алгоритмом Прима и находит кратчайший путь с помощью двунаправленного A*.
Почему я выбрал именно h3?
Ведь есть, например, Geohash, s2, Hexbin, возможно, что-то еще. Во-первых, это красиво и open-source с хорошей документацией https://h3geo.org, во-вторых, в гексагональной сетке у каждой ячейки ровно 6 соседей, и все они на одинаковом расстоянии. Никаких диагоналей, никаких двойных весов. Красота!
Более того, исследование показало, что при поиске пути на гексагональной сетке branching factor (коэффициент ветвления) можно снизить до 3, если учитывать направление движения. Это напрямую влияет на производительность — меньше узлов для обхода, быстрее находим путь.
Если коротко: h3 разбивает всю поверхность Земли на гексагональные ячейки с 16 уровнями детализации от 0 до 15.
Разрешение | Средняя площадь ячейки |
|---|---|
0 | 4,357,449 км² |
5 | 252 км² |
9 | 0.1 км² |
15 | 0.9 м² |
То есть можно работать как с огромными регионами, так и с точностью до квадратного метра.
Как это работает под капотом?
H3 использует икосаэдр (двадцатигранник) как основу для проекции земного шара. Каждая грань икосаэдра проецируется с помощью гномонической проекции, что минимизирует искажения размера ячеек (привет, проекция Меркатора с её гигантской Гренландией).
Важный момент: невозможно замостить сферу только гексагонами. Поэтому на каждом уровне разрешения присутствует ровно 12 пентагонов (пятиугольников). Но они расположены в океанах, так что в большинстве практических задач можно о них не думать.
Более подробно на h3geo.org
Картографический движок
В Qt начиная с версии 5.12 появился модуль для отображения карты, но есть нюансы:
Нет нормальной поддержки MBTiles и PMTiles (который значительно экономит дисковое пространство и быстрее загружается благодаря оптимизированной архитектуре хранения)
При рендеринге большого числа объектов возникают тормоза
Нет поддержки Vulkan, только OpenGL (Metal появился только с версии 6.9 для macOS)
Поэтому был выбран движок от MapLibre, которым я пользовался на работе. Это форк Mapbox, который прекратил обновления своего C++ движка в open-source.
В данном проекте использовал qt 6.10.1
MapLibre Native Qt решает все вышеперечисленные проблемы:
Поддержка MBTiles и PMTiles
Эффективный рендеринг большого количества объектов
Векторные и растровые карты
Полная совместимость с Qt Location API (
geoCircle,geoCoordinate,geoPath,geoPolygon,geoRectangleи т.д.)
Выбор алгоритма построения лабиринта
Для генерации лабиринта я выбрал алгоритм Прима https://ru.wikipedia.org/wiki/Алгоритм_Прима
Почему алгоритм Прима?
Классический алгоритм Прима находит минимальное остовное дерево графа, жадно выбирая рёбра с наименьшим весом. Для генерации лабиринтов мы его «ломаем»: вместо минимального веса берём случайное ребро из фронтира.
Такой подход даёт лабиринту с характерный «колючий» вид — много коротких тупиков, разветвлённая структура. В отличие от DFS-лабиринтов с их длинными коридорами, здесь навигация становится нетривиальной.
Адаптация под гексагоны.
В квадратной сетке соседей находим простым (x±1, y±1). В H3 всё немного сложнее.
Для начала я выбрал минимальный уровень разрешения 2(при таком разрешении всего 5,882 ячеек на всю карту и каждый гексагон занимает аж 86,801 км²), в процессе оказалось что поиск маршрута происходит слишком легко и быстро, также при построении лабиринта сложно было создать сложный лабиринт с ветвлениями и тупиками. На текущий момент я использую 3 разрешение 41,162 пентагонов, каждый занимает площадь 12,393 км².
Чтобы получить соседей делаем примерно так:
std::array<H3Index, H3AStar::MAX_NEIGHBORS> H3AStar::getNeighbors(const H3Index cell) {
std::array<H3Index, 7> ring = {};
if (const H3Error err = gridDisk(cell, 1, ring.data()); err != E_SUCCESS) {
return {};
}
int64_t maxSize = 0;
if (maxGridDiskSize(1, &maxSize) != E_SUCCESS) {
return {};
}
std::array<H3Index, MAX_NEIGHBORS> neighbors_ = {};
int count = 0;
for (auto i = 0; i < maxSize; i++) {
if (ring[i] != 0 && ring[i] != cell) {
neighbors_[count++] = ring[i];
}
}
return neighbors_;
}
, где MAX_NEIGHBORS равен 6.
Двунаправленный A*: ищем с двух сторон
Начинал я с алгоритма Дейкстры как и предполагалось, он довольно медленный для такой задачи, п.c. я оставил его в проекте для бенчмарка.
Стандартный A* — это, конечно, классика. Но когда лабиринт большой, а путь извилистый, можно ускориться, запустив поиск с обоих концов.
Идея алгоритма
Запускаем два A* — один из старта, другой из финиша. Когда фронтиры встречаются, мы (возможно) нашли путь. Но нельзя сразу останавливаться — первая встреча не гарантирует оптимальность!
Критерий остановки: если сумма минимальных f-значений в обоих открытых списках больше или равна лучшему найденному пути, поиск можно завершить.
Эвристика для гексагонов
H3 предоставляет функцию gridDistance, которая возвращает количество шагов между двумя ячейками:
int64_t hexDistance(const H3Index a, const H3Index b) {
int64_t distance;
gridDistance(a, b, &distance);
return distance;
}
Это идеальная допустимая эвристика: она никогда не переоценивает реальное расстояние.
Multi-Waypoint Routing: когда одного финиша мало
Реальные маршруты редко бывают из точки A в точку B. Чаще нужно заехать в несколько мест. Это подводит нас к задаче коммивояжёра (TSP), которую для небольшого числа точек решаем эвристически.
Алгоритм:
Предвычисление путей: вычисляем оптимальные пути между всеми парами waypoints
Построение графа: строим полный граф с этими расстояниями
Оптимизация порядка: находим хороший порядок обхода методом ближайшего соседа + 2-opt
Финальный маршрут: склеиваем предвычисленные пути
Производительность: цифры и бенчмарки
Одна из важных частей проекта — понять, насколько быстро работают разные алгоритмы поиска пути. Для этого я написал бенчмарки, сравнивающие три подхода:
Алгоритм | Время поиска | Узлов обработано | Ускорение |
|---|---|---|---|
Дейкстра | ~450 мс | ~8,500 | 1x (baseline) |
A* | ~180 мс | ~3,200 | 2.5x |
Bidirectional A* | ~29 мс | ~1,800 | 6.1x |
Данные для ла��иринта на разрешении 3 (41,162 ячейки), расстояние ~300 шагов
Использовался процессор M5 pro.
Как видите, двунаправленный A* почти в ~6 раз быстрее наивного подхода Дейкстры. Это особенно критично для интерактивных приложений, где пользователь кликает по карте и ожидает мгновенного отклика.
Почему такая разница?
Дейкстра исследует узлы во всех направлениях равномерно
A* фокусируется на направлении к цели благодаря эвристике
Bidirectional A* сокращает пространство поиска вдвое, встречаясь посередине
Поиск маршрута до конечной точки не заканчивается на 3 разрешении
Реализованный алгоритм Bidirectional A* позволяет искать путь от 3 до 15 разрешения. Например: одна из точек маршрута находится на уровне 14, сначала находим соту, которую находится над этой точкой на уровне 3, далее опускаемся от 3 до 14 с шагом 1. Также если начальная точка находится не на 3 разрешении делает также, поднимается до 3 ищет путь на 3 уровне до заданной цели.
Небольшое видео-демонстрация приложения
Код полностью открыт и доступен на https://github.com/wecand0/qHexWalker, это начальная версия приложения, буду рад комментариям, вопросам, предложения :)
