Поиск пути для бегства

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

Но как рассчитать путь, когда объект находится в точке A и хочет уйти из точки B как можно быстрее и дальше?

Немного справочной информации: моя игра использует 2D-среду, которая не основана на тайлах, но имеет точность с плавающей запятой. Движение основано на векторах. Поиск пути осуществляется путем разбиения игрового мира на прямоугольники, которые можно пройти или не пройти, и построения графа из их углов. У меня уже есть поиск путей между точками, работающими с использованием алгоритма Дейкстры. Вариант использования алгоритма бегства заключается в том, что в определенных ситуациях актеры в моей игре должны воспринимать другого актера как опасность и избегать ее.

Тривиальным решением было бы просто переместить актера в векторе в направлении, противоположном угрозе, до тех пор, пока не будет достигнуто «безопасное» расстояние, или актер не достигнет стены, где он затем покрывается страхом.

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

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

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

Существуют ли стандартные решения для этой проблемы?

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

Шаг 1. Преобразуйте алгоритм Дейкстры в A * . Это должно быть просто, просто добавив эвристику, которая измеряет минимальное расстояние, оставшееся до цели. Эта эвристика добавляется к пройденному расстоянию при оценке узла. В любом случае вы должны внести это изменение, так как оно значительно улучшит ваш поиск пути.

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

Если вы действительно хотите, чтобы ваши актеры умели убегать, просто Dijkstra / A * pathfinding не поможет. Причина этого заключается в том, что для того, чтобы найти оптимальный путь спасения от врага, актер также должен учитывать, как противник будет двигаться в преследовании.

Следующая диаграмма MS Paint должна иллюстрировать конкретную ситуацию, когда использование только статического нахождения пути для максимизации расстояния от противника приведет к неоптимальному результату:

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

Чтобы правильно найти такие стратегии побега, вам понадобится альтернативный алгоритм поиска, такой как минимаксный поиск, или его уточнения, такие как альфа-бета-обрезка . Такой алгоритм, примененный к описанному выше сценарию с достаточной глубиной поиска, будет правильно выводить, что переход в тупиковый путь вправо неизбежно приведет к захвату, тогда как нахождение на круге не приведет (пока зеленая точка может обогнать красный)

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

На практике вы, вероятно, не сможете выполнять очень глубокие поиски в реальном времени с большим количеством агентов, поэтому вам придется во многом полагаться на эвристику. Выбор этих эвристик будет определять «психологию» ваших актеров - насколько они умны, как много внимания они уделяют различным стратегиям, насколько они совместны или независимы и т. Д.

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

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

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

Если ваш убегающий актер быстрее, чем какой-либо другой актер, которого также может заинтересовать угроза, выберите точку в направлении этого другого актера, но за его пределами и найдите путь к этой точке: «Мне не нужно опережать медведя Я должен только опередить тебя. "

Без возможности убежать, убить или отвлечь угрозу, ваш актер обречен, верно? Так что выбирайте произвольную точку, к которой нужно бежать, и если вы туда доберетесь, и угроза все еще преследует вас, какого черта: поверните и сражайтесь.

Поскольку определение подходящей целевой позиции во многих ситуациях может оказаться непростым делом, возможно, стоит рассмотреть следующий подход, основанный на двухмерных сеточных картах занятости. Его обычно называют «итерацией значения», и в сочетании с градиентным спуском / подъемом он дает простой и довольно эффективный (в зависимости от реализации) алгоритм планирования пути. Благодаря своей простоте, он хорошо известен в области мобильной робототехники, в частности, для "простых роботов", которые перемещаются в помещениях. Как подразумевается выше, этот подход предоставляет средства для нахождения пути от начальной позиции без явного указания целевой позиции следующим образом. Обратите внимание, что при желании можно указать целевую позицию, если она доступна. Кроме того, подход / алгоритм представляет собой поиск в ширину,

В двоичном случае двумерная сеточная карта занятости - одна для занятых ячеек сетки и ноль в другом месте. Обратите внимание, что это значение занятости также может быть непрерывным в диапазоне [0,1], я вернусь к этому ниже. Значение заданной ячейки сетки g _i равно V (g _i ) .

Базовая версия

1. Предполагая, что ячейка сетки g ₀ содержит начальную позицию. Установите V (g ₀ ) = 0 и поместите g ₀ в очередь FIFO.
2. Возьмите следующую ячейку сетки g _i из очереди.
3. Для всех соседей g _j of g _i :
   • Если g _j не занят и ранее не посещался:
     • V (g _j ) = V (g _i ) +1
     • Отметить g _j как посещенные.
     • Добавьте g _j в FIFO-очередь.
4. Если заданный порог расстояния еще не достигнут, переходите к (2.), в противном случае переходите к (5.).
5. Путь получается путем следования наискорейшего подъема градиента, начиная с g ₀ .

Примечания к шагу 4.

• Как указано выше, шаг (4.) требует отслеживать максимальное пройденное расстояние, которое было опущено в вышеприведенном описании из соображений ясности / краткости.
• Если задана целевая позиция, итерация останавливается, как только достигается целевая позиция, т.е. обрабатывается / посещается как часть шага (3.).
• Конечно, также возможно просто обработать всю карту сетки, то есть продолжать, пока все (свободные) ячейки сетки не будут обработаны / посещены. Ограничивающим фактором, очевидно, является размер карты-сетки в сочетании с ее разрешением.

Расширения и дальнейшие комментарии

Уравнение обновления V (g _j ) = V (g _i ) +1 оставляет достаточно места для применения всех видов дополнительной эвристики путем уменьшения V (g _j ).или аддитивный компонент, чтобы уменьшить значение для определенных опций пути. Большинство, если не все, такие модификации могут быть красиво и в общем случае встроены с использованием карты сетки с непрерывными значениями из [0,1], которая фактически представляет собой этап предварительной обработки исходной двоичной карты сетки. Например, добавление перехода от 1 к 0 по границам препятствий приводит к тому, что «субъект» предпочтительно остается чистым от препятствий. Такая сеточная карта может, например, быть сгенерирована из двоичной версии с помощью размытия, взвешенного расширения или подобного. Добавление угроз и врагов в качестве препятствий с большим радиусом размытия штрафует пути, которые приближаются к ним. Можно также использовать диффузионный процесс на общей карте сетки следующим образом:

V (g _j ) = (1 / (N + 1)) × [V (g _j ) + сумма (V (g _i ))]

где « сумма » относится к сумме по всем соседним ячейкам сетки. Например, вместо создания двоичной карты начальные (целочисленные) значения могут быть пропорциональны величине угроз, а препятствия представляют «небольшие» угрозы. После применения процесса диффузии значения сетки должны / должны быть масштабированы до [0,1], а ячейки, занятые препятствиями, угрозами и врагами, должны быть установлены / принудительно установлены на 1. В противном случае масштабирование в уравнении обновления может не работает, как хотелось бы.

Существует много вариантов этой общей схемы / подхода. Препятствия и т. Д. Могут иметь небольшие значения, в то время как свободные ячейки сетки имеют большие значения, что может потребовать снижения градиента на последнем этапе в зависимости от цели. В любом случае, подход, на мой взгляд, удивительно универсален, довольно прост в реализации и потенциально довольно быстр (в зависимости от размера / разрешения сетки). Наконец, как и во многих алгоритмах планирования пути, которые не предполагают конкретной целевой позиции, существует очевидный риск застрять в тупиках. В некоторой степени может быть возможно применить выделенные этапы последующей обработки перед последним этапом, чтобы уменьшить этот риск.

Вот еще одно краткое описание с иллюстрацией в Java-Script (?), Хотя иллюстрация не работает с моим браузером :(

http://www.cs.ubc.ca/~poole/demos/mdp/vi.html

Много более подробной информации о планировании можно найти в следующей книге. Итерация значения конкретно обсуждается в главе 2, раздел 2.3.1 Оптимальные планы фиксированной длины.

http://planning.cs.uiuc.edu/

Надеюсь, что это помогает, с уважением, Дерик.

Как насчет хищников? Давайте просто сделаем рейкаст на 360 градусов по положению Хищника с соответствующей плотностью. И у нас могут быть образцы убежища. И выбрать лучшее убежище.

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