Faire en sorte que l'IA emprunte des chemins différents

16

J'ai un jeu 2d de haut en bas où l'IA apparaît sur les bords de la carte et court vers le centre.

J'utilise A * et un maillage de noeud pour faire le pathfinding.

En ce moment, l'IA apparaît à un point sur le bord de la carte et tous empruntent le même chemin qui est le chemin le plus court vers le centre.

Maintenant, je veux qu'ils soient plus surprenants et intéressants et empruntent des chemins différents.

Je peux immédiatement penser à deux idées pour le faire, mais je voulais savoir s'il existe d'autres façons ou de meilleures façons que les gens utilisent souvent?

  1. Lorsqu'un ennemi apparaît et génère un chemin vers le centre, augmentez temporairement le coût de tous les nœuds sur ce chemin, puis diminuez-les lentement au fil du temps. Ensuite, l'IA ennemie qui apparaîtra plus tard sera obligée de prendre un chemin plus large.

  2. L'approche ci-dessus conduira l'IA à prendre un chemin de plus en plus large et sera toujours très prévisible. J'ai donc pensé introduire également un certain nombre de nœuds d'objectif intermédiaires autour de la carte. Lorsque l'IA apparaît, ils choisissent au hasard l'un des objectifs intermédiaires et s'y dirigent d'abord avant de se diriger vers le centre de la carte. Combiner cela avec l'approche ci-dessus d'augmenter les coûts pourrait sembler plutôt bon?

Quelles approches les gens ont-ils trouvé les plus efficaces pour amener l'IA à varier les voies empruntées, à être convaincante et surprenante?

TerryB
la source

Réponses:

7

Votre deuxième option suggère une approche plus fondamentale: garantir que les ennemis approchent votre joueur de différentes directions. La question est de savoir jusqu'où doivent-ils voyager pour se déplacer autour de votre joueur? L'idéal serait un mélange de

  • générer dynamiquement des points qui entourent étroitement (c'est-à-dire suivent) la position du joueur;
  • ce que Nevermind a suggéré en termes de randomisation des chemins vers ces points environnants, à un degré plus ou moins grand.

De cette façon, vous pouvez vous assurer que les IA ne prendront pas de longs détours inutiles juste pour obtenir une variation de chemin réaliste lors de la convergence sur le joueur.

La diffusion collaborative fait ce que vous voulez implicitement dans le cadre de l'algorithme. Mais ce n'est pas anodin à mettre en œuvre.

Ingénieur
la source
La diffusion en collaboration n'est qu'une inondation avec une certaine pondération. Il est trivial à mettre en œuvre, peut-être plus facile que A *. Cela nécessite simplement une vision différente de votre monde - un changement conceptuel non trivial, peut-être, mais aucun problème de mise en œuvre.
Il n'est toujours pas trivial à mettre en œuvre car il s'agit d'un point de vue non standard en termes de gestion des entités d'IA :)
Ingénieur
Merci Nick. Je pense que la mise en place de certains waypoints qui entourent le lecteur au centre de la carte sera la principale voie à suivre. Je ne sais pas à ce stade si elles seront générées dynamiquement ou si un artisanat sera impliqué pour chaque niveau pour ma situation particulière. Merci encore!
TerryB
12

Comme première idée, essayez d'ajouter une petite valeur aléatoire au poids de chaque nœud lors de la recherche de chemin. De cette façon, chaque agent recherchera un chemin dans un environnement légèrement différent. Je ne sais pas si cela fonctionnera dans votre cas, mais cela devrait être vraiment facile à essayer.

Ça ne fait rien
la source
Les ennemis finiront par courir comme des poulets, et dans un environnement à grain fin, les chemins ne seront pas si différents de toute façon. C'est un bon ajout à d'autres solutions, mais pas une solution en soi
Coyote
@Coyote Cela dépend beaucoup de la structure du maillage de navigation et des relations entre les poids des nœuds, les vitesses et les composants aléatoires. C'est pourquoi j'ai encadré la réponse comme une suggestion à essayer, pas comme une réponse définitive.
Nevermind
En effet :) je suis généralement fan d'entropie. Mais le résultat final est rarement excellent.
Coyote
Je crois en fait que la réponse de Nick Wiggill est bien meilleure que la mienne. Mais d'une manière ou d'une autre, il n'obtient pas les votes positifs qu'il mérite.
Nevermind
Il est ... Mais le vôtre est le premier et le plus simple ... nous pourrions essayer de voter contre: P
Coyote
3

J'aime la réponse de Nevermind , cependant, étant donné la limitation décrite dans les commentaires, voici ce que j'essaierais:

  1. L'algorithme pour une seule unité au centre, enregistre la distance totale parcourue.
  2. Pour chaque unité suivante, allouez-lui une distance aléatoire et petite plus longue que celle-ci.
  3. Tout en faisant le A * pour chaque unité, ajoutez un poids supplémentaire en fonction de votre distance et de la distance que vous souhaitez parcourir. Ce serait probablement quelque chose comme ça (distanceToGoal) + Max(0, desiredDistance - distanceTravelled)).

Cela inciterait les unités à aller plus loin, ce qui est probablement un chemin différent, ce qui les amènerait éventuellement à prendre des chemins différents.

Vous pouvez également l'ajouter à votre huerestic de départ pour chaque unité, mais la plage aléatoire devrait probablement être un peu plus grande.

Jonathan Dickinson
la source
2

Comme l'a souligné Nick Wiggill, l'approche la plus simple serait d'obtenir un cercle entourant l'objectif.

  • attribuer au hasard un point proche de ce cercle comme waypoint.
  • éliminer tous les chemins dans le cercle du chemin initial (ou augmenter considérablement la valeur de ces points)
  • puis à partir de ce point de cheminement, obtenez le chemin vers l'objectif.

La partie importante est d'éliminer tous les chemins dans le cercle pour le waypoint d'origine comme vous vous retrouveriez probablement avec des ennemis traversant le cercle pour arriver à leur waypoint initial.

De là, vous pouvez obtenir n'importe quelle variante en jouant avec plusieurs valeurs en ajoutant des points de cheminement secondaires dans le cercle proche de celui initial, etc.

Coyote
la source
si votre carte le supporte, trouvez des endroits `` intéressants '' autour de ce cercle (portes, couverture, arbres, rochers, bâtiments; n'importe quel nœud avec un avantage tactique) et demandez à vos ennemis de se diriger d'abord vers ces emplacements s'ils sont disponibles et ne sortent que dans l'ouvert s'il le faut. Cela semblera beaucoup plus intelligent que de simplement frapper un endroit aléatoire sur le bord du cercle.
DampeS8N
Merci Coyote, oui je vais probablement aller avec la solution Nicks et comme suggéré par DampeS8N certains endroits clés d'intérêt comme waypoints. Pour éviter le problème de l'IA "traversant le cercle", je vais simplement augmenter considérablement le coût des nœuds dans le cercle, donc A * devrait contourner ce dernier avec un peu de
chance
2

Votre problème ici est essentiellement que A * est un algorithme pour trouver l'itinéraire le plus rapide vers une cible. Si tel est votre critère principal pour une «bonne» voie, il n'est pas surprenant que tous vos acteurs prennent les mêmes décisions.

Ce que vous devez faire est de modifier vos critères de qualité pour le chemin, de sorte que «le plus court est le meilleur» n'est pas le seul facteur. L'élément de hasard est clé à cet égard, mais pas tellement qu'il nuit à l'intelligence de recherche de chemin (c'est-à-dire que les acteurs empruntent stupidement des chemins détournés vers la cible).

Un * pathfinding est intrinsèquement naïf, car il suppose généralement que l'acteur a une parfaite connaissance de l'itinéraire complet avant de commencer. Cela va toujours sembler irréaliste. La solution a suggéré que les objectifs intermédiaires choisis soient à un pas de cela - l'IA essaie de se rapprocher de la cible, mais essaie seulement de naviguer dans de petites sections à la fois (c'est analogue à la vraie vie où vous ne pouvez naviguer que jusqu'à comme vous pouvez le voir, et que vous parcourez plus du chemin, vous pouvez voir plus loin).

Je recommanderais peut-être une façon plus simple de voir les choses. Lorsque vous recherchez un chemin, ne vous contentez pas de conserver un seul meilleur chemin que j'ai trouvé jusqu'à présent. À la place, récupérez un ensemble des 5 ou 10 meilleurs chemins. Utilisez un seuil pour éliminer les valeurs aberrantes évidentes. Par exemple, si le meilleur chemin traverse 20u pour se rendre à la cible, le meilleur suivant traverse 21u et le suivant passe ensuite 50u. Définissez un seuil de 20% plus grand que le meilleur chemin, et jetez donc le chemin 50u car il est stupidement plus long. Vous avez maintenant le choix entre plusieurs chemins, et en sélectionnant au hasard dans cet ensemble de chemins, vos acteurs prendront des décisions différentes.

Cependant, vous n'obtiendrez pas ce type d'informations avec la recherche A * standard, donc je pense que vous devrez modifier l'algorithme ou utiliser autre chose pour rassembler l'ensemble des chemins possibles.

MrCranky
la source
1

Si vous avez un petit nombre d'ennemis récurrents (ou types d'ennemis), vous pouvez essayer de leur donner des personnalités qui affectent leurs mouvements. Ils ne doivent pas être de grandes choses, juste des choses qui surgissent de temps en temps. Les fantômes de Pac-Man en sont un bon exemple. Faites diviser votre A * en plusieurs objectifs intermédiaires. Peut-être qu'un ennemi est vraiment stupide et se perd facilement, se dirigeant dans une direction aléatoire tous les trois nœuds (autre que directement en arrière). Sois créatif.

Un gars
la source