Каково стандартное решение для поиска пути к движущейся цели?

Я работаю над 2D RTS-подобной игрой, базовая A * отлично подходит для перемещения юнита из точки A в точку B.

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

так что является стандартным методом для этой проблемы?

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

Вот документ, использующий D * для поиска пути перемещения цели: Moving Target D * Lite

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

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

Простой примерный способ может быть чем-то вроде:

A = NPC

B = цель

T = время, чтобы добраться до позиции B: s (начальная позиция B: s)

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

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

Я согласен с Kylotan, что нет стандартного метода.

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

Сделать лучше, чем это очень сложно. Если вы на самом деле не обладаете знаниями о непоколебимом пути цели, вы движетесь в страну довольно жесткого ИИ, потому что у вас будет второе угадывание или моделирование ИИ поведения цели, чтобы угадать, где они будут находиться, и путь к этому. Этот вид ИИ представляет собой AB-игру в реальном времени из теории игр, область, которая не является стандартной в любом инструментарии ИИ для 3D-игр.

Один из способов динамического поиска пути - предсказать сущность, куда движется цель.

Один из способов сделать это - использовать серию Тейлора.

Я назову путь цели с течением времени функцией S (t), где S - это позиция, а t - текущее время, а приближение к пути - это A (f), а f - это дата в будущем, которая приближается. ,

Тогда самое простое и самое глупое приближение - это A (f) = 0.

Следующий простейший - это A (f) = S (t), где t - текущее время, а f - будущее. Это предсказывает, что цель просто останавливается на месте.

Третий простейший: A (f) = S '(t) * f + S (t), где S' - производная от S по времени. Это предсказывает, что цель продолжается с постоянной скоростью без ускорения.

Четвертый простейший - это A (f) = S '' (t) * f ^ 2/2 + S '(t) * f + S (t). Это предсказывает, что цель ускоряется с постоянной скоростью, как падающий шар.

Я знаю, что это можно перефразировать с точки зрения изменения во времени, что, вероятно, более удобно для игры. Теперь S может быть чем угодно. Это может быть координата X, это может быть координата Y, это может быть расстояние между объектами, это может быть угол. Также есть, вероятно, лучшие методы предсказания будущего пути объекта, так что я бы немного осмотрелся.

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