Заставить ИИ идти разными путями

16

У меня есть 2d игра сверху вниз, где ИИ появляется на краях карты и бежит к центру.

Я использую A * и узел сетки, чтобы найти путь.

Прямо сейчас ИИ появляется в точке на краю карты и все выбирают один и тот же путь, который является кратчайшим путем к центру.

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

Я могу сразу придумать две идеи для этого, но хотел бы знать, есть ли другие способы или способы, которыми люди часто пользуются?

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

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

Какие подходы люди нашли работу лучше всего, чтобы заставить ИИ варьировать пути, которые они выбирают, выглядеть убедительно и удивительно?

TerryB
источник

Ответы:

7

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

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

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

Совместная диффузия делает то, что вы хотите, неявно, как часть алгоритма. Но это не тривиально для реализации.

инженер
источник
Совместная диффузия - это просто заливка с некоторым весом. Это легко реализовать, может быть, проще, чем A *. Это просто требует другого взгляда на ваш мир - возможно, нетривиальный концептуальный сдвиг, но не проблема реализации.
Это все еще нетривиально реализовать из-за того, что это нестандартная точка зрения с точки зрения управления объектами ИИ :)
Инженер
Спасибо Ник. Я думаю, что установка некоторых путевых точек, которые окружают игрока в центре карты, будет основным путем. Не уверен на этом этапе, будут ли они генерироваться динамически или для каждого уровня в моей конкретной ситуации будет использоваться ручная обработка. Еще раз спасибо!
TerryB
12

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

Ничего
источник
В конечном итоге враги будут бегать как цыплята, и в мелкозернистой среде пути в любом случае не будут такими разными. Это хорошее дополнение к другим решениям, но не решение само по себе
Coyote
@Coyote Это во многом зависит от структуры nav-mesh и отношений между весами узлов, скоростями и случайным компонентом. Вот почему я назвал ответ попыткой, а не определенным ответом.
Nevermind
Действительно :) Я обычно фанат энтропии. Но конечный результат редко бывает велик.
Койот
Я действительно считаю, что ответ Ника Виггилла намного лучше, чем мой. Но так или иначе это не получает голосов, которых это заслуживает.
Nevermind
Это ... Но ваш первый и простой ... мы могли бы попытаться проголосовать против: P
Койот
3

Мне нравится ответ Nevermind , однако, учитывая ограничение, описанное в комментариях, я бы попробовал:

  1. Алгоритм для одного подразделения до центра, записывает общее пройденное расстояние.
  2. Для каждой последующей единицы выделяют это расстояние, которое является случайным и на небольшую величину длиннее этого.
  3. Делая A * для каждого юнита, добавьте дополнительный вес в зависимости от того, насколько вы близки и как далеко вы хотите путешествовать. Это, вероятно, будет что-то вроде (distanceToGoal) + Max(0, desiredDistance - distanceTravelled)).

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

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

Джонатан Дикинсон
источник
2

Как указал Ник Виггилл, самый простой подход - создать круг вокруг цели.

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

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

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

койот
источник
если ваша карта поддерживает это, найдите «интересные» места вокруг этого круга (дверные проемы, укрытие, деревья, камни, здания; любой узел с некоторым тактическим преимуществом), и пусть ваши враги сначала направятся в эти места, если они доступны и выходят только в открытое, если они должны. Это будет выглядеть намного умнее, чем простое попадание в случайное место на краю круга.
DampeS8N
Благодаря Coyote, да, я, вероятно, собираюсь использовать решение Nicks и, как предлагает DampeS8N, некоторые ключевые места, представляющие интерес, в качестве путевых точек. Чтобы избежать проблемы ИИ "пересечения круга", я просто собираюсь значительно увеличить стоимость узлов в круге, поэтому A * должен обойти его с надеждой :)
TerryB
2

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

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

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

Возможно, я бы порекомендовал более простой способ взглянуть на это. Когда вы ищите пути, не просто поддерживайте единый лучший путь, который я нашел до сих пор. Вместо этого соберите набор из лучших 5 или 10 путей. Используйте порог, чтобы отбросить очевидные выбросы. Например, если лучший путь проходит через 20u, чтобы добраться до цели, следующий лучший путь проходит через 21u, а следующий - 50u. Установите порог на 20% больше, чем лучший путь, и поэтому откажитесь от пути 50u, потому что он тупо длиннее. Теперь у вас есть несколько путей на выбор, и, выбрав случайным образом из этого набора путей, ваши актеры будут принимать разные решения.

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

MrCranky
источник
1

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

Какой-то парень
источник