[Перевод] Новый алгоритм поиска пути в Factorio

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

Поиск пути

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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