Around. Как я пытался покрыть весь мир квадратами – и почему в итоге появились шестиугольники
Around – это игра про передвижение в реальном мире.
В начале всё выглядело максимально просто: есть карта мира, есть игроки, значит нужно лишь разбить Землю на одинаковые клетки, чтобы их можно было захватывать просто идя по улице.
Ну что может быть проще квадратной сетки?
Я написал Python-скрипт, который несколько часов генерировал огромный GeoJSON со всеми клетками мира. Когда генерация наконец закончилась, я открыл результат и был уверен, что первый большой этап позади.
Проблема с проекцией карты
Стоило посмотреть на глобус внимательнее, как стало ясно: квадраты больше не были квадратами.
Это не ошибка программы. Так устроена сама геометрия Земли.
Поверхность нашей планеты – сфера, а квадраты строились по линиям широты и долготы. По мере приближения к полюсам меридианы начинают сходиться, поэтому клетки постепенно сжимаются и превращаются в прямоугольники/трапеции.
Также большинство картографических сервисов используют проекцию Меркатора – способ развернуть поверхность шара на плоскость. Чтобы сохранить правильные углы, области возле полюсов приходится искусственно растягивать.
Получался забавный эффект: на глобусе квадраты сжимались, а на карте наоборот вытягивались и выглядели уже как прямоугольники.
«Ладно, – подумал я. – Значит клетки просто слишком большие».
Казалось, решение очевидное: уменьшить их.
Я сделал сетку 500×500 – около 250 тысяч клеток.
Краш. Приложение просто не смогло открыть файл: памяти не хватало.
Тогда я перенёс данные на сервер и стал подгружать их по мере необходимости. И всё вроде заработало.
В тот момент я снова подумал, что победил. Но чем меньше становились клетки, тем быстрее росли объёмы данных.
Для сетки 4000×4000 компьютеру уже требовалось около 18 ГБ оперативной памяти только на генерацию. Сам GeoJSON занимал примерно 20 ГБ.
А потом начали появляться совершенно странные вещи.
На карте возникали пустые полосы. Некоторые полигоны просто исчезали. Оказалось, я упёрся уже не в память, а в ограничения картографического движка и сервера.
Тогда я впервые задал себе вопрос, который стоило задать ещё в самом начале.
А сколько вообще клеток понадобится для всей Земли?
Я сел считать.
Сначала получилось около 16 миллионов квадратов.
Звучит внушительно.
Но один квадрат всё ещё занимал сразу несколько районов города.
Если же уменьшить клетки примерно до одного квадратного метра, получалось около 510 триллионов квадратов.
Именно в этот момент стало понятно, что проблема вообще не в оптимизации.
Я пытался решить задачу неправильным способом.
Нельзя заранее хранить карту всей планеты.
Нужен был совершенно другой подход.
И тут я наткнулся на решение
Именно тогда я нашёл библиотеку H3 от Uber.
Она использует не квадраты, а шестиугольники и хранит не сами клетки, а математическую модель, позволяющую получать любую ячейку по её координатам.
После этого вся архитектура Around фактически изменилась.
Теперь не нужно хранить гигантский файл с картой всей Земли.
Не нужно загружать миллионы полигонов.
И не нужно рисовать то, чего игрок сейчас даже не видит.
При сильном отдалении используются крупные шестиугольники.
По мере приближения они автоматически делятся на более мелкие.
Из-за этого игра спокойно работает как на масштабе всей планеты, так и на уровне нескольких метров вокруг игрока.
Казалось бы, наконец всё получилось.
Но проблемы на этом не закончились
Когда две территории разных команд соприкасались, их границы начинали мерцать.
Линии буквально боролись друг с другом за право оказаться сверху.
Иногда это выглядело так, будто карта дрожит.
Решение оказалось простым. Я добавил между клетками небольшой визуальный зазор.
После этого мерцание исчезло полностью.
А позже я сделал ещё один важный шаг.
Вместо того чтобы рисовать тысячи отдельных шестиугольников, я начал объединять соседние клетки одного цвета в большие области.
Что получилось в итоге
Карта стала гораздо чище, понятнее и производительнее. Но тут опять конфликтуют границы теперь уже областей, однако это всё равно выглядит лучше, да и цвет хорошо видно – решил оставить так.
Если интересно узнать больше
Это далеко не единственная инженерная задача, с которой я столкнулся за четыре года разработки Around. Если интересно, могу рассказать и про другие неожиданные решения – например, почему я использую не Яндекс Карты.
А если захотите попробовать Around сами – игра уже доступна в RuStore (открывать без VPN, с ним RuStore не находит). Будем рады любому фидбеку и предложениям по развитию проекта.
Тг канал: t.me/around_game
Сайт: https://aroundgame.ru/