Эффективен ли А *, даже когда препятствия движутся?

30

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

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

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

Этан Храбрый
источник

Ответы:

27

Есть несколько алгоритмов, которые намного быстрее, чем A *, когда вам нужно пересчитать путь с движущимися препятствиями. Смотрите здесь в разделе «Простые пересчеты».

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

  • Только пересчитывает лучший путь в редких интервалах
  • Совместное использование лучших путей среди нескольких юнитов ( пример )
  • Создание иерархического графика, поэтому вам нужно только пересчитать часть пути

и т.д. Вы можете найти более подробную информацию об этих трюках и многое другое на этом сайте или на страницах Amit's A *

BlueRaja - Дэнни Пфлугхофт
источник
10

Да. A * - это путь почти во всех случаях. Расчет стоимости вашего узла становится динамическим и, следовательно, более сложным для расчета и отслеживания.

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

Например: этот узел будет достигнут за 4 тика, занятых с тика № 3 до тика № 6, поэтому стоимость поездки на этом узле составляет 6 - 4 = +2 тика. Это все еще может быть лучшим путем.

Направление движения препятствия также должно быть принято во внимание.

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

Тупик - это когда оба ждут, пока другой переместится и никто не сдвинется

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

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

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

Получив эту информацию, вы также можете планировать перехват.

Стефан Хоккенхалл
источник
19
Боже мой, "живой замок" - вы описали ту ужасную уклонение влево-вправо, которую я вынужден постоянно делать в коридорах.
Итан Храбрый
2
Простое решение в режиме реального времени / взаимоблокировки заключается в случайном выборе между доступными опциями (например, 50% шансов не двигаться и 50% шансов двигаться влево). Пока каждый актер выбирает случайно, есть ненулевой шанс, что блокировка будет решена.
Draco18s
@ Draco18s И экспоненциально увеличивайте размер вашего колебания взад и вперед, пока кто-то не уступит (возможно, я только что описал, как разрешаются коллизии Ethernet!)
Cort Ammon - Восстановите Monica
Я полагаю, что вместо этого они могли бы сыграть « Каменные ножницы» или дружескую игру «Дилемма узника Петри» . ; P
Draco18s