Игрок замкнул петлю. Как моей GPS-стратегии понять, что именно он захватил?
В GeoConquest основное правило звучит довольно просто: игрок выходит со своей территории, оставляет за собой след, возвращается обратно и захватывает оказавшуюся внутри область.
Но для сервера никакого «внутри» не существует.
Он видит только набор гексов: вот территория игрока, вот его след, вот точка выхода и точка возвращения. След может пересекаться сам с собой, разветвляться, соединять два отдельных владения или проходить внутри уже окружённой области.
И каждый раз игре нужно решить, что именно теперь должно стать территорией игрока.
Первая версия: коснулся своего следа — замкнул петлю
Изначально захват завершался двумя способами:
игрок возвращался на принадлежащую ему территорию;
игрок наступал на более раннюю часть собственного следа.
Второй вариант казался естественным. Если маршрут пересёк сам себя, значит появилась замкнутая фигура. Можно закрасить её внутренность, а оставшийся след удалить.
Но довольно быстро выяснилось, что собственный след превращается для игрока в препятствие.
Его нельзя было свободно пересекать. Нельзя было вернуться немного назад, провести параллельный маршрут или сделать несколько ветвей. Любое случайное касание могло быть воспринято как завершение захвата.
Особенно плохо это сочеталось с настоящим GPS, который даже у неподвижного телефона продолжает немного гулять. Это называют дрейфом GPS: человек стоит на месте, а координаты прыгают между соседними точками.
Как Bedrock потерял огромный маршрут
Однажды участники клана Bedrock шли по большой петле. Они уже прошли приличное расстояние, а затем остановились передохнуть примерно на стыке трёх гексов.
Маркеры игроков двигались не совсем синхронно, координаты немного отличались, а дрейф GPS несколько раз подёргал их между соседними клетками.
В результате след случайно замкнулся сам на себя.
Игра решила, что захват завершён, закрасила три гекса возле места остановки и удалила весь остальной маршрут.
В те времена следы одного владельца ещё не разделялись на независимые части. Поэтому маленькая случайно замкнувшаяся петля уничтожила всё, что клан успел пройти до неё.
Сама ошибка была связана с GPS, но она показала, что проблема находилась глубже: правило замыкания о собственный след не подходило для игры, в которой люди действительно ходят по улицам.
След перестал быть стеной для владельца
Я полностью изменил условие завершения захвата.
Теперь петля закрывается только тогда, когда игрок:
выходит со своей территории;
проходит хотя бы один чужой или нейтральный гекс;
возвращается на принадлежащую ему территорию.
Повторное касание собственного следа больше ничего не завершает.
По следу можно пройти ещё раз. Его можно пересекать, вести параллельно, разветвлять и соединять с другими участками. Даже короткий выход на один гекс с немедленным возвращением считается нормальным захватом этого гекса.
Это исправило случайные самозамыкания, но породило гораздо более сложный вопрос.
Раньше след сам образовывал готовый контур. Теперь он мог выглядеть как угодно. Значит, серверу требовалось понять, какие области отрезали друг от друга след вместе с уже существующей территорией.
Внешний захват
Самый понятный случай: игрок выходит с внешней границы своих владений, делает дугу по нейтральной или чужой земле и возвращается обратно.
След и старая территория становятся стенками нового кармана. Область внутри оказывается отрезана от остального мира и захватывается.
На схемах используются квадратные клетки, чтобы не усложнять рисунок. В самой игре все вычисления происходят на H3-гексах.
Внешний мир считается бесконечным. Сервер смотрит, какие области после добавления следа больше не имеют выхода наружу. Именно они становятся кандидатами на захват.
Если маршрут образовал несколько связанных карманов, игра может захватить их вместе.
А если никакого кармана не появилось?
Игрок может выйти из одной своей территории и прийти в другую, которая пока с ней не соединена.
В таком случае маршрут не обязательно что-то окружает. Он просто становится тонкой полосой новой территории, соединяющей два владения.
Но эта перемычка уже участвует в следующих захватах. Если потом провести между теми же владениями ещё один маршрут, старая полоска и новый след могут окружить полноценную область.
Более того, сам маршрут может разветвляться и создавать дополнительные карманы.
То есть результат зависит не только от текущей прогулки. На него может повлиять территория, захваченная несколько дней назад и находящаяся довольно далеко от точки возвращения.
Внутренний захват работает иначе
Представим, что внутри территории игрока осталась большая нейтральная или вражеская полость. Со всех сторон она уже окружена его землёй.
Игрок выходит с внутренней границы, проводит через полость след и возвращается к своей территории с другой стороны.
Маршрут разделяет полость на две части. Но обе выглядят замкнутыми: выхода во внешний мир не было ещё до начала прогулки.
Если применить к такой ситуации правила внешнего захвата, результат получится неоднозначным. Поэтому для внутренних петель действует отдельное правило:
захватывается самый маленький образовавшийся карман.
На схеме серая рамка — уже принадлежащая игроку территория. Внутри неё находится незахваченная полость. Красный маршрут разрезает её на большую и маленькую части, поэтому зелёной становится маленькая.
Из этого возникает отдельная стратегия: большую внутреннюю полость выгодно постепенно распиливать тонкими маршрутами, каждый раз отрезая от неё меньшую часть.
Получается, внешние и внутренние захваты отвечают на разные вопросы:
внешний: какие области новый маршрут отрезал от бесконечного внешнего мира;
внутренний: какую наименьшую часть уже замкнутой полости отделил маршрут.
Потом появились общие клановые следы
С кланами всё снова усложнилось.
След получил не личного владельца, а общего: clan:<id>. Несколько участников могут продолжать один клановый маршрут и вместе замыкать петли.
Но соклановцы могут находиться не только на соседних улицах, но и в разных городах или странах.
Если считать весь след клана одной сущностью, захват в одном городе уничтожит незавершённый маршрут участника в другом. То же самое произойдёт, если противник наступит на маленький участок общего следа.
Поэтому следы пришлось разделить на связанные компоненты.
Теперь завершение захвата превращает в территорию только участвовавшую в нём связанную часть. Независимые маршруты клана в других местах остаются на карте. При атаке тоже уничтожается только та часть следа, в которую наступил противник.
Когда правильный алгоритм начал подвешивать сервер
Некоторое время захваты вычислялись при помощи flood fill: сервер строил вокруг связанной территории большую область из гексов и обходил её, определяя внутренние и внешние карманы.
На обычных владениях это работало нормально.
А затем у клана «Нелетающие» появилась очень длинная и тонкая территория. Некоторые захваты возле неё начали подвешивать сервер более чем на 20 секунд.
Я попробовал ограничить расчёт ближайшими 128 гексами от активного маршрута. Серверу стало легче, но механика сломалась.
Далёкая часть одной связанной территории может быть стенкой глубокой бухты, пещеры или огромного внутреннего кармана. Если просто обрезать её по радиусу, закрытая область внезапно превращается в открытую, а внутренний захват — во внешний.
Оптимизацию пришлось откатить.
В итоге я заменил большой пространственный flood fill вычислениями по топологии H3. Сервер по-прежнему учитывает всю связанную территорию, какой бы длинной она ни была, но работает с её контурами и превращает в отдельные гексы только итоговую захватываемую область.
Что происходит сейчас
Когда игрок возвращается на свою землю, сервер:
находит связанную часть следа, которая пришла к точке возвращения;
добавляет другие ветви, связанные с той же территорией;
определяет, является захват внешним или внутренним;
для внешнего захвата ищет отрезанные от мира карманы;
для внутреннего выбирает самый маленький карман;
если никакого кармана нет, превращает в территорию только сам след;
отдельно разыгрывает захват владений каждого противника внутри области.
Так короткое правило «замкнул петлю — получил землю» превратилось в одну из самых сложных частей игры.
А какой результат вы ожидали бы от внутреннего захвата: меньший карман, направление движения игрока или возможность самому выбрать сторону?
Играть можно прямо в браузере: https://geo.juju.ru
Кстати, вчера переехал на новый сервер, игра снова работает без впнов!
Прямо сейчас работаю над приложением в Google Play, надеюсь скоро выйдет!)
Патчноуты и история разработки: https://t.me/GeoConquest
