Используя A * и все еще избегая столкновений?

Question

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

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

Алгоритм работает так, что все юниты перемещают одну плитку за раз.

Answer 1

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

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

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

Answer 2

Вы можете использовать поведение стада, чтобы они следовали по одному и тому же общему пути, но не складывались друг на друга.Вот пример XNA, предоставленный MS здесь: http://xbox.create.msdn.com/en-US/education/catalog/sample/flocking

Answer 3

Вы пересчитываете кратчайший путь на каждом временном шаге?

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

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

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

РЕДАКТИРОВАТЬ 1 На самом деле, сложность алгоритма в обоих случаях одинакова, однако мне кажется, что вариант 1 гораздо проще реализовать.

Answer 4

Как насчет итеративного поиска пути?

1. Запустите алгоритм поиска пути, игнорируя проблемы с перекрытием.Это найдет кратчайший путь.
2. Имитировать движение ползучести.Это моделирование должно выполняться с движением на основе плитки, чтобы оно было быстрым.
3. Выберите половину (возитесь с этим) крипов, которые ожидают в линии и, следовательно, не двигаются.Перезапустите алгоритм для этих крипов, но добавьте дополнительный штраф веса в этой позиции, которую они ждали.Этот вес будет применяться ТОЛЬКО к крипам, у которых был дополнительный вес.
4. Повторяйте шаги 2-3 до тех пор, пока не будет выполнено какое-либо условие, уделяя некоторое (воздерживаясь от этого) внимание на предыдущие дополнительные веса.

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

Answer 5

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

Хотя это не обязательно будет самым быстрым путем.Это также может сделать их более непредсказуемыми, что в зависимости от вашей целевой сложности может быть хорошим или плохим:)