Про Ingress и дроны

Начну с самого начала. Ingress — это такая геолокационная игра. Не люблю это сравнение, но это как Pokémon Go, но от тех же разработчиков и вышедшая на 4 года раньше. В ней на карте расставлены точки, с которыми можно взаимодействовать (они называются порталами). Физически (ногами) ходя между порталами, можно связывать их друг с другом (создавать линки) и закрывать треугольники (поля). Две фракции (Просвещение и Сопротивление) борются друг с другом за контроль над порталами и территорией.

Одна из дополнительных механик в игре — дроны, которые начинают свой полёт от местоположения игрока и раз в час могут прыгать от одного портала к другому в радиусе примерно 500 метров.

Они не требуют от игрока выходить из дома, но при этом тесно связаны с портальной сетью. С учётом того, что их ввели летом 2020 года, в этом и была задумка

Иногда бывает полезно отправить дрон в какое-нибудь определенное место или просто улететь куда подальше. И тут возникает вопрос: как это сделать наиболее быстро? А с учетом того, что дрон прыгает только раз в час, этот вопрос превращается в "как это сделать за минимальное число прыжков?"

И тут на помощь приходит IITC. У игры есть официальный сайт под названием Ingress Intel, на котором можно посмотреть карту игровых действий в любой точке мира.

IITC (расшифровывается Ingress Intel Total Conversion) же — это неофициальный проект, поддерживаемый сообществом, который представляет собой такую же карту, но переписанную на библиотеке Leaflet. В отличие от стокового интела, IITC легко расширяется с помощью кастомных плагинов. Они есть буквально для всего, в том числе и для построения путей для дронов.

Этот плагин написал игрок из США под ником tehstone. С его помощью можно посмотреть, какие порталы доступны для прыжка с выбранного. Можно заметить, что кроме круга радиусом в 500 метров также учитываются зеленые ячейки (S2-ячейки уровня 16). Интересный факт: нет точной информации, как именно выбираются доступные для прыжка порталы. Есть лишь догадки и наблюдения сообщества.

Но мне пришла идея: а что если это... слегка автоматизировать? Я сел и написал автоматический путеискатель с использованием алгоритма Дейкстры. [наконец-то мне пригодились знания по олимпиадной информатике]

Нужно лишь указать начальный и конечный порталы, и алгоритм найдёт все маршруты, позволяющие достичь цели за минимальное количество прыжков.

Практическая полезность такого путеискателя весьма ограниченна, но иногда он находит неочевидные маршруты, на которые сложно наткнуться вручную.

Но я весело провёл полдня, заставляя это всё работать как надо, и уже поэтому не жалею о потраченном времени.

Сначала я хотел выгружать данные из браузера и скармливать их программе на C++, но в итоге передумал и стал реализовывать это всё полностью на JavaScript'е. Да, язык для этого не предназначен (например, очень не хватало структуры Set, позволяющей быстро находить минимальный элемент в ней), но оно таки заработало и даже с приемлемой скоростью (зависит от количества порталов, но подсчёт занимает примерно пару секунд).

Спасибо, что прочитали! Код плагина вот тут: https://github.com/Loskir/IngressDronePath/blob/master/dronePathTravelPlanner.user.js#L1037