Поиск пути с помощью динамических препятствий

Question

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

Однако как мне справиться с ситуацией, когда эти препятствия движутся с определенной скоростью?
Есть ли вариант алгоритма LPA * или D * Lite, который обрабатывает это?
ИЛИ Должен ли я комбинировать некоторую форму поведения рулевого управления с этими алгоритмами?

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

Answer 1

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

Движение персонажа состоит из двух компонентов: выбор цели высокого уровня и поиск пути, и локальное управление. Поиск пути решает проблему «я здесь, и мне нужно знать, как туда добраться». Местное рулевое управление решает проблему «я еду туда, а кто-то только что встал на моем пути».

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

В книге «Искусственный интеллект для игр» (автор сайта: http://ai4g.com/ и Amazon: http://amzn.to/k9K62F) подробно описаны несколько способов сочетания поиска пути с предотвращением столкновений. В этой статье также рассматриваются алгоритмы управления довольно хорошо на высоком уровне. Высокоэффективный метод, который я реализовал, - это управляющий конвейер, также известный как кооперативный арбитраж.

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

Answer 2

В этой статье есть отличные идеи о динамическом А *, которые могут быть вам полезны

В любое время Динамический A *: Алгоритм перепланирования в любое время Максим Лихачев, Дейв Фергюсон † Джефф Гордон †, Энтони Стентц † и Себастьян Трун Также эта статья , Рандомизированное планирование кинодинамического движения с движущимися препятствиями by Дэвид Хсу Роберт, Киндель Жан-Клод Латомб, Стивен Рок

Они должны быть хорошим началом.