Trouver efficacement de nombreux ennemis en masse autour des obstacles

20

Je travaille à essayer d'améliorer le repérage des ennemis de mon jeu. À l'heure actuelle, ils se déplacent essentiellement vers la position exacte du joueur en calculant l'angle entre eux et les joueurs et en se déplaçant dans cette direction. J'ai également un algorithme de flocage qui empêche les ennemis de s'empiler les uns sur les autres, ils se formeront donc en groupes plutôt que de se couper les uns les autres.

Cependant, maintenant que j'ai ajouté une carte à base de tuiles, j'ai besoin que les ennemis puissent également contourner les obstacles et les murs par exemple. J'ai d'abord essayé d'ajouter une valeur de séparation aux tuiles "non accessibles à pied" afin que l'algorithme de flocage considère les murs et les obstacles comme des objets à éloigner. Je dois encore déterminer si cela est faisable ou non, car mon test initial a montré que les ennemis frappaient un "mur" invisible où il n'y avait pas de tuiles non accessibles à pied, mais pour une raison quelconque, ils le frappaient et commençaient à briller.

Je me demandais si les performances pouvaient être trop lourdes pour calculer un chemin vers le joueur en utilisant A *, puis utiliser l'algorithme de flocage pour éviter l'agglutination. À l'origine, mon jeu allait être un jeu de tir basé sur les vagues, mais j'ai plutôt décidé de le faire en fonction du niveau dans la veine de Hotline Miami, il est donc probable que j'aurai moins d'ennemis, avec la horde occasionnelle, et je ferai juste les plus forts.

Est-ce une solution viable? J'utilise Java avec Slick2D comme moteur de jeu. Ou existe-t-il une meilleure solution / algorithme qui s'attaque à ces deux problèmes?

Darin Beaudreau
la source
7
Comme je l'ai décrit dans l'édition, "est-ce trop lourd" est une question à poser à votre profileur, car cela dépendra de votre implémentation, du matériel cible, du budget de performance et du contexte de votre jeu - toutes les choses que vous et votre profileur connaissez intimement, mais pas les étrangers sur Internet. Si vous voulez que le traçage des troupeaux soit efficace, nous pouvons suggérer des stratégies pour vous aider, mais seul votre propre profilage peut répondre à ce qui est assez efficace pour vos besoins. Si vous profilez et identifiez un problème de performances spécifique, nous pouvons également vous aider à trouver comment résoudre ce problème.
DMGregory
1
La façon dont vous les implémentez affecte les performances. Par exemple, exécuter uniquement A * sur les leaders et compter sur le flocage pour les suiveurs.
Pikalek
Si votre jeu est principalement basé sur la lutte contre ces ennemis, l'algorithme que vous utiliserez aura un impact énorme sur la sensation du jeu. Vous devriez donc essayer différentes approches, par exemple, avez-vous l'impression que les ennemis connaissent parfaitement le niveau et la position du joueur à tout moment et qu'ils le suivent comme dirigé par une IA omnisciente? - d'autres approches pourraient être de laisser les ennemis courir dans la direction générale où le joueur a fait du bruit et uniquement en ligne de vue directe courir vers lui, ou crier et informer les autres ennemis où le joueur est ...
Falco
@Falco Étant donné que le jeu n'est plus basé sur les vagues, et sera basé sur le niveau, et puisque les ennemis sont des zombies ... J'envisageais de le faire de sorte que vous deviez être vu ou faire du bruit pour qu'ils vous trouvent. Donc, si vous utilisez une arme bruyante? Il émet un son dans une portée et tous les ennemis dans la trajectoire de la portée vers l'emplacement du son émis, et se dirigera ensuite de manière aléatoire autour de cette zone.
Darin Beaudreau

Réponses:

49

Cela ressemble à un cas d'utilisation pour les champs de flux.

Dans cette technique, vous effectuez une seule requête de recherche de chemin vers l'extérieur à partir de vos objets joueur, en marquant chaque cellule que vous rencontrez avec la cellule à partir de laquelle vous l'avez atteinte.

Si toutes vos tuiles / arêtes ont un coût de traversée égal, vous pouvez utiliser une simple recherche en largeur pour cela. Sinon, l'algorithme de Dijkstra (comme A * sans objectif / heuristique) fonctionne.

Cela crée un champ de flux: une table de recherche qui associe chaque cellule à l'étape suivante vers l'objet joueur le plus proche de cette position.

Désormais, vos ennemis peuvent chacun rechercher leur position actuelle dans le champ de flux pour trouver la prochaine étape dans leur chemin le plus court évitant les obstacles vers l'objet joueur le plus proche, sans chacun faire leur propre requête de recherche de chemin.

Cela évolue de mieux en mieux avec le nombre d'ennemis que vous avez dans votre troupeau. Pour un seul ennemi, c'est plus cher que A * car il recherche sur toute la carte (bien que vous puissiez effectuer une sortie anticipée une fois que vous avez atteint tous les agents d'orientation). Mais au fur et à mesure que vous ajoutez des ennemis, ils partagent de plus en plus le coût de la recherche de chemin en calculant les segments de chemin partagés une fois plutôt que plusieurs fois. Vous bénéficiez également d'un avantage du fait que les BFS / Dijkdtra sont plus simples que A *, et généralement moins chers à évaluer par cellule inspectée.

Exactement là où le seuil de rentabilité frappe, de l'individu A * étant moins cher, à A * avec la mémorisation étant moins cher (où vous réutilisez certains des résultats d'une ancienne requête de recherche de chemin pour accélérer la suivante), pour que les champs de flux soient moins cher, dépendra de votre implémentation, du nombre d'agents et de la taille de votre carte. Mais si jamais vous prévoyez un grand essaim d'ennemis approchant de plusieurs directions dans une zone confinée, un champ d'écoulement sera presque certainement moins cher que A * itéré.

À titre d'exemple extrême, vous pouvez voir une vidéo ici avec 20 000 agents, tous simultanément à la recherche de chemins sur une grille relativement petite .

DMGregory
la source
Cette technique semble vraiment soignée. Je vérifierai.
Darin Beaudreau
15
Il est possible d'utiliser un algorithme hybride qui construit un champ de flux partiel sans rechercher plus sur la carte que ne le feraient des appels répétés à A *, et sans jamais chercher deux fois la même position. L'idée de base est de choisir un ennemi arbitraire et de lancer une recherche A * du joueur vers cet ennemi, en marquant les cellules au fur et à mesure que vous les rencontrez, comme dans la génération de champ de flux normal. Une fois que la recherche a trouvé cet ennemi, choisissez un autre ennemi (que vous n'avez pas encore trouvé) comme cible, triez à nouveau l'ensemble ouvert en fonction de la nouvelle heuristique et continuez la recherche. Arrêtez-vous lorsque vous avez trouvé tous les ennemis.
Ilmari Karonen
1
Et éviter les collisions? C'est (un peu) mentionné dans l'OP (en évitant l'écrêtage lorsqu'ils atteignent le joueur). Il me semble que vous devrez réexécuter les djikstras complets chaque fois que quelque chose bouge (ou ajouter une logique supplémentaire)
Mars
2
@Mars Le PO parle de flocage, donc je suppose que tous les individus peuvent se déplacer à la même vitesse; les seuls endroits où les collisions seront un problème sont les goulots d'étranglement, qui nécessitent qu'une partie du troupeau s'arrête et attende. Cependant, il n'a pas vraiment besoin de changer la recherche de chemin - une simple file d'attente fonctionnerait probablement assez bien dans la plupart des cas, et une certaine polarisation de chemin (une sélection pseudo-aléatoire de chemins alternatifs avec des coûts similaires) fonctionnera pour produire un troupeau plus naturel. des flux qui évitent également à tout le troupeau d'essayer de passer par un écart particulier d'une seule tuile :)
Luaan
3
@Luaan Dans un jeu basé sur des tuiles, vous seriez surpris de la fréquence des collisions. Personnellement, je trouve que l'option "file d'attente" n'est pas optimale. De plus, si les unités ne peuvent pas se traverser, vous devrez recalculer le moment où les unités commenceront à atteindre leur position finale et un tas d'autres cas de bord. Flocage est difficile;)
Mars
8

Un * n'est pas très performant. J'aborderais cette situation en faisant varier les algorithmes. Faites A * de temps en temps et entre les deux, vérifiez si la prochaine étape est libre de monter ou si vous avez besoin d'évasion.

Par exemple, suivez la distance des joueurs par rapport à l'emplacement cible A *, si elle est supérieure à un seuil, recalculez un * puis effectuez simplement des mouvements de mise à jour. La plupart des jeux utilisent une combinaison de points de cheminement, par exemple une grille simplifiée pour la recherche de chemin et une logique qui gère le mouvement entre les points de cheminement avec des algorithmes de pilotage d'évasion utilisant des raycasts. Les agents tentent de courir vers un waypoint éloigné en manoeuvrant autour des obstacles à leur proximité est la meilleure approche à mon avis.

Il est préférable de travailler avec des machines à états finis ici et de lire le livre "Programming Game AI By Example" de Mat Buckland. Le livre propose des techniques éprouvées pour votre problème et détaille les mathématiques requises. Le code source du livre est disponible sur le Web; le livre est en C ++ mais certaines traductions (y compris Java) sont disponibles.

D3d_dev
la source
2
Avec une approche A * rarement mise à jour, il peut être utile d'échelonner vos mises à jour, en maintenant un budget pour le nombre d'ennemis autorisés à se réorienter sur une seule image. De cette façon, vous pouvez limiter votre coût maximal de recherche de chemin par image et gérer de manière plus robuste de nombreux chemins AI en amortissant leur coût total sur plusieurs images. Une IA utilisant un chemin périmé pour une image ou deux lorsque le budget de l'image a été dépassé, ou retombant sur un calcul mort s'il est proche, ne sera généralement pas perturbatrice.
DMGregory
2
Indiquant probablement l'évidence ici, mais si vous ne mettez à jour que certains de vos chemins dans un cadre donné, vous voudrez peut-être un système de priorité basé sur la distance au joueur. Il est probablement plus important pour les ennemis proches du joueur de mettre à jour leurs trajectoires, alors qu'il est probablement correct pour les ennemis éloignés d'utiliser un chemin périmé.
AC
4

Non seulement c'est faisable, je crois que cela a été fait dans un jeu commercial dans les années 90 - BattleZone (1998).

Ce jeu avait des unités 3D avec un mouvement gratuit sans tuiles et une construction de base à base de tuiles.

Voici comment cela semblait fonctionner:

Tout d'abord, A * ou quelque chose de similaire (probablement une variation de A * avec des limites strictes sur la durée d'un chemin, il ne prend donc jamais trop de ressources à exécuter mais ne trouve pas toujours un chemin jusqu'à la destination) serait utilisé pour trouver un chemin pour un hovertank pour arriver à sa destination sans se coincer dans des obstacles à base de tuiles.

Ensuite, le char volerait autour de l'espace jusqu'à ce qu'il soit attiré vers le centre d'une tuile voisine sur son chemin, et repoussé par des obstacles, d'autres chars à proximité, etc.

Robyn
la source
1
Alors, quel est un bon moyen de gérer le suivi du chemin, mais pas exactement? Si j'autorise les virages kiddy, je dois pouvoir empêcher les ennemis d'entrer en collision avec le coin d'un obstacle. Dois-je conserver le comportement de flocage pour les ennemis et les obstacles et ajouter A * pour faire face à ces situations?
Darin Beaudreau