Новый алгоритм поиска пути в Factorio

Автор оригинала: Oxyd
  • Перевод

На прошлой неделе мы говорили в своём блоге об изменениях, которые позволят врагам (biters) не наталкиваться друг на друга, но это было не единственное обновление, связанное с biter-ами. Совпало так, что в обновления этой недели вошло то, над чем мы работали предыдущие несколько недель — обновление системы поиска пути для врагов.

Поиск пути


Когда юнит хочет куда-то переместиться, ему сначала нужно понять, как туда добраться. В самом простом случае можно двигаться прямиком к цели, но на пути иногда возникают препятствия — скалы, деревья, гнёзда врагов (spawners), юниты игрока. Чтобы проложить дорогу, мы должны сообщить функции поиска пути (pathfinder) текущую и конечную позиции, а pathfinder вернёт нам (возможно, через много тактов) путь, который просто является набором промежуточных точек (waypoints), по которым должен двигаться юнит, чтобы добраться до места назначения.

Для выполнения своей работы pathfinder использует алгоритм под названием A* (произносится «A star»). Простой пример поиска пути при помощи A* показан на видео: biter хочет найти путь в обход скал. Функция поиска пути начинает исследовать карту вокруг biter-а (исследование показано белыми точками). Сначала она пытается пойти напрямик к цели, но как только достигает скал, «разливается» в обе стороны, пытаясь найти позицию из которой снова можно будет двигаться к цели.


Алгоритм в этом видео замедлен, чтобы было лучше видно, как он работает.

Каждая точка в анимации обозначает узел. Каждый узел запоминает расстояние от начала поиска и оценку расстояния от этого узла до цели (эта оценка вычисляется эвристической функцией). Именно благодаря эвристической функции работает A* — она направляет алгоритм в верную сторону.

В простейшем случае эта функция является просто вычислением расстояния по прямой от узла до позиции цели — именно такой подход мы использовали в Factorio с самого начала разработки, и благодаря ему алгоритм изначально движется по прямой. Однако это не единственный вариант — ели эвристическая функция знала бы о некоторых из препятствий, то могла бы направлять алгоритм в обход, что ускорило бы поиск, потому что не пришлось бы исследовать лишние узлы. Очевидно, что чем умнее эвристика, тем сложнее её реализовать.

Простая эвристическая функция оценки расстояния по прямой хороша для поиска путей на относительно коротких расстояниях. Она устраивала нас в предыдущих версиях Factorio — почти всегда biter-ы перемещались на дальние расстояния только из-за того, что их приводило в гнев загрязнение, а такое случалось не очень часто. Однако теперь у нас есть артиллерия. Артиллерия может запросто стрелять по огромным количествам biter-ов с другой стороны большого озера (и «агрить» их), после чего они пытаются проложить путь в обход озера. На видео ниже показано, как простой алгоритм A*, который мы использовали ранее, пытается обойти озеро.


В этом видео показана скорость работы алгоритма в реальности; он не замедлен.

Сокращение блоков


Поиск пути — это задача, имеющая долгую историю, и существует множество техник его улучшения. Часть этих техник относится к категории иерархического поиска пути: в этом случае карта сначала упрощается, на этой упрощённой карте находится путь, который затем используется для поиска настоящего пути. Повторюсь, конкретных реализаций такой методики существует несколько, но все они требуют упрощения пространства поиска.

Как же можно упростить мир Factorio? Наши карты генерируются случайным образом и постоянно изменяются: размещение и удаление сущностей (например, сборщиков, стен или турелей) — это, наверно, самая базовая механика всей игры. Мы не хотим пересчитывать всю упрощённую карту при каждом добавлении или удалении сущности. В то же время, если упрощать карту заново каждый раз, когда нам нужно найти путь, то можно запросто потерять весь полученный выигрыш в производительности.

Одному из людей с доступом к исходному коду игры (Allaizn) пришла в голову идея. которую я в результате реализовал. Теперь эта идея кажется очевидной.

Игра основана на блоках размером 32x32 тайлов. Процесс упрощения заменяет каждый блок одним или несколькими абстрактными узлами. Так как наша цель заключается в улучшении поиска пути вокруг озёр, мы можем игнорировать все сущности и рассматривать только тайлы: по воде двигаться нельзя, по суше — можно. Мы разделяем каждый блок на отдельные компоненты. Компонент — это область тайлов, в которой юнит может добраться с одного тайла внутри компонента до любого другого тайла того же компонента. На изображении ниже блок разделён на два отдельных компонента, красный и зелёный. Каждый из этих компонентов станет одним абстрактным узлом — по сути, весь блок сокращается до двух «точек».


Самая важная мысль Allaizn заключалась в том, что нам не нужно хранить компонент для каждого тайла карты — достаточно запомнить компоненты тайлов по периметру каждого блока, потому что нас интересует только то, с чем соединены другие компоненты (в соседних блоках) каждого компонента, а это зависит только от тайлов, которые находятся на самой границе блока.

Иерархический поиск пути


Итак, мы выяснили, как упростить карту, но как же использовать это для поиска путей? Как я и говорил, существует множество техник иерархического поиска пути. Простейшая идея заключается в нахождении пути при помощи абстрактных узлов от начала до цели, то есть путь будет являться списком компонентов блоков, которые нужно посетить. После чего мы используем серию старых добрых поисков A*, чтобы конкретно выяснить, как двигаться от одного компонента блока к другому.

Проблема здесь заключается в том, что мы слишком уж упростили карту: что, если переместиться из одного блока в другой невозможно, потому что какие-то сущности (например, скалы) блокируют путь? При сокращении блоков мы игнорируем все сущности, поэтому знаем только, что тайлы между блоками каким-то образом связаны, но совершенно ничего не знаем о том, можно ли передвигаться от одного к другому.

Решение заключается в том, чтобы использовать упрощение просто как «рекомендацию» для реального поиска. В частности, мы будем применять его для создания умной версии эвристической функции поиска.

В результате мы получили следующую схему: у нас есть два pathfinder: базовый pathfinder, который находит настоящий путь, и абстрактный pathfinder, предоставляющий базовому pathfinder эвристическую функцию. Каждый раз, когда базовый pathfinder создаёт новый базовый узел, он вызывает абстрактный pathfinder для получения оценки расстояния до цели. Абстрактный pathfinder действует в обратном порядке — он начинает с цели поиска и прокладывает дорогу к началу, переходя от одного компонента блока к другому. Когда абстрактный поиск находит блок и компонент, в котором создаётся новый базовый узел, он использует расстояние от начала абстрактного поиска (которое, как я говорил, является позицией цели всего поиска) для вычисления оценки расстояния от нового базового узла до общей цели.

Однако выполнение всего pathfinder для каждого отдельного узла будет далеко не быстрым, даже если абстрактный pathfinder переходит от одного блока к другому. Поэтому вместо этого мы используем схему под названием «обратный возобновляемый A*» (Reverse Resumable A*). «Обратный» означает, что он, как я говорил выше, выполняется от цели к началу. «Возобновляемый» означает, что после нахождения блока, который интересен базовому pathfinder, мы сохраняем все его узлы в памяти. Когда в следующий раз базовый pathfinder создаёт новый узел и ему требуется оценка расстояния, мы просто смотрим на абстрактные узлы, сохранённые из предыдущего поиска. При этом есть большая вероятность того, что требуемый абстрактный узел всё ещё будет в памяти (в конце концов, один абстрактный узел покрывает большую часть блока, а часто и весь блок).

Даже если базовый pathfinder создаёт узел, находящийся в блоке, не покрытом ни одним из абстрактных узлов, нам не нужно заново выполнять весь абстрактный поиск целиком. Удобное свойство алгоритма A* заключается в том, что даже после того, как он «завершает работу» и находит путь, он продолжает выполнение, исследуя узлы вокруг уже исследованных узлов. И именно это мы делаем, если нам нужна оценка расстояния для базового узла, расположенного в блоке, ещё не покрытом абстрактным поиском: мы возобновляем абстрактный поиск с узлов, хранящихся в памяти, пока он не расширится до узла, который нам нужен.

На видео ниже показана новая система поиска пути в действии. Синие круги — это абстрактные узлы; белые точки — базовый поиск. Pathfinder в видео сильно замедлен по сравнению с игровым, чтобы показать, как он работает. При обычной скорости весь поиск занимает всего несколько тактов. Заметьте, что базовый поиск, который по-прежнему использует старый алгоритм, который мы применяли всегда, просто волшебным образом «знает», как двигаться в обход озера.


Так как абстрактный pathfinder используется только для получения эвристической оценки расстояния, базовый поиск довольно легко может отступать от предложенного абстрактным поиском пути. Это значит, что даже несмотря на то, что схема сокращения блоков игнорирует все сущности, базовый pathfinder почти без проблем может обходить их. Благодаря игнорированию сущностей в процессе упрощения карты нам не нужно повторять его заново при каждом добавлении или удалении сущности, достаточно покрывать только те тайлы, которые были изменены (например, как в случае с мусорным полигоном), что происходит намного реже, чем размещение сущностей.

Кроме того, это означает, что мы по сути используем тот же pathfinder, которым пользовались годами, обновилась только эвристическая функция. То есть это изменение не затронет множество других систем, и повлияет только на скорость поиска.
Поддержать автора
Поделиться публикацией

Похожие публикации

AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 28

    +2
    Было бы интересно посмотреть как алгоритм будет находить путь из случайного лабиринта.
      +2
      Полагаю, никак. Потому как этому алгоритму требуется хорошая связность пространства поиска.
        0
        Точно так же. Принцип ведь простой, разбить карту на узлы, вычислить проходимость между соседними узлами, построить оптимальный маршрут. А тут это в два этапа делается, сначала маршрут по крупным «клеткам», потом внутри каждой клетки маршрут «по пикселям».
        –13
        Я не знаком с игрой, но фраза
        Мы не хотим пересчитывать всю упрощённую карту при каждом добавлении или удалении сущности. В то же время, если упрощать карту заново каждый раз, когда нам нужно найти путь, то можно запросто потерять весь полученный выигрыш в производительности.

        я трактую примерно как «Я не хочу программировать, хочу чтобы само».
        А кто мешает построить упрощённую карту после редактирования? А зачем её пересчитывать каждый раз перед алгоритмом?
        Предложенное решение по факту и является упрощением карты, только с какими-то своими ограничениями что, скорее всего, в конечном счёте выйдет боком.
          +3

          Читайте эту фразу как "мы не хотим пересчитывать всю упрощенную карту десяток раз в секунду".


          К подлагиваниям после выстрелов артиллерии игроки уже как-то привыкли, а вот лаги в процессе строительства каких-нибудь стен или разворачивания базы из чертежа с помощью дронов могут здорово испортить игру.

            +2
            А кто мешает построить упрощённую карту после редактирования?

            карта постоянно меняется, можно стену построить например
              0

              Не целиком же она меняется, а только тайл, где стена.

                0

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

                  0

                  А MipMapping ещё не изобрели? Кажется я забрался слишком далеко в прошлое..

                    0

                    А причём тут MipMapping-то?

                      0

                      При том, что объём пересчётов на каждом уровне незначителен, а пересчитать надо по одному не большому тайлу в каждом.

                0
                Если построить стену, то по моему опыту это не изменит глобальный путь кусак, они будут грызть стену, но не оббегать по карте её.

                По большому счёту карта меняется редко, только засыпание водоёмов кардинально меняет карту, а любые постройки не меняют путь кусак. По крайней мере я ни разу не видел чтобы кусаки как-то хитро себя вели, бегут по кратчайшему пути от своей базы к максимально загрязнённым блокам не учитывая при выборе пути стены или другие постройки. Как только встречают что-то не природное, начинают грызть. Игрок для них более приоритетная цель и они бросают грызть и бегут к нему и, если он за стеной, а рядом можно оббежать, только тогда они могут оббежать стену.
                  0
                  Камни и деревья грызут точно также как и стенки, то что «мешает пройти»
                +3

                Может вы не так поняли "не хотим пересчитывать всю упрощённую карту" ?


                Они-то может в душе и хотят пересчитывать, но из-за этого пересчета у них смысл оптимизации потеряется.

                +2
                Это переведенные Friday facts? Или пишет один из разработчиков?
                  +1

                  Первое, о чём "намекает" плашка "Перевод" и ссылка на оригинал под заголовком.

                    0
                    Может не заметил, а может в мобильном приложении не видно было. Скорее первое.
                  –1
                  А зачем считать весь путь непосредственно в момент «агры»?

                  Там же путь от одного стационарного объекта до другого стационарного объекта.

                  Фактически у нас есть группа гнезд кусак/плевак, которые можно объединить в большую сущность «база кусак» (БК). Можно взять сущность «база игрока» (БИ) — некоторая окрестность радом с чанками занятыми источниками загрязнения (например 2 чанка).

                  Соответственно можно заранее в фоне построить маршрут от вейпоинта рядом с КБ кусак до некого вейпоинта окрестности БИ.

                  Тогда придется только иногда (при постройке игроком чего-то там) уточнять позицию последней точки маршрута БК-БИ, а при поиске пути искать путьдо вейпоинта БК, добавлять к нему путь БК-БИ и потом достраивать путь от БИ до собственно того, что надо «покусать».

                  Опять же для артеллерийских вагонов — можно заранее почитать путь к нескольким окрестностям каждой ЖД сети (далее можно просто воспользоваться поиском пути от поездов)
                    0

                    Так ведь проблема-то не в источниках загрязнения, а в артиллерии. А она бывает и мобильной (арт. вагоны).

                      0
                      Вагоны ездят по рельсам. Рельсы стационарный объект. Можно заранее посчитать пути до нескольких точек на рельсах (например через каждые 5 чанков для каждой ЖД системы) а от этих точек тупо «вдоль рельс» идти (Используя алгоритм поиска пути от поездов)
                        0

                        Во-первых, подобный способ перемещения кусак будет заметен невооруженным глазом. Во-вторых, рельсы могут быть построены игроком очень быстро, что при вашем алгоритме вызовет лаги. В-третьих, используя мод FARL можно вовсе отвязаться от рельс и получить полностью автономную мобильную арту, пусть и сложную в управлении.

                          +2
                          А если баз несколько? Я вот по фану делаю несколько разнесенных фабрик специализирующихся на своем типе производства(химия, электроника, плавильня, военка и т д) и соединенных крупной ЖД сетью для обмена ресурсами. В таком случае куда бежать? Или каждому рою отдельно высчитывать маршруты к каждой из фабрик? Да и с ЖД, вы, я так понял, предлагаете рассчитывать путь к каждому из сегментов ЖД, чтобы кусаки понимали куда бежать?

                          А если, например, игрок отойдет от базы и поставит пушку «в чистом поле». Бежать кусакам к базе или к Ж\Д? Или растеряться и начать искать путь к внезапно появившемуся и шмальнувшему орудию? Так это ничем и не отличается от того что уже есть. А предложенная вами «оптимизация», выходит, неработоспособна, т.к. предполагает заранее общитывать гораздо больше маршрутов, чем требуется, и при этом совсем не учитывает ряд вполне возможных кейсов.
                        0
                        Думаю кусаки собираются в строй именно для того чтобы не считать путь для каждого, а посчитать для отряда. И эта атака планируется заранее и в принципе в фоне и считается путь.
                        А вот агра от арты происходит внезапно, и реакция у кусак другая, они уже не собираются в отряд, а каждый из выживших сам по себе бежит на звук выстрела и путь честно считается для каждого, вот этот массовый рассчёт и вызывает снижение ups.
                        Теперь же как раз, примерно как вы и предлагаете, в фоне считается крупный путь по тайлам, а в момент агры и уже во время движения постоянно считается уже более точный используя посчитанный ранее упрощённый как эвристику.
                        +5
                        biter-ов

                        Кусак. Они в русском переводе просто «кусаки». Spitters — «плеваки»

                          +1
                            +4

                            Меня всегда удивляло то, что байтеры находят артиллерию где попало на любом расстоянии. Исходя из бытового опыта, если не видишь атакующего, то надо переть в сторону откуда прилетело (а не делать pathfinding неограниченного размера).

                              0
                              Алгоритм очень упрощённо напоминает вариант реализованный в игре Казаки:

                              dailytelefrag.ru/articles/print.php?id=3895

                              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                              Самое читаемое