Comment dois-je replanifier A *?

10

J'ai un boss ennemi qui cherche le chemin en cherchant le joueur en utilisant l'algorithme A *. C'est un environnement assez complexe, et je le fais en Flash, donc la recherche peut devenir un peu lente lorsqu'elle recherche sur de longues distances. Si le joueur était immobile, je ne pouvais chercher qu'une seule fois, mais en ce moment je cherchais chaque image. Cela prend suffisamment de temps pour que mon framerate souffre.

Quelle est la solution habituelle à cela? Existe-t-il un moyen de "replanifier" A * sans refaire toute la recherche? Dois-je simplement chercher un peu moins souvent (toutes les demi-secondes ou secondes) et accepter qu'il y aura un peu d'inexactitude dans le chemin?

Gregory Avery-Weir
la source

Réponses:

13

Vous n'avez pas besoin de rechercher le chemin entier dans une seule image, je l'ai fait en donnant une limite à la boucle de recherche, l'IA commencera alors à suivre le peu d'informations dont elle dispose, et l'image suivante je chercherai encore plus , cela peut prendre 3 images jusqu'à ce que le chemin soit trouvé. Cela peut sembler assez convaincant, car il semble que l'IA recherche réellement.

PhilCK
la source
+1. C'est aussi ce que Mat Buckland décrit dans son livre sur l'IA. Il l'appelle "Planification de parcours en tranches de temps" ( books.google.ch/… ). Bon produit.
bummzack
8

Vous pouvez utiliser la détection de proximité pour exécuter l'algorithme toutes les quelques images si la distance est très grande (car dans la plupart des cas, si la distance est grande, le chemin cible ne changera pas radicalement d'une image à l'autre). Par exemple:

      Distance > 100, run A* every 2 seconds
100 > Distance >  50, run A* every 1 second
50  > Distance >  25, run A* every 10 frames
25  > Distance <  25, run A* every frame

Cela suppose qu'il existe une distance où l'exécution de A * chaque trame a des performances qui sont toujours acceptables. En bref, j'irais pour votre deuxième option. Surtout si ce que vous avez fonctionne, j'éviterais de réimplémenter autre chose si je peux simplement réduire ce qui fonctionne bien. L'essentiel est que vous devrez l'essayer pour voir si cela fonctionne pour votre jeu.

Nate
la source
8

Ne répondant pas vraiment à votre question exacte, mais ... si vous êtes prêt à "tricher", vous pouvez faire en sorte que le joueur laisse "le fil d'Ariane" et demander au patron de les suivre. Si le chemin du fil d'Ariane se croise, suivez le plus récent (cela fait que le boss évite les boucles et autres chemins qui peuvent être trop longs, sans oublier de ne pas suivre le chemin exact du joueur)

Cela fonctionnerait bien si le patron est une sorte d'animal avec un bon odorat. Cela fonctionnerait un peu comme suivre l'odeur du joueur :)

ggambett
la source
5

Votre cas est à peu près ce à quoi HPA * a été inventé pour répondre. Si cela semble exagéré, cependant, j'aurais tendance à penser que la recherche de chemin toutes les demi-secondes devrait fonctionner assez bien.

le chaos
la source
4

S'il s'agit d'un environnement statique, vous pouvez précalculer le chemin le plus court toutes paires.

Peter Taylor
la source
2
S'il s'agit d'un petit environnement statique.
Dépend de la plate-forme et de la mémoire disponibles.
Nate
@Joe, @Nate, c'est vrai.
Peter Taylor
2

J'ai créé un jeu pour une compétition de 48 jeux où un personnage A * suit le joueur autour d'un niveau. Parce que mon implémentation A * était lente (elle ne pouvait pas exécuter chaque trame), j'ai mis l'intervalle sur un délai de trois secondes. Cela a eu le résultat inattendu de permettre au joueur de "tromper" l'IA pendant quelques instants. Cela a en fait rendu le jeu plus amusant.

Plus tard, j'ai amélioré les performances de l'implémentation A * et essayé de l'exécuter sur chaque trame. Le jeu a cessé d'être amusant car l'ennemi recherchait toujours parfaitement le joueur.

C'était inattendu et une bonne expérience d'apprentissage.

GloryFish
la source
1
C'est un bon point. Je me souviens avoir lu sur la recherche de chemin dans pac-man où ils ont délibérément utilisé un algorithme imparfait, permettant au joueur de déjouer les fantômes. Chaque fantôme avait une imperfection légèrement différente qui lui donnait plus de caractère. Ce qu'il faut retenir ici, c'est que dans les jeux, c'est amusant> tout le reste.
Nick Van Brunt
0

À moins que vous ne vouliez (ou n'ayez absolument besoin) d'utiliser A *, vous pouvez également jeter un œil aux comportements de pilotage . Comme il n'y a pas de planification de chemin complète par trame impliquée, elle devrait être beaucoup plus légère sur le traitement.


la source
J'utilise des comportements de pilotage (en particulier Seek) dans les cas où il n'y a pas d'obstacles entre l'agent et sa cible. Malheureusement, mon environnement contient des choses comme des couloirs sinueux, où une solution plus intelligente est nécessaire.
Gregory Avery-Weir