Пятничные факты #317 – Новый алгоритм поиска пути

Поделиться

опубликовали Oxyd, TOGoS, Klonan

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

На прошлой неделе мы упомянули изменение, в котором кусаки не сталкивались друг с другом, но это было не единственное связанное с кусаками обновление, которое мы выпустили на прошлой неделе.Так совпало, что обновления этой недели включали в себя то, над чем я работал несколько недель назад, – обновление системы поиска пути.

Поиск пути

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

Для выполнения своей работы используется алгоритм A * (произносится как «А Звезда»). Простой пример поиска пути A * показан на видео ниже: Кусака хочет обойти некоторые утесы. Алгоритм начинает исследовать карту вокруг кусаки(показана белыми точками). Сначала он пытается идти прямо к цели, но как только он достигает скал, он «разливается» в обе стороны, пытаясь найти положение, из которого он снова может идти к цели.

Каждая точка в анимации представляет узел. Каждый узел запоминает свое расстояние от начала поиска и оценку расстояния от этого узла до цели – эта оценка обеспечивается так называемой эвристической функцией. Эвристические функции – это то, что заставляет A * работать – это то, что направляет алгоритм в правильном направлении.

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

Простая прямолинейная эвристическая функция хороша для поиска пути на относительно коротких расстояниях. Это было хорошо в прошлых версиях Factorio – о том, что единственное нахождение на дальних расстояниях было сделано кусаками, рассерженными загрязнением, и это случается не очень часто, условно говоря. Однако в наши дни у нас есть артиллерия. Артиллерия может легко стрелять  множество кусак в дальнем конце большого озера, которые затем попытаются найти путь вокруг озера. Видео ниже показывает, как это выглядит, когда простой алгоритм A *, который мы использовали до сих пор, пытается обойти озеро.

Сжимающиеся чанки

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

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

Это был один из наших специалистов по доступу к источникам, Allaizn, который пришел к идее, которую я в итоге реализовал. Оглядываясь назад, идея очевидна.

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

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

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

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

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

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

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

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

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

На видео ниже показана новая система поиска пути в действии. Синие круги – это абстрактные узлы; белые точки – это базовый поиск. Поиск пути был значительно замедлен, чтобы сделать это видео, чтобы показать, как оно работает. На нормальной скорости весь поиск занимает всего несколько тиков. Обратите внимание, что базовый поиск, который все еще использует тот же старый алгоритм, который мы всегда использовали, просто «знает», куда идти вокруг озера, как по волшебству.

Поскольку абстрактный указатель пути используется только для предоставления эвристических оценок расстояния, базовый поиск может довольно легко отклониться от пути, предложенного абстрактным поиском. Это означает, что даже при том, что наша схема сокращения фрагментов игнорирует все объекты, базовый указатель пути может обойти их без особых проблем. Игнорирование объектов в процессе упрощения карты означает, что нам не нужно повторять их каждый раз, когда объект помещается или удаляется, а нужно только покрывать изменяемые фрагменты (например, на свалке) – что происходит гораздо реже, чем размещение объектов.

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

Прощаемся TOGoS TOGoS

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

Основная причина этого переключения – то, что работа полностью удаленно оказалась тем, с чем я не смог справиться. Но кроме того, мой основной вклад в проект, программируемый генератор карт, является полным, стабильным и довольно хорошо понятным по крайней мере еще одному человеку, поэтому с точки зрения времени это показалось мне хорошим моментом для продолжения. Для работы в ферме кубов написание Android приложений для беговых дорожек, по-видимому.
Посмотрим как пойдет!

Для меня было честью участвовать в этом удивительном проекте и оставить на нем свой отпечаток. И работа над большой и довольно хорошо управляемой базой кода C ++, полной вещей, сделанных немного иначе, чем я когда-либо думал, была открытием для ума.

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

Я буду продолжать читать FFF каждую неделю, читать форум и, возможно, обновлять документацию здесь и там. Надеюсь, я найду время, чтобы проверить свои собственные изменяющие ландшафт моды. И я с нетерпением жду возможности увидеть, что еще вы с этим сделаете. (Который включает в себя работу с отставанием модов – мне еще предстоит добраться до части исследования космоса в Space Exploration!)

Всем пока на данный момент.

Обзор сообщества- 13×9 Micro Factory Klonan

Более 100 FFF назад мы рассказали о фабрике DaveMcW 9×14 Micro Factory (FFF-197). Хотя на это ушло более двух лет, он улучшил свой дизайн еще больше, и результат такой же впечатляющий, как и раньше.

//youtu.be/9dzQge6pe2o

В этом сообщении на форуме он предлагает более подробное объяснение своей микро фабрики.

Как всегда, дайте нам знать, что вы думаете на нашем форуме.


Поделиться

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