quelle est la solution standard pour trouver un chemin vers une cible en mouvement?

Je travaille sur un jeu 2D RTS, le A de base fonctionne parfaitement pour déplacer une unité du point A au point B.

Mais maintenant, je suis confronté au problème continu de recherche de chemin, comme A attaque un objet en mouvement B, appelle A * à chaque image une fois que la position de l'objet B a changé semble inefficace.

alors quelle est la méthode standard pour ce problème?

D'après ce que je sais, vous pouvez jeter un œil à l'algorithme D * qui signifie "Dynamic A *". Cet algorithme est utilisé pour calculer le pathfinding pour un environnement dynamique, ici avec une cible mobile.

Voici un document utilisant D * pour déplacer la recherche de chemin cible: Moving Target D * Lite

Une option consiste à créer un nouveau chemin uniquement toutes les quelques images. Si vous l'avez fait une ou deux fois par seconde plutôt que plus de 60 fois par seconde, il est peu probable que l'utilisateur le remarque à moins qu'il ne s'agisse de deux objets se déplaçant très rapidement

Vous pouvez utiliser l'approche "courbe de chien" que les chiens utilisent apparemment lorsqu'ils traquent quelqu'un. Ils calculent où le point d'impact sera "dans le futur" et fixe directement à cette position.

Un moyen approximatif simple pourrait être quelque chose dans le sens:

A = PNJ

B = cible

T = temps pour arriver à la position B: s (position initiale B: s)

Calculez où B sera dans le temps «T» (si B continue à la même vitesse / angle) et allez-y à la place.

Ce n'est pas le moyen parfait car la distance change, mais beaucoup plus simple que de faire une solution parfaite et bien mieux que d'essayer simplement d'arriver à «B».

Je suis d'accord avec Kylotan qu'il n'y a pas de méthode standard .

Une méthode que j'ai vue fonctionner était de supposer que la cible continue de se déplacer dans la même direction et de changer la position de l'objectif pendant que vous parcourez votre algorithme de recherche de chemin. Cela signifie que vous devez conserver deux métriques dans vos nœuds A * (coût et temps par opposition au seul coût).

Faire mieux que cela est très difficile. À moins que vous ne connaissiez réellement le chemin inébranlable de la cible, vous vous dirigez vers le pays de l'IA assez difficile, car vous aurez la deuxième devinette de l'IA ou simulerez le comportement de la cible afin de deviner où ils se trouveront et le chemin vers cela. Ce type d'IA est un jeu AB en temps réel issu de la théorie des jeux, un domaine qui n'est pas standard dans toute boîte à outils d'IA de jeu 3D.

Une façon de rechercher un chemin dynamique consiste à faire prédire par l’entité où va la cible et à y aller.

Une façon de procéder consiste à utiliser une série Taylor.

J'appellerai le chemin de la cible au fil du temps la fonction S (t) où S est la position et t est l'heure actuelle et l'approximation du chemin est A (f) et f est la date dans le futur une approximation .

Alors l'approximation la plus simple et la plus stupide est A (f) = 0.

Le plus simple suivant est A (f) = S (t) où t est l'heure actuelle et f est l'avenir. Cela prédit que la cible s'arrête simplement en place.

Le troisième plus simple est A (f) = S '(t) * f + S (t) où S' est la dérivée de S par rapport au temps. Cela prédit que la cible continue à une vitesse constante sans accélération.

Le quatrième plus simple est A (f) = S '' (t) * f ^ 2/2 + S '(t) * f + S (t). Cela prédit que la cible accélère à une vitesse constante comme une balle qui tombe.

Je sais que cela peut être reformulé en termes de changement dans le temps, ce qui est probablement plus pratique pour un jeu. Maintenant, S peut être n'importe quoi. Ce pourrait être une coordonnée X, ce pourrait être une coordonnée Y, ce pourrait être la distance entre les objets, ce pourrait être un angle. Il existe également de meilleures méthodes probables pour prédire le chemin futur d'un objet, je regarderais donc un peu.

Si le terrain est raisonnablement ouvert et que la cible n'est pas trop loin du poursuivant, vous pouvez utiliser le comportement de direction d'interception. Essentiellement, vous prenez la position et la vitesse de la cible pour calculer une position devant la cible qui n'est pas trop loin et pas trop près, et vous dirigez le poursuivant vers ce point (calculé chacun à intervalles réguliers).