Генерация лабиринта с использованием Uber H3 на карте в Qt

[Tantrido]

Прекрасно! Как подобного инструментария не хватало нам на 5.12-5.15: MapLibre появился только через год или был в зачаточном сотоянии - сейчас мощнейшая штука! Плюс ничего не знали про Bidirectional A* - сейчас бы наш алгоритм летал бы, всё было бы сильно проще и красивее. Спасибо!

[hauptling]

Самое удобное что интеграция карт в приложение проста, на работе разрабатывал приложение с довольно большим числом объектов динамически перемещающиеся на карте(вся математика как и тут в c++, графика qml), был стабильный fps 60 и нагрузка на CPU меньше 0.4% на 4 летнем i7.

[alliumnsk]

Разрешите придраться - гномоническая проекция искажает площади и форму сильнее меркаторской, просто на достаточно маленьких треугольниках это не важно, зато вычисление координат намного быстрее происходит

[hauptling]

Да, спасибо, Вы правы!

[Jijiki]

тоесть получается тут не наивная реализация, а как тогда у вас будут обстоять дела если нужно будет картографически масштабироваться например 1 к 1000 000 (ну хотябы отрисовать в 512 512 чтобы были улицы), это сколько по памяти-то, тоесть тут что-то воксельное или ааббшное мне видится, чтобы граф переваривать на нужном уровне масштаба, или у вас масштабы реализованы до улиц?

классная тематика вообще, успехов

[hauptling]

Архитектура разделена на два слоя:

Рендеринг (MapLibre Native):

• Векторные тайлы с встроенным LOD и frustum culling

• Масштаб 1:1000000 — стандартный кейс для тайловых движков, грузятся только видимые тайлы z-уровня

• Улицы приходят из vector tiles (OSM/MapTiler), не из H3

Геоиндексация (H3):

• Иерархическая сетка, 16 резолюций (0-15), апертура 7

• Индекс = uint64 (8 байт), ячейки не хранятся — вычисляются через latLngToCell()

• Переход между масштабами: cellToParent() / cellToChildren() за O(1)

• Viewport 512×512 при res 9 ≈ 2000-5000 ячеек = ~40 КБ на индексы

Граф для A*:

• Строится лениво для видимой области + буфер

• gridDisk() для соседей — O(k) где k = количество соседей (6-7)

• При zoom меняется resolution → граф пересчитывается для нового LOD

Воксели/AABB не нужны — H3 уже даёт иерархию с гарантированной вложенностью parent→children. Это по сути discrete global grid system (DGGS).