¿Cuál es la solución estándar para encontrar caminos hacia un objetivo en movimiento?

Estoy trabajando en un juego similar a RTS 2D, el A * básico funciona perfectamente para mover una unidad del punto A al punto B.

Pero ahora me enfrento al problema de búsqueda de ruta continua, como A atacar un objeto en movimiento B, llamar a A * en cada cuadro una vez que la posición del objeto B cambió parece ineficiente.

Entonces, ¿cuál es el método estándar para este problema?

Por lo que sé, podría echar un vistazo al algoritmo D * que significa "Dynamic A *". Este algoritmo se utiliza para calcular la búsqueda de rutas para un entorno dinámico, aquí con un objetivo en movimiento.

Aquí hay un documento que usa D * para encontrar la ruta del objetivo en movimiento: Objetivo en movimiento D * Lite

Una opción es crear una nueva ruta una vez cada pocos fotogramas. Si lo hizo una o dos veces por segundo en lugar de más de 60 veces por segundo, es poco probable que el usuario lo note a menos que ambos sean dos objetos que se mueven muy rápido

Puede usar el enfoque de "curva de perro" que los perros aparentemente usan cuando cazan a alguien. Calculan dónde estará el punto de impacto "en el futuro" y los conjuntos de directamente a esa posición.

Una forma aproximada simple podría ser algo similar:

A = NPC

B = objetivo

T = tiempo para llegar a la posición B: s (B: posición inicial)

Calcule dónde estará B en el tiempo 'T' (si B continúa a la misma velocidad / ángulo) y vaya allí.

Esta no es la manera perfecta a medida que cambia la distancia, pero es mucho más simple que hacer una solución perfecta y mucho mejor que solo tratar de llegar a 'B'.

Estoy de acuerdo con Kylotan en que no existe un método estándar .

Un método que he visto funcionar fue asumir que el objetivo continúa moviéndose en la misma dirección y cambiar la posición del objetivo a medida que avanza a través de su algoritmo de búsqueda de ruta. Esto significa que debe mantener dos métricas en sus nodos A * (costo y tiempo en lugar de solo costo).

Hacerlo mejor que eso es muy difícil. A menos que realmente tenga conocimiento sobre el camino inquebrantable del objetivo, se dirigirá a la tierra de la IA bastante difícil porque tendrá una segunda adivinanza o simulación del comportamiento del objetivo para adivinar dónde estarán y el camino hacia eso. Este tipo de IA es un juego AB en tiempo real de la teoría de juegos, un área que no es estándar en ningún juego de herramientas de IA de juegos 3D.

Una forma de hacer una búsqueda dinámica de ruta es hacer que la entidad prediga hacia dónde va el objetivo e ir allí.

Una forma de hacerlo es usar una serie de Taylor.

Llamaré a la ruta del objetivo a lo largo del tiempo la función S (t) donde S es la posición yt es la hora actual y la aproximación a la ruta es A (f) yf es la fecha en el futuro que se aproxima .

Entonces la aproximación más simple y más estúpida es A (f) = 0.

El siguiente más simple es A (f) = S (t) donde t es el tiempo actual yf es el futuro. Esto predice que el objetivo simplemente se detiene en su lugar.

El tercero más simple es A (f) = S '(t) * f + S (t) donde S' es la derivada de S con respecto al tiempo. Esto predice que el objetivo continúa a una velocidad constante sin aceleración.

El cuarto más simple es A (f) = S '' (t) * f ^ 2/2 + S '(t) * f + S (t). Esto predice que el objetivo está acelerando a una velocidad constante como una bola que cae.

Sé que esto se puede reformular en términos de cambio en el tiempo, lo que probablemente sea más conveniente para un juego. Ahora S puede ser cualquier cosa. Podría ser una coordenada X, podría ser una coordenada Y, podría ser la distancia entre los objetos, podría ser un ángulo. También hay probablemente mejores métodos para predecir la ruta futura de un objeto, por lo que miraría un poco a mi alrededor.

Si el terreno está razonablemente abierto y el objetivo no está demasiado lejos del perseguidor, entonces podría usar el comportamiento de intercepción de dirección. Esencialmente, tomas la posición y la velocidad del objetivo para calcular una posición frente al objetivo que no está demasiado lejos y no demasiado cerca, y diriges al perseguidor hacia ese punto (calculado cada uno a intervalos regulares).