A * est-il efficace même lorsque les obstacles se déplacent?

30

Je commence tout juste à en apprendre davantage sur la recherche de chemin et j'ai étudié l'algorithme A * et ma principale préoccupation est que tous les exemples que j'ai vus montrent des obstacles statiques qu'il calcule.

Si j'ai des obstacles en mouvement, disons d'autres personnages par exemple, se déplaçant également pour que le personnage trouve son chemin, je suppose que je devrai exécuter l'algorithme à chaque image, mais je crains que cela devienne assez cher pour que le matériel traite chaque image pour chaque acteur en mouvement.

Ainsi, A * est-il toujours suffisamment efficace pour être utilisé lorsque les obstacles se déplacent également, ou existe-t-il une autre méthode de recherche de chemin qui gère les obstacles en mouvement avec plus d'éloquence?

Ethan The Brave
la source

Réponses:

27

Il existe plusieurs algorithmes beaucoup plus rapides que A * lorsque vous devez recalculer un chemin avec des obstacles en mouvement. Voir ici sous "Recalculs simples".

Cependant, vous n'allez probablement pas trouver de solution standard pour l'un d'entre eux, donc dans 99% des cas, ils sont exagérés pour un jeu. Votre temps serait mieux utilisé en utilisant une solution A * existante et entièrement optimisée, et en utilisant les astuces existantes courantes pour accélérer la recherche de chemin dans les jeux:

  • Recalculer uniquement le meilleur chemin dans des intervalles peu fréquents
  • Partage des meilleurs chemins entre plusieurs unités ( exemple )
  • Création d'un graphe hiérarchique pour ne recalculer qu'une partie du chemin

etc. Vous pouvez trouver plus d'informations sur ces astuces et plus partout sur ce site, ou sur les pages A * d'Amit

BlueRaja - Danny Pflughoeft
la source
10

Oui. A * est toujours le chemin à parcourir dans presque tous les cas. C'est votre calcul de coût de nœud qui devient dynamique et donc plus complexe à calculer et à suivre.

Si vous savez déjà où seront les obstacles mobiles à l'avenir, votre A * peut prendre en compte la temporalité des obstacles dans la fonction de coût.

Par exemple: Ce nœud sera atteint en 4 ticks, occupé du tick # 3 au tick # 6, donc le coût du voyage sur ce nœud est de 6 - 4 = +2 ticks. C'est peut-être toujours le meilleur chemin.

Le sens de déplacement de l'obstacle doit également être pris en compte.

Si vous ne le savez pas à l'avance, vous ne pouvez assumer aucun obstacle et recalculer le chemin lorsque les obstacles sont atteints, mais vous devrez faire quelque chose pour les blocages et les verrous de sécurité. (Il en va de même si vous pouvez prédire où se trouveront les obstacles, mais qu'il s'agit en soi d'un type d'évitement d'impasse / de blocage et qui peut être assez bon pour votre objectif.)

Un blocage se produit lorsque les deux attendent que l'autre bouge et qu'aucun ne bouge.

Un livelock est lorsque les deux ( ou plus <- c'est important à considérer) se déplacent pour éviter l'autre dans la même direction et finissent par aller et venir sans progrès.

La résolution des livelocks peut devenir très complexe et cela dépend entièrement des règles de collision et de la mécanique de votre jeu (par exemple: doivent-ils combattre et détruire l'obstacle?).

Il revient souvent à vos objets en mouvement de planifier des réservations de nœuds / chemins (n'oubliez pas les annulations lorsqu'ils changent de chemin ou meurent) afin que d'autres objets en mouvement puissent planifier à l'avance.

Une fois que vous avez ces informations, vous pouvez également planifier des interceptions.

Stéphane Hockenhull
la source
19
Oh mon dieu, "livelock" - vous avez décrit cette horrible chose d'esquive gauche-droite que je finis par devoir faire dans les couloirs tout le temps.
Ethan The Brave
2
Une solution live / deadlock simple consiste à choisir aléatoirement entre les options disponibles (par exemple 50% de chances de ne pas bouger et 50% de chances de se déplacer vers la gauche). Tant que chaque acteur choisit au hasard, il y a une chance non nulle que le verrouillage soit résolu.
Draco18s
@ Draco18s Et augmentez de façon exponentielle la taille de vos mouvements de va-et-vient jusqu'à ce que l'on cède (je viens de décrire comment les collisions Ethernet sont résolues!)
Cort Ammon - Réinstallez Monica
Je suppose qu'ils pourraient jouer à Rock Paper Scissors ou à une partie amicale de Petri Dish Prisoner's Dilemma à la place. ; P
Draco18s