Как заставить агентов A * избегать других агентов?

Я реализую мультиагентный алгоритм A * на карте тайлов. Агенты движутся только по осям X и Y. Я избегаю столкновений между ними, проверяя, где находятся другие при расчете путей.

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

Кроме того, если нет северного коридора, то поиск пути не удастся.

Как я мог реализовать такой алгоритм?

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

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

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

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

Много лет назад мой друг работал над очень известным FPS, у которого была именно та проблема, которую вы описываете: ограниченная область будет иметь количество ИИ-персонажей, которые имеют определенные желаемые позиции, и алгоритм поиска пути постоянно сталкивает их друг в друга. В частности, игрок, скажем, бросал гранату в маленькую комнату, полную врагов, и все персонажи ИИ в этой области пытались бежать к выходу, но сталкивались друг с другом и в итоге останавливались, поворачиваясь, бить кого-то, оборачиваться и так далее. Это выглядит очень нереально.

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

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

Я обычно считаю, что лучше дополнить путь A * другими формами поиска пути для других локализованных сценариев; Избегание юнитов обычно является одним из них, особенно в мире, где одновременно работают несколько агентов, которые создают динамические блокираторы).

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

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

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

Если у вас есть система движения, основанная на поворотах / тиках, вы можете создать трехмерный график, в котором каждый переход перемещает агента в то, как карта будет выглядеть в будущем. Затем попросите каждого агента заявить плитки, на которых они будут находиться в этой точке в будущем, и пометить их как недоступные. Затем у каждого агента есть дополнительная опция «ожидание» на следующем тике как третий способ перехода через график. Это будет сложнее в вашей системе, но должно дать вам лучшие результаты, чем случайное ожидание. Еще лучше, если вы разрешите двум агентам общаться, причем один из них отправит сообщение «Я хочу передать вас», если через этого агента проходит кратчайший путь,

При использовании такого алгоритма, как A *, вы имеете наибольшую свободу работы с эвристикой затрат.

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

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

В случае, когда существует только один путь, поиск пути либо не удастся, либо они будут продвигаться друг к другу до тех пор, пока не будут заблокированы.

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

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

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

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

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

1. Как вы решаете, есть ли другой приемлемый способ обойти другого агента или нет? Вы не хотите ждать другого агента, если есть достаточно места, чтобы обойти его. Ошибка поиска пути при рассмотрении другого агента является явным признаком ситуации, которую вы хотите исправить, но в приведенном вами примере не будет ошибки поиска пути. Но вы можете - с небольшим расчетом - решить, дает ли вам альтернативный путь A * просто обойти другого агента по маленькому кругу или использовать совершенно другой путь, такой как северный коридор.

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

Одним из возможных решений было бы отключение столкновения юнитов в таких труднодоступных местах.

Например, в игре Starcraft рабочие (SCV, Probes, Drones) не сталкиваются друг с другом при добыче кристаллов.