Je suis tombé sur du matériel intéressant sur l'intelligence artificielle dans les jeux. Avec une explication des éléments de base de l'IA à l'aide d'exemples simples, et à l'intérieur se trouvent de nombreux outils et méthodes utiles pour son développement et sa conception pratiques. Comment, où et quand les utiliser est également indiqué.
La plupart des exemples sont écrits en pseudocode, aucune connaissance avancée en programmation n'est donc requise. Sous la coupe se trouvent 35 feuilles de texte avec des images et des gifs, alors préparez-vous.
MISE À JOUR. Je m'excuse, mais j'ai déjà fait ma propre traduction de cet article sur Habré . Vous pouvez lire sa version , mais pour une raison quelconque, l'article m'a échappé (j'ai utilisé la recherche, mais quelque chose s'est mal passé). Et comme j'écris sur un blog dédié au développement de jeux, j'ai décidé de laisser ma version de la traduction aux abonnés (certains points sont formatés différemment, certains ont été délibérément omis sur les conseils des développeurs).
Qu'est-ce que l'IA?
L'IA du jeu se concentre sur les actions qu'un objet doit effectuer en fonction des conditions dans lesquelles il se trouve. C'est ce qu'on appelle communément la gestion des « agents intelligents », où un agent est un personnage de joueur, un véhicule, un robot, ou parfois quelque chose de plus abstrait : un groupe entier d'entités ou même une civilisation. Dans chaque cas, c'est une chose qui doit voir son environnement, prendre des décisions basées sur celui-ci et agir en conséquence. C’est ce qu’on appelle le cycle Sens/Penser/Agir :
- Sens : L'agent trouve ou reçoit des informations sur des éléments de son environnement susceptibles d'influencer son comportement (menaces à proximité, objets à collecter, lieux intéressants à explorer).
- Réfléchissez : l'agent décide comment réagir (il considère s'il est suffisamment sûr pour collecter des objets ou s'il doit d'abord se battre/se cacher).
- Agir : l'agent effectue des actions pour mettre en œuvre la décision précédente (commence à se déplacer vers l'ennemi ou l'objet).
- ...maintenant, la situation a changé en raison des actions des personnages, donc le cycle se répète avec de nouvelles données.
L’IA a tendance à se concentrer sur la partie Sense de la boucle. Par exemple, les voitures autonomes prennent des photos de la route, les combinent avec des données radar et lidar et les interprètent. Cela se fait généralement par l'apprentissage automatique, qui traite les données entrantes et leur donne un sens, en extrayant des informations sémantiques telles que « il y a une autre voiture à 20 mètres devant vous ». Ce sont ce qu’on appelle les problèmes de classification.
Les jeux n’ont pas besoin d’un système complexe pour extraire les informations puisque la plupart des données en font déjà partie intégrante. Il n'est pas nécessaire d'exécuter des algorithmes de reconnaissance d'images pour déterminer s'il y a un ennemi devant vous : le jeu le sait déjà et intègre les informations directement dans le processus de prise de décision. Par conséquent, la partie Ressentir du cycle est souvent beaucoup plus simple que la partie Réfléchir et Agir.
Limites de l'IA du jeu
L’IA présente un certain nombre de limites qui doivent être respectées :
- L’IA n’a pas besoin d’être entraînée à l’avance, comme s’il s’agissait d’un algorithme d’apprentissage automatique. Cela n’a aucun sens d’écrire un réseau de neurones pendant le développement pour surveiller des dizaines de milliers de joueurs et apprendre la meilleure façon de jouer contre eux. Pourquoi? Parce que le jeu n’est pas sorti et qu’il n’y a pas de joueurs.
- Le jeu doit être amusant et stimulant, les agents ne doivent donc pas trouver la meilleure approche contre les gens.
- Les agents doivent avoir l’air réalistes pour que les joueurs aient l’impression de jouer contre de vraies personnes. Le programme AlphaGo a surpassé les humains, mais les étapes choisies étaient très éloignées de la compréhension traditionnelle du jeu. Si le jeu simule un adversaire humain, ce sentiment ne devrait pas exister. L’algorithme doit être modifié afin qu’il prenne des décisions plausibles plutôt qu’idéales.
- L'IA doit fonctionner en temps réel. Cela signifie que l’algorithme ne peut pas monopoliser l’utilisation du processeur pendant de longues périodes pour prendre des décisions. Même 10 millisecondes, c'est trop long, car la plupart des jeux n'ont besoin que de 16 à 33 millisecondes pour effectuer tout le traitement et passer à l'image graphique suivante.
- Idéalement, au moins une partie du système devrait être basée sur les données, afin que les non-codeurs puissent apporter des modifications et que les ajustements puissent se produire plus rapidement.
Examinons les approches d'IA qui couvrent l'ensemble du cycle Sens/Penser/Agir.
Prendre des décisions de base
Commençons par le jeu le plus simple : Pong. Objectif : déplacer la raquette pour que la balle rebondisse dessus plutôt que de passer devant. C'est comme le tennis, où l'on perd si l'on ne frappe pas la balle. Ici, l'IA a une tâche relativement simple : décider dans quelle direction déplacer la plate-forme.
Expressions conditionnelles
Pour l’IA de Pong, la solution la plus évidente est de toujours essayer de placer la plateforme sous le ballon.
Un algorithme simple pour cela, écrit en pseudocode :
chaque image/mise à jour pendant que le jeu est en cours d'exécution :
si la balle est à gauche de la raquette :
déplacer la pagaie vers la gauche
sinon si la balle est à droite de la raquette :
déplacer la pagaie vers la droite
Si la plate-forme se déplace à la vitesse de la balle, alors c'est l'algorithme idéal pour l'IA de Pong. Il n'est pas nécessaire de compliquer quoi que ce soit s'il n'y a pas autant de données et d'actions possibles pour l'agent.
Cette approche est si simple que l’ensemble du cycle Sens/Penser/Agir est à peine perceptible. Mais c'est là :
- La partie Sense est composée de deux instructions if. Le jeu sait où se trouve le ballon et où se trouve la plate-forme, donc l'IA se tourne vers lui pour obtenir cette information.
- La partie Think est également incluse dans les deux instructions if. Ils incarnent deux solutions qui, dans ce cas, s’excluent mutuellement. En conséquence, l'une des trois actions est sélectionnée : déplacer la plate-forme vers la gauche, la déplacer vers la droite ou ne rien faire si elle est déjà correctement positionnée.
- La partie Act se trouve dans les instructions Move Paddle Left et Move Paddle Right. Selon la conception du jeu, ils peuvent déplacer la plateforme instantanément ou à une vitesse spécifique.
De telles approches sont appelées réactives - il existe un ensemble simple de règles (dans ce cas, des instructions if dans le code) qui réagissent à l'état actuel du monde et prennent des mesures.
Arbre de décision
L’exemple de Pong est en fait équivalent à un concept formel d’IA appelé arbre de décision. L’algorithme le parcourt pour atteindre une « feuille » : une décision sur l’action à entreprendre.
Faisons un schéma fonctionnel de l'arbre de décision pour l'algorithme de notre plateforme :
Chaque partie de l’arbre est appelée un nœud – l’IA utilise la théorie des graphes pour décrire ces structures. Il existe deux types de nœuds :
- Nœuds de décision : choix entre deux alternatives en fonction du test d'une condition, où chaque alternative est représentée comme un nœud distinct.
- Nœuds de fin : l'action à effectuer qui représente la décision finale.
L'algorithme part du premier nœud (la « racine » de l'arbre). Soit il décide vers quel nœud enfant accéder, soit il exécute l'action stockée dans le nœud et quitte.
Quel est l'avantage d'avoir un arbre de décision faisant le même travail que les instructions if de la section précédente ? Il existe ici un système général où chaque décision n’a qu’une seule condition et deux résultats possibles. Cela permet au développeur de créer une IA à partir de données représentant des décisions dans un arbre sans avoir à la coder en dur. Présentons-le sous forme de tableau :
Côté code, vous obtiendrez un système de lecture de chaînes. Créez un nœud pour chacun d'eux, connectez la logique de décision basée sur la deuxième colonne et les nœuds enfants basés sur les troisième et quatrième colonnes. Vous devez toujours programmer les conditions et les actions, mais désormais la structure du jeu sera plus complexe. Ici, vous ajoutez des décisions et des actions supplémentaires, puis personnalisez l'intégralité de l'IA en modifiant simplement le fichier texte de définition de l'arborescence. Ensuite, vous transférez le fichier au concepteur du jeu, qui peut modifier le comportement sans recompiler le jeu ni modifier le code.
Les arbres de décision sont très utiles lorsqu'ils sont construits automatiquement à partir d'un large ensemble d'exemples (par exemple, en utilisant l'algorithme ID3). Cela en fait un outil efficace et performant pour classer les situations en fonction des données obtenues. Cependant, nous allons au-delà d’un simple système permettant aux agents de sélectionner des actions.
scénarios
Nous avons analysé un système d'arbre de décision qui utilisait des conditions et des actions pré-créées. La personne qui conçoit l’IA peut organiser l’arbre comme bon lui semble, mais elle doit quand même s’appuyer sur le codeur qui a tout programmé. Et si nous pouvions donner au concepteur les outils nécessaires pour créer ses propres conditions ou actions ?
Pour que le programmeur n'ait pas à écrire de code pour les conditions Is Ball Left Of Paddle et Is Ball Right Of Paddle, il peut créer un système dans lequel le concepteur écrira des conditions pour vérifier ces valeurs. Ensuite, les données de l’arbre de décision ressembleront à ceci :
C'est essentiellement la même chose que dans le premier tableau, mais les solutions elles-mêmes ont leur propre code, un peu comme la partie conditionnelle d'une instruction if. Du côté du code, cela se lirait dans la deuxième colonne pour les nœuds de décision, mais au lieu de rechercher une condition spécifique à exécuter (Is Ball Left Of Paddle), il évalue l'expression conditionnelle et renvoie vrai ou faux en conséquence. Cela se fait à l'aide du langage de script Lua ou Angelscript. En les utilisant, un développeur peut prendre des objets dans son jeu (balle et paddle) et créer des variables qui seront disponibles dans le script (ball.position). De plus, le langage de script est plus simple que le C++. Il ne nécessite pas d’étape de compilation complète, il est donc idéal pour ajuster rapidement la logique du jeu et permet aux « non-codeurs » de créer eux-mêmes les fonctions nécessaires.
Dans l'exemple ci-dessus, le langage de script est utilisé uniquement pour évaluer l'expression conditionnelle, mais il peut également être utilisé pour des actions. Par exemple, les données Move Paddle Right pourraient devenir une instruction de script (ball.position.x += 10). Pour que l'action soit également définie dans le script, sans qu'il soit nécessaire de programmer Move Paddle Right.
Vous pouvez aller encore plus loin et écrire l’intégralité de l’arbre de décision dans un langage de script. Il s'agira d'un code sous la forme d'instructions conditionnelles codées en dur, mais elles seront situées dans des fichiers de script externes, c'est-à-dire qu'elles pourront être modifiées sans recompiler l'intégralité du programme. Vous pouvez souvent modifier le fichier de script pendant le jeu pour tester rapidement différentes réponses de l'IA.
Réponse à un événement
Les exemples ci-dessus sont parfaits pour Pong. Ils exécutent en permanence le cycle Sens/Penser/Agir et agissent en fonction de l’état le plus récent du monde. Mais dans des jeux plus complexes, vous devez réagir à des événements individuels et ne pas tout évaluer en même temps. Pong dans ce cas est déjà un mauvais exemple. Choisissons-en un autre.
Imaginez un jeu de tir où les ennemis restent immobiles jusqu'à ce qu'ils détectent le joueur, après quoi ils agissent en fonction de leur « spécialisation » : quelqu'un courra pour « se précipiter », quelqu'un attaquera de loin. Il s'agit toujours d'un système réactif de base - "si un joueur est repéré, faites quelque chose" - mais il peut être logiquement décomposé en un événement Player Seen et une Réaction (sélectionnez une réponse et exécutez-la).
Cela nous ramène au cycle Sens/Penser/Agir. Nous pouvons coder une partie Sense qui vérifiera à chaque image si l'IA voit le joueur. Sinon, rien ne se passe, mais s'il le voit, alors l'événement Player Seen est créé. Le code comportera une section distincte indiquant « lorsque l'événement Player Seen se produit, faites », où se trouve la réponse dont vous avez besoin pour répondre aux parties Réfléchir et Agir. Ainsi, vous configurerez des réactions à l'événement Player Seen : pour le personnage « précipité » - ChargeAndAttack, et pour le tireur d'élite - HideAndSnipe. Ces relations peuvent être créées dans le fichier de données pour une édition rapide sans avoir à recompiler. Le langage de script peut également être utilisé ici.
Prendre des décisions difficiles
Bien que les systèmes de réaction simples soient très puissants, il existe de nombreuses situations où ils ne suffisent pas. Parfois, vous devez prendre des décisions différentes en fonction de ce que fait actuellement l'agent, mais il est difficile d'imaginer cela comme une condition. Parfois, il y a trop de conditions pour les représenter efficacement dans un arbre de décision ou un script. Parfois, vous devez évaluer à l’avance comment la situation va changer avant de décider de la prochaine étape. Des approches plus sophistiquées sont nécessaires pour résoudre ces problèmes.
Machine à états finis
La machine à états finis ou FSM (finite state machine) est une façon de dire que notre agent est actuellement dans l'un des nombreux états possibles et qu'il peut passer d'un état à un autre. Il existe un certain nombre de ces États, d'où leur nom. Le meilleur exemple de la vie est un feu de circulation. Il existe différentes séquences de lumières à différents endroits, mais le principe est le même : chaque état représente quelque chose (arrêt, marche, etc.). Un feu de circulation n'est que dans un seul état à un moment donné et passe de l'un à l'autre en fonction de règles simples.
C'est une histoire similaire avec les PNJ dans les jeux. Par exemple, prenons un garde avec les états suivants :
- Patrouille.
- Attaquer.
- Fuite.
Et ces conditions pour changer son état :
- Si le garde voit l'ennemi, il attaque.
- Si le garde attaque mais ne voit plus l'ennemi, il retourne en patrouille.
- Si un garde attaque mais est grièvement blessé, il s'enfuit.
Vous pouvez également écrire des instructions if avec une variable d'état gardien et diverses vérifications : y a-t-il un ennemi à proximité, quel est le niveau de santé du PNJ, etc. Ajoutons quelques états supplémentaires :
- Farniente - entre les patrouilles.
- Recherche - lorsque l'ennemi remarqué a disparu.
- Trouver de l'aide - lorsqu'un ennemi est repéré, mais qu'il est trop fort pour se battre seul.
Le choix pour chacun d'eux est limité - par exemple, le garde ne cherchera pas un ennemi caché s'il a une faible santé.
Après tout, il y a une énorme liste de « si » , Que " peut devenir trop lourd, nous devons donc formaliser une méthode qui nous permette de garder à l'esprit les états et les transitions entre les états. Pour ce faire, nous prenons en compte tous les états, et sous chaque état nous notons dans une liste toutes les transitions vers d'autres états, ainsi que les conditions qui y sont nécessaires.
Il s'agit d'un tableau de transition d'état - une manière complète de représenter le FSM. Dessinons un diagramme et obtenons un aperçu complet de la façon dont le comportement des PNJ change.
Le diagramme reflète l'essence de la prise de décision pour cet agent en fonction de la situation actuelle. De plus, chaque flèche montre une transition entre les états si la condition à côté est vraie.
À chaque mise à jour, nous vérifions l'état actuel de l'agent, parcourons la liste des transitions et si les conditions de la transition sont remplies, il accepte le nouvel état. Par exemple, chaque trame vérifie si le minuteur de 10 secondes a expiré et si c'est le cas, le gardien passe de l'état Inactif à l'état Patrouille. De la même manière, l'état d'attaque vérifie la santé de l'agent : si elle est faible, il passe alors à l'état de fuite.
Il s’agit de gérer les transitions entre les états, mais qu’en est-il du comportement associé aux états eux-mêmes ? En termes d'implémentation du comportement réel pour un état particulier, il existe généralement deux types de « hook » dans lesquels nous attribuons des actions au FSM :
- Actions que nous effectuons périodiquement pour l'état actuel.
- Les actions que nous entreprenons lors de la transition d'un état à un autre.
Exemples pour le premier type. L'état Patrouille déplacera l'agent le long de l'itinéraire de patrouille à chaque image. L'état attaquant tentera de lancer une attaque à chaque image ou transition vers un état où cela est possible.
Pour le deuxième type, considérez la transition « si l'ennemi est visible et que l'ennemi est trop fort, alors passez à l'état Trouver de l'aide. L'agent doit choisir où s'adresser pour obtenir de l'aide et stocker ces informations afin que l'état Recherche d'aide sache où aller. Une fois l’aide trouvée, l’agent retourne à l’état Attaquant. À ce stade, il voudra informer l'allié de la menace, afin que l'action NotifyFriendOfThreat puisse se produire.
Encore une fois, nous pouvons examiner ce système à travers le prisme du cycle Sens/Penser/Agir. Le sens s’incarne dans les données utilisées par la logique de transition. Pensez - transitions disponibles dans chaque état. Et l'acte est réalisé par des actions exécutées périodiquement au sein d'un état ou lors de transitions entre états.
Parfois, l’interrogation continue des conditions de transition peut s’avérer coûteuse. Par exemple, si chaque agent effectue des calculs complexes à chaque image pour déterminer s'il peut voir les ennemis et comprendre s'il peut passer de l'état Patrouille à l'état Attaquant, cela prendra beaucoup de temps CPU.
Les changements importants dans l’état du monde peuvent être considérés comme des événements qui seront traités au fur et à mesure qu’ils se produisent. Au lieu que le FSM vérifie la condition de transition « Mon agent peut-il voir le joueur ? » à chaque image, un système distinct peut être configuré pour vérifier moins fréquemment (par exemple 5 fois par seconde). Et le résultat est d'émettre Player Seen lorsque le contrôle est réussi.
Ceci est transmis au FSM, qui doit maintenant accéder à la condition de réception de l'événement Player Seen et répondre en conséquence. Le comportement qui en résulte est le même à l’exception d’un délai presque imperceptible avant de répondre. Mais les performances se sont améliorées grâce à la séparation de la partie Sense en une partie distincte du programme.
Machine à états finis hiérarchique
Cependant, travailler avec de grands FSM n’est pas toujours pratique. Si nous voulons étendre l'état d'attaque pour séparer MeleeAttacking et RangedAttacking, nous devrons modifier les transitions de tous les autres états qui mènent à l'état d'attaque (actuel et futur).
Vous avez probablement remarqué que dans notre exemple, il y a beaucoup de transitions en double. La plupart des transitions à l'état Inactif sont identiques aux transitions à l'état Patrouille. Ce serait bien de ne pas se répéter, surtout si nous ajoutons d'autres états similaires. Il est logique de regrouper la marche au ralenti et les patrouilles sous l'étiquette générale de « non-combat », où il n'existe qu'un seul ensemble commun de transitions vers des états de combat. Si nous considérons cette étiquette comme un état, alors la marche au ralenti et la patrouille deviennent des sous-états. Un exemple d'utilisation d'une table de transition distincte pour un nouveau sous-état hors combat :
Principaux états :
Statut hors combat :
Et sous forme de schéma :
C'est le même système, mais avec un nouvel état de non-combat qui inclut la marche au ralenti et la patrouille. Avec chaque état contenant un FSM avec des sous-états (et ces sous-états, à leur tour, contenant leurs propres FSM - et ainsi de suite aussi longtemps que vous en avez besoin), nous obtenons une machine à états finis hiérarchique ou HFSM (machine à états finis hiérarchique). En regroupant les états de non-combat, nous avons éliminé un certain nombre de transitions redondantes. Nous pouvons faire de même pour tout nouvel état ayant des transitions communes. Par exemple, si à l’avenir nous étendons l’état d’attaque aux états d’attaque de mêlée et d’attaque de missiles, ce seront des sous-états qui feront la transition entre eux en fonction de la distance par rapport à l’ennemi et de la disponibilité des munitions. En conséquence, les comportements et sous-comportements complexes peuvent être représentés avec un minimum de transitions en double.
Arbre de comportement
Avec HFSM, des combinaisons complexes de comportements sont créées de manière simple. Il existe cependant une légère difficulté : la prise de décision sous la forme de règles transitoires est étroitement liée à l’état actuel. Et dans de nombreux jeux, c'est exactement ce dont nous avons besoin. Et une utilisation prudente de la hiérarchie des états peut réduire le nombre de répétitions de transition. Mais parfois, vous avez besoin de règles qui fonctionnent quel que soit l’État dans lequel vous vous trouvez ou qui s’appliquent dans presque tous les États. Par exemple, si la santé d'un agent tombe à 25 %, vous souhaiterez qu'il s'enfuie, qu'il soit au combat, inactif ou en train de parler - vous devrez ajouter cette condition à chaque état. Et si votre concepteur souhaite ultérieurement modifier le seuil de santé faible de 25 % à 10 %, il faudra alors refaire cette opération.
Idéalement, cette situation nécessite un système dans lequel les décisions sur « dans quel état se trouver » sont prises en dehors des États eux-mêmes, afin d'apporter des changements uniquement en un seul endroit et de ne pas toucher aux conditions de transition. Des arbres de comportement apparaissent ici.
Il existe plusieurs façons de les mettre en œuvre, mais l'essence est à peu près la même pour toutes et s'apparente à un arbre de décision : l'algorithme commence par un nœud « racine » et l'arbre contient des nœuds qui représentent soit des décisions, soit des actions. Il existe cependant quelques différences clés :
- Les nœuds renvoient désormais l'une des trois valeurs suivantes : Réussite (si la tâche est terminée), Échec (s'il ne peut pas être démarré) ou En cours d'exécution (s'il est toujours en cours d'exécution et qu'il n'y a pas de résultat final).
- Il n’y a plus de nœuds de décision permettant de choisir entre deux alternatives. Au lieu de cela, ce sont des nœuds Decorator, qui ont un nœud enfant. S'ils réussissent, ils exécutent leur seul nœud enfant.
- Les nœuds qui effectuent des actions renvoient une valeur Running pour représenter les actions en cours d'exécution.
Ce petit ensemble de nœuds peut être combiné pour créer un grand nombre de comportements complexes. Imaginons la garde HFSM de l'exemple précédent comme un arbre de comportement :
Avec cette structure, il ne devrait pas y avoir de transition évidente entre les états Au ralenti/Patrouille et l'Attaque ou tout autre état. Si un ennemi est visible et que la santé du personnage est faible, l'exécution s'arrêtera au nœud de fuite, quel que soit le nœud qu'il exécutait auparavant : patrouille, ralenti, attaque ou tout autre nœud.
Les arbres de comportement sont complexes : il existe de nombreuses façons de les composer, et trouver la bonne combinaison de décorateurs et de nœuds composés peut s'avérer difficile. Il y a aussi des questions sur la fréquence à laquelle il faut vérifier l'arbre : voulons-nous en parcourir chaque partie ou seulement lorsqu'une des conditions a changé ? Comment stockons-nous l'état relatif aux nœuds - comment savoir si nous sommes restés inactifs pendant 10 secondes, ou comment savoir quels nœuds s'exécutaient la dernière fois afin de pouvoir traiter la séquence correctement ?
C'est pourquoi il existe de nombreuses implémentations. Par exemple, certains systèmes ont remplacé les nœuds décorateurs par des décorateurs en ligne. Ils réévaluent l'arborescence lorsque les conditions du décorateur changent, aident à rejoindre les nœuds et fournissent des mises à jour périodiques.
Système basé sur un utilitaire
Certains jeux ont de nombreuses mécaniques différentes. Il est souhaitable qu’ils bénéficient de tous les bénéfices de règles de transition simples et générales, mais pas nécessairement sous la forme d’un arbre de comportement complet. Au lieu d’avoir un ensemble clair de choix ou un arbre d’actions possibles, il est plus facile d’examiner toutes les actions et de choisir celle qui est la plus appropriée pour le moment.
Le système basé sur l’utilitaire vous aidera précisément à cela. Il s’agit d’un système dans lequel l’agent dispose d’une variété d’actions et choisit celles qu’il effectue en fonction de l’utilité relative de chacune. Où l’utilité est une mesure arbitraire de l’importance ou de la désirabilité pour l’agent d’effectuer cette action.
L'utilité calculée d'une action en fonction de l'état et de l'environnement actuels, l'agent peut vérifier et sélectionner l'autre état le plus approprié à tout moment. Ceci est similaire au FSM, sauf que les transitions sont déterminées par une estimation pour chaque état potentiel, y compris l'état actuel. Attention, nous choisissons l'action la plus utile pour passer à autre chose (ou rester si nous l'avons déjà réalisée). Pour plus de variété, cela pourrait être une sélection équilibrée mais aléatoire à partir d’une petite liste.
Le système attribue une plage arbitraire de valeurs d'utilité, par exemple de 0 (totalement indésirable) à 100 (totalement souhaitable). Chaque action possède un certain nombre de paramètres qui affectent le calcul de cette valeur. Revenant à notre exemple de tuteur :
Les transitions entre les actions sont ambiguës : n’importe quel état peut en suivre un autre. Les priorités d'action se trouvent dans les valeurs d'utilité renvoyées. Si un ennemi est visible, que cet ennemi est fort et que la santé du personnage est faible, alors Fleeing et FindingHelp renverront des valeurs élevées non nulles. Dans ce cas, FindingHelp sera toujours plus élevé. De même, les activités hors combat ne rapportent jamais plus de 50, elles seront donc toujours inférieures aux activités de combat. Vous devez en tenir compte lors de la création d’actions et du calcul de leur utilité.
Dans notre exemple, les actions renvoient soit une valeur constante fixe, soit l'une des deux valeurs fixes. Un système plus réaliste renverrait une estimation à partir d’une plage continue de valeurs. Par exemple, l'action Fuir renvoie des valeurs utilitaires plus élevées si la santé de l'agent est faible, et l'action Attaquer renvoie des valeurs utilitaires plus faibles si l'ennemi est trop fort. De ce fait, l'action Fuir a priorité sur l'Attaque dans toute situation où l'agent estime qu'il n'a pas assez de santé pour vaincre l'ennemi. Cela permet de hiérarchiser les actions en fonction d'un certain nombre de critères, ce qui rend cette approche plus flexible et variable qu'un arbre comportemental ou un FSM.
Chaque action comporte de nombreuses conditions pour le calcul du programme. Ils peuvent être écrits dans un langage de script ou sous forme d’une série de formules mathématiques. Les Sims, qui simule la routine quotidienne d'un personnage, ajoute une couche de calcul supplémentaire : l'agent reçoit une série de « motivations » qui influencent les notes d'utilité. Si un personnage a faim, il aura encore plus faim avec le temps et la valeur utilitaire de l'action EatFood augmentera jusqu'à ce que le personnage l'exécute, réduisant ainsi le niveau de faim et ramenant la valeur EatFood à zéro.
L'idée de sélectionner des actions sur la base d'un système de notation est assez simple, donc un système basé sur l'utilitaire peut être utilisé dans le cadre des processus décisionnels de l'IA, plutôt que comme un remplacement complet de ceux-ci. L'arbre de décision peut demander une évaluation d'utilité de deux nœuds enfants et sélectionner celui qui est le plus élevé. De même, un arbre de comportement peut avoir un nœud utilitaire composite pour évaluer l'utilité des actions afin de décider quel enfant exécuter.
Mouvement et navigation
Dans les exemples précédents, nous avions une plate-forme que nous déplacions à gauche ou à droite et un garde qui patrouillait ou attaquait. Mais comment gérer exactement les mouvements des agents sur une période donnée ? Comment définir la vitesse, comment éviter les obstacles et comment planifier un itinéraire lorsqu'il est plus difficile d'atteindre une destination que de simplement se déplacer en ligne droite ? Regardons ça.
Gestion
Au stade initial, nous supposerons que chaque agent a une valeur de vitesse, qui inclut la vitesse à laquelle il se déplace et dans quelle direction. Elle peut se mesurer en mètres par seconde, en kilomètres par heure, en pixels par seconde, etc. En rappelant la boucle Sense/Penser/Act, on peut imaginer que la partie Penser sélectionne une vitesse, et la partie Agir applique cette vitesse à l'agent. Généralement, les jeux disposent d'un système physique qui effectue cette tâche à votre place, en apprenant la valeur de vitesse de chaque objet et en l'ajustant. Par conséquent, vous pouvez laisser à l'IA une seule tâche : décider de la vitesse que l'agent doit avoir. Si vous savez où doit se trouver l'agent, vous devez le déplacer dans la bonne direction à une vitesse définie. Une équation très triviale :
voyage_désir = position_destination – position_agent
Imaginez un monde en 2D. L'agent se trouve au point (-2,-2), la destination est quelque part au nord-est au point (30, 20) et le chemin requis pour que l'agent s'y rende est (32, 22). Disons que ces positions sont mesurées en mètres - si nous prenons la vitesse de l'agent à 5 mètres par seconde, alors nous mettrons à l'échelle notre vecteur de déplacement et obtiendrons une vitesse d'environ (4.12, 2.83). Avec ces paramètres, l’agent arriverait à destination en près de 8 secondes.
Vous pouvez recalculer les valeurs à tout moment. Si l'agent était à mi-chemin de la cible, le mouvement ferait la moitié de la longueur, mais comme la vitesse maximale de l'agent est de 5 m/s (nous l'avons décidé ci-dessus), la vitesse sera la même. Cela fonctionne également pour les cibles en mouvement, permettant à l'agent d'effectuer de petits changements à mesure qu'elles se déplacent.
Mais nous voulons plus de variation – par exemple, augmenter lentement la vitesse pour simuler un personnage passant de la position debout à la course. La même chose peut être faite à la fin avant de s'arrêter. Ces caractéristiques sont connues sous le nom de comportements de pilotage, chacun d'entre eux portant des noms spécifiques : recherche, fuite, arrivée, etc. L'idée est que des forces d'accélération peuvent être appliquées à la vitesse de l'agent, en comparant la position et la vitesse actuelle de l'agent avec la destination dans afin d'utiliser différentes méthodes pour avancer vers l'objectif.
Chaque comportement a un objectif légèrement différent. La recherche et l'arrivée sont des moyens de déplacer un agent vers une destination. L'évitement et la séparation d'obstacles ajustent le mouvement de l'agent pour éviter les obstacles sur le chemin vers l'objectif. L’alignement et la cohésion permettent aux agents d’avancer ensemble. Un certain nombre de comportements de direction différents peuvent être additionnés pour produire un vecteur de trajectoire unique prenant en compte tous les facteurs. Un agent qui utilise les comportements Arrivée, Séparation et Évitement d'obstacles pour rester à l'écart des murs et des autres agents. Cette approche fonctionne bien dans des emplacements ouverts sans détails inutiles.
Dans des conditions plus difficiles, l'ajout de différents comportements fonctionne moins bien - par exemple, un agent peut rester coincé dans un mur en raison d'un conflit entre l'arrivée et l'évitement d'obstacles. Par conséquent, vous devez envisager des options plus complexes que la simple addition de toutes les valeurs. La façon de procéder est la suivante : au lieu d'additionner les résultats de chaque comportement, vous pouvez envisager un mouvement dans différentes directions et choisir la meilleure option.
Cependant, dans un environnement complexe caractérisé par des impasses et des choix quant à la voie à suivre, nous aurons besoin de quelque chose d’encore plus avancé.
Rechercher une voie
Les comportements de direction sont parfaits pour les déplacements simples dans une zone ouverte (terrain de football ou arène) où se rendre d'un point A à un point B est un chemin droit avec seulement des détours mineurs autour des obstacles. Pour les itinéraires complexes, nous avons besoin de pathfinding, qui est une façon d’explorer le monde et de décider d’un itinéraire à travers celui-ci.
Le plus simple est d'appliquer une grille à chaque case à côté de l'agent et d'évaluer lesquels d'entre eux sont autorisés à se déplacer. Si l'un d'eux est une destination, suivez alors l'itinéraire de chaque case à la précédente jusqu'à atteindre le début. C'est l'itinéraire. Sinon, répétez le processus avec d'autres cases à proximité jusqu'à ce que vous trouviez votre destination ou que vous manquiez de cases (ce qui signifie qu'il n'y a aucun itinéraire possible). C'est ce qui est officiellement connu sous le nom de Breadth-First Search ou BFS (breadth-first search algorithm). À chaque pas, il regarde dans toutes les directions (d’où largeur, « largeur »). L'espace de recherche est comme un front d'onde qui se déplace jusqu'à atteindre l'emplacement souhaité : l'espace de recherche s'étend à chaque étape jusqu'à ce que le point final soit inclus, après quoi il peut être retracé jusqu'au début.
En conséquence, vous recevrez une liste de carrés le long desquels l'itinéraire souhaité est établi. Il s'agit du chemin (d'où le nom de recherche de chemin) - une liste de lieux que l'agent visitera tout en suivant la destination.
Étant donné que nous connaissons la position de chaque carré du monde, nous pouvons utiliser des comportements de pilotage pour nous déplacer le long du chemin – du nœud 1 au nœud 2, puis du nœud 2 au nœud 3, et ainsi de suite. L'option la plus simple est de se diriger vers le centre de la case suivante, mais une option encore meilleure est de s'arrêter au milieu du bord entre la case actuelle et la suivante. De ce fait, l’agent sera capable de prendre des virages serrés.
L'algorithme BFS présente également des inconvénients : il explore autant de carrés dans la « mauvaise » direction que dans la « bonne » direction. C’est là qu’intervient un algorithme plus complexe appelé A* (A star). Cela fonctionne de la même manière, mais au lieu d'examiner aveuglément les carrés voisins (puis les voisins des voisins, puis les voisins des voisins des voisins, et ainsi de suite), il rassemble les nœuds dans une liste et les trie de sorte que le nœud suivant examiné soit toujours le celui qui mène au chemin le plus court. Les nœuds sont triés sur la base d'une heuristique qui prend en compte deux éléments : le « coût » d'un itinéraire hypothétique vers la case souhaitée (y compris les éventuels frais de déplacement) et une estimation de la distance entre cette case et la destination (en biaisant la recherche dans le champ de recherche). bonne direction).
Cet exemple montre que l'agent explore une case à la fois, en choisissant à chaque fois celle adjacente qui est la plus prometteuse. Le chemin résultant est le même que celui de BFS, mais moins de carrés ont été pris en compte dans le processus, ce qui a un impact important sur les performances du jeu.
Mouvement sans grille
Mais la plupart des jeux ne sont pas disposés sur une grille, et il est souvent impossible de le faire sans sacrifier le réalisme. Des compromis sont nécessaires. Quelle taille doivent avoir les carrés ? Trop grands et ils ne pourront pas représenter correctement les petits couloirs ou virages, trop petits et il y aura trop de carrés à rechercher, ce qui prendra finalement beaucoup de temps.
La première chose à comprendre est qu’un maillage nous donne un graphe de nœuds connectés. Les algorithmes A* et BFS fonctionnent réellement sur des graphiques et ne se soucient pas du tout de notre maillage. Nous pourrions placer des nœuds n'importe où dans le monde du jeu : tant qu'il y a une connexion entre deux nœuds connectés, ainsi qu'entre les points de début et de fin et au moins un des nœuds, l'algorithme fonctionnera aussi bien qu'avant. C'est ce qu'on appelle souvent un système de points de cheminement, car chaque nœud représente une position significative dans le monde qui peut faire partie d'un nombre illimité de chemins hypothétiques.
Exemple 1 : un nœud dans chaque carré. La recherche démarre au nœud où se trouve l'agent et se termine au nœud du carré souhaité.
Exemple 2 : un ensemble plus petit de nœuds (waypoints). La recherche commence sur la place de l'agent, passe par le nombre de nœuds requis, puis se poursuit jusqu'à la destination.
Il s'agit d'un système complètement flexible et puissant. Mais une certaine prudence est nécessaire pour décider où et comment placer un waypoint, sinon les agents risquent tout simplement de ne pas voir le point le plus proche et ne pourront pas commencer le chemin. Ce serait plus simple si nous pouvions placer automatiquement des waypoints en fonction de la géométrie du monde.
C'est ici qu'apparaît le maillage de navigation ou navmesh (navigation mesh). Il s'agit généralement d'un maillage 2D de triangles superposé à la géométrie du monde, partout où l'agent est autorisé à marcher. Chacun des triangles du maillage devient un nœud dans le graphique et comporte jusqu'à trois triangles adjacents qui deviennent des nœuds adjacents dans le graphique.
Cette image est un exemple du moteur Unity - il a analysé la géométrie du monde et créé un navmesh (dans la capture d'écran en bleu clair). Chaque polygone d'un navmesh est une zone dans laquelle un agent peut se tenir debout ou se déplacer d'un polygone à un autre. Dans cet exemple, les polygones sont plus petits que les étages sur lesquels ils se trouvent - ceci afin de prendre en compte la taille de l'agent, qui s'étendra au-delà de sa position nominale.
Nous pouvons rechercher un itinéraire à travers ce maillage, toujours en utilisant l'algorithme A*. Cela nous donnera un itinéraire presque parfait dans le monde, qui prend en compte toute la géométrie et ne nécessite pas de nœuds inutiles ni de création de waypoints.
Le Pathfinding est un sujet trop vaste pour lequel une seule section d’un article ne suffit pas. Si vous souhaitez l'étudier plus en détail, cela vous aidera .
planification
Grâce à l'exploration de chemin, nous avons appris que parfois, il ne suffit pas de simplement choisir une direction et de se déplacer : nous devons choisir un itinéraire et faire quelques virages pour arriver à la destination souhaitée. On peut généraliser cette idée : atteindre un objectif n'est pas seulement l'étape suivante, mais toute une séquence, nécessitant parfois d'anticiper plusieurs étapes pour savoir quelle devrait être la première. C’est ce qu’on appelle la planification. L’orientation peut être considérée comme l’une des nombreuses extensions de la planification. En ce qui concerne notre cycle Sens/Penser/Agir, c'est là que la partie Réfléchir planifie plusieurs parties Agir pour le futur.
Regardons l'exemple du jeu de société Magic : The Gathering. Nous commençons par avoir le jeu de cartes suivant en main :
- Marais - Donne 1 mana noir (carte de terrain).
- Forêt - donne 1 mana vert (carte de terrain).
- Assistant fugitif – Nécessite 1 mana bleu pour être invoqué.
- Elfique Mystique – Nécessite 1 mana vert pour être invoqué.
Nous ignorons les trois cartes restantes pour faciliter les choses. Selon les règles, un joueur est autorisé à jouer 1 carte de terrain par tour, il peut « appuyer » sur cette carte pour en extraire du mana, puis lancer des sorts (y compris invoquer une créature) en fonction de la quantité de mana. Dans cette situation, le joueur humain sait jouer Forest, engager 1 mana vert, puis invoquer Elvish Mystic. Mais comment l’IA du jeu peut-elle comprendre cela ?
Planification facile
L’approche triviale consiste à essayer chaque action tour à tour jusqu’à ce qu’il n’en reste plus aucune qui convienne. En regardant les cartes, l'IA voit ce que Swamp peut jouer. Et il y joue. Y a-t-il d'autres actions restantes ce tour-ci ? Il ne peut invoquer ni Elvish Mystic ni Fugitive Wizard, car ils nécessitent respectivement du mana vert et bleu pour les invoquer, tandis que Swamp ne fournit que du mana noir. Et il ne pourra plus jouer à Forest, car il a déjà joué à Swamp. Ainsi, l’IA du jeu a suivi les règles, mais l’a mal fait. Peut être amélioré.
La planification peut trouver une liste d'actions qui amènent le jeu à l'état souhaité. Tout comme chaque case d'un chemin avait des voisins (en recherche de chemin), chaque action d'un plan a également des voisins ou des successeurs. Nous pouvons rechercher ces actions et les actions ultérieures jusqu'à ce que nous atteignions l'état souhaité.
Dans notre exemple, le résultat souhaité est « invoquer une créature si possible ». Au début du tour, on ne voit que deux actions possibles autorisées par les règles du jeu :
1. Jouez à Swamp (résultat : Swamp dans le jeu)
2. Jouez à Forest (résultat : Forest dans le jeu)
Chaque action entreprise peut conduire à d’autres actions et en fermer d’autres, encore une fois en fonction des règles du jeu. Imaginez que nous jouions à Swamp - cela supprimera Swamp à l'étape suivante (nous l'avons déjà joué), et cela supprimera également Forest (car selon les règles, vous pouvez jouer une carte de terrain par tour). Après cela, l'IA ajoute l'obtention d'1 mana noir comme étape suivante car il n'y a pas d'autres options. S'il continue et choisit Tap the Swamp, il recevra 1 unité de mana noir et ne pourra rien en faire.
1. Jouez à Swamp (résultat : Swamp dans le jeu)
1.1 Marais « Tap » (résultat : Marais « exploité », +1 unité de mana noir)
Aucune action disponible - FIN
2. Jouez à Forest (résultat : Forest dans le jeu)
La liste des actions était courte, nous sommes arrivés à une impasse. Nous répétons le processus pour l'étape suivante. Nous jouons à Forest, ouvrons l'action « obtenez 1 mana vert », qui à son tour ouvrira la troisième action - invoquer Elvish Mystic.
1. Jouez à Swamp (résultat : Swamp dans le jeu)
1.1 Marais « Tap » (résultat : Marais « exploité », +1 unité de mana noir)
Aucune action disponible - FIN
2. Jouez à Forest (résultat : Forest dans le jeu)
2.1 « Exploiter » la forêt (résultat : la forêt est « engagée », +1 unité de mana vert)
2.1.1 Invoquer un Mystique Elfique (résultat : Mystique Elfique en jeu, -1 mana vert)
Aucune action disponible - FIN
Finalement, nous avons exploré toutes les actions possibles et trouvé un plan qui invoque une créature.
Ceci est un exemple très simplifié. Il est conseillé de choisir le meilleur plan possible, plutôt que n’importe quel plan répondant à certains critères. Il est généralement possible d’évaluer les plans potentiels en fonction des résultats ou des avantages globaux de leur mise en œuvre. Vous pouvez gagner 1 point en jouant une carte de terrain et 3 points en invoquant une créature. Jouer à Swamp serait un plan en 1 point. Et jouer à Forest → Tap the Forest → invoquer Elvish Mystic donnera immédiatement 4 points.
C'est ainsi que fonctionne la planification dans Magic : The Gathering, mais la même logique s'applique dans d'autres situations. Par exemple, déplacer un pion pour laisser la place au fou de se déplacer aux échecs. Ou cachez-vous derrière un mur pour tirer en toute sécurité dans XCOM comme celui-ci. En général, vous voyez l'idée.
Planification améliorée
Parfois, il y a trop d’actions potentielles pour envisager toutes les options possibles. Reprenons l'exemple de Magic : The Gathering : disons que dans le jeu et dans votre main il y a plusieurs cartes de terrain et de créature - le nombre de combinaisons possibles de mouvements peut être de plusieurs dizaines. Il existe plusieurs solutions au problème.
La première méthode est le chaînage vers l’arrière. Au lieu d’essayer toutes les combinaisons, il vaut mieux commencer par le résultat final et essayer de trouver un itinéraire direct. Au lieu d'aller de la racine de l'arbre à une feuille spécifique, nous nous déplaçons dans la direction opposée : de la feuille à la racine. Cette méthode est plus simple et plus rapide.
Si l'ennemi a 1 point de vie, vous pouvez trouver le plan "infliger 1 dégât ou plus". Pour y parvenir, un certain nombre de conditions doivent être remplies :
1. Les dégâts peuvent être causés par un sort - il doit être en main.
2. Pour lancer un sort, vous avez besoin de mana.
3. Pour obtenir du mana, vous devez jouer une carte de terrain.
4. Pour jouer une carte de terrain, vous devez l'avoir en main.
Une autre méthode consiste à rechercher le meilleur en premier. Au lieu d’essayer toutes les voies, nous choisissons celle qui convient le mieux. Le plus souvent, cette méthode donne le plan optimal sans frais de recherche inutiles. A* est une forme de meilleure première recherche : en examinant les itinéraires les plus prometteurs dès le début, il peut déjà trouver le meilleur chemin sans avoir à vérifier d'autres options.
Une option de recherche intéressante et de plus en plus populaire est la recherche arborescente Monte Carlo. Au lieu de deviner quels plans sont meilleurs que d’autres lors du choix de chaque action ultérieure, l’algorithme choisit des successeurs aléatoires à chaque étape jusqu’à la fin (lorsque le plan a abouti à une victoire ou à une défaite). Le résultat final est ensuite utilisé pour augmenter ou diminuer le poids des options précédentes. En répétant ce processus plusieurs fois de suite, l'algorithme donne une bonne estimation du meilleur prochain coup, même si la situation change (si l'ennemi prend des mesures pour interférer avec le joueur).
Aucune histoire sur la planification dans les jeux ne serait complète sans la planification d'action orientée vers un objectif ou GOAP (planification d'action orientée vers un objectif). Il s’agit d’une méthode largement utilisée et discutée, mais à part quelques détails distinctifs, il s’agit essentiellement de la méthode de chaînage arrière dont nous avons parlé plus tôt. Si l'objectif était de « détruire le joueur » et que le joueur est à couvert, le plan pourrait être : détruire avec une grenade → l'obtenir → le lancer.
Il existe généralement plusieurs objectifs, chacun ayant sa propre priorité. Si l'objectif de priorité la plus élevée ne peut être atteint (aucune combinaison d'actions ne crée un plan « tuer le joueur » car le joueur n'est pas visible), l'IA se rabattra sur des objectifs de priorité inférieure.
Formation et adaptation
Nous avons déjà dit que l'IA des jeux n'utilise généralement pas l'apprentissage automatique car elle n'est pas adaptée à la gestion des agents en temps réel. Mais cela ne signifie pas que vous ne pouvez pas emprunter quelque chose à ce domaine. Nous voulons un adversaire dans un jeu de tir dont nous pouvons apprendre quelque chose. Renseignez-vous par exemple sur les meilleurs emplacements sur la carte. Ou un adversaire dans un jeu de combat qui bloquerait les mouvements combo fréquemment utilisés par le joueur, le motivant à en utiliser d'autres. L’apprentissage automatique peut donc s’avérer très utile dans de telles situations.
Statistiques et probabilités
Avant d'aborder des exemples complexes, voyons jusqu'où nous pouvons aller en prenant quelques mesures simples et en les utilisant pour prendre des décisions. Par exemple, la stratégie en temps réel : comment déterminer si un joueur peut lancer une attaque dans les premières minutes du jeu et quelle défense préparer contre cela ? Nous pouvons étudier les expériences passées d'un joueur pour comprendre quelles pourraient être ses réactions futures. Pour commencer, nous ne disposons pas de telles données brutes, mais nous pouvons les collecter - chaque fois que l'IA joue contre un humain, elle peut enregistrer l'heure de la première attaque. Après quelques sessions, nous obtiendrons une moyenne du temps qu'il faudra au joueur pour attaquer dans le futur.
Il y a aussi un problème avec les valeurs moyennes : si un joueur s'est précipité 20 fois et a joué lentement 20 fois, alors les valeurs requises se situeront quelque part au milieu, et cela ne nous donnera rien d'utile. Une solution consiste à limiter les données d'entrée - les 20 dernières pièces peuvent être prises en compte.
Une approche similaire est utilisée pour estimer la probabilité de certaines actions en supposant que les préférences passées du joueur seront les mêmes dans le futur. Si un joueur nous attaque cinq fois avec une boule de feu, deux fois avec des éclairs et une fois avec une mêlée, il est évident qu'il préfère la boule de feu. Extrapolons et voyons la probabilité d'utiliser différentes armes : boule de feu=62,5 %, éclair=25 % et mêlée=12,5 %. Notre IA de jeu doit se préparer à se protéger du feu.
Une autre méthode intéressante consiste à utiliser le classificateur Naive Bayes pour étudier de grandes quantités de données d'entrée et classifier la situation afin que l'IA réagisse de la manière souhaitée. Les classificateurs bayésiens sont surtout connus pour leur utilisation dans les filtres anti-spam. Là, ils examinent les mots, les comparent à l'endroit où ces mots sont apparus auparavant (dans le spam ou non) et tirent des conclusions sur les e-mails entrants. Nous pouvons faire la même chose avec moins d’intrants. Sur la base de toutes les informations utiles que l'IA voit (comme quelles unités ennemies sont créées, ou quels sorts elles utilisent, ou quelles technologies elles ont recherchées), et le résultat final (guerre ou paix, se précipiter ou se défendre, etc.) - nous choisirons le comportement de l'IA souhaité.
Toutes ces méthodes de formation sont suffisantes, mais il est conseillé de les utiliser sur la base de données de tests. L’IA apprendra à s’adapter aux différentes stratégies utilisées par vos playtesteurs. L'IA qui s'adapte au joueur après sa sortie peut devenir trop prévisible ou trop difficile à vaincre.
Adaptation basée sur la valeur
Compte tenu du contenu de notre monde de jeu et des règles, nous pouvons modifier l'ensemble des valeurs qui influencent la prise de décision, plutôt que d'utiliser simplement les données d'entrée. Nous faisons ceci :
- Laissez l'IA collecter des données sur l'état du monde et les événements clés du jeu (comme ci-dessus).
- Modifions quelques valeurs importantes en fonction de ces données.
- Nous mettons en œuvre nos décisions sur la base du traitement ou de l’évaluation de ces valeurs.
Par exemple, un agent dispose de plusieurs salles parmi lesquelles choisir sur une carte de jeu de tir à la première personne. Chaque pièce a sa propre valeur, qui détermine à quel point il est souhaitable de la visiter. L'IA choisit au hasard dans quelle pièce se rendre en fonction de la valeur. L'agent se souvient alors de la pièce dans laquelle il a été tué et réduit sa valeur (la probabilité qu'il y revienne). De même pour la situation inverse : si l'agent détruit de nombreux adversaires, alors la valeur de la pièce augmente.
Modèle de Markov
Et si nous utilisions les données collectées pour faire des prédictions ? Si nous nous souvenons de chaque pièce dans laquelle nous voyons un joueur pendant une certaine période de temps, nous pourrons prédire dans quelle pièce le joueur pourrait se rendre. En suivant et en enregistrant les mouvements du joueur à travers les pièces (valeurs), nous pouvons les prédire.
Prenons trois pièces : rouge, verte et bleue. Et aussi les observations que nous avons enregistrées en regardant la session de jeu :
Le nombre d'observations dans chaque pièce est presque égal - nous ne savons toujours pas où trouver un bon endroit pour une embuscade. La collecte de statistiques est également compliquée par la réapparition des joueurs, qui apparaissent uniformément sur toute la carte. Mais les données sur la prochaine pièce dans laquelle ils entrent après leur apparition sur la carte sont déjà utiles.
On voit que la salle verte convient aux joueurs - la plupart des gens s'y déplacent de la salle rouge, dont 50 % y restent plus loin. La chambre bleue, au contraire, n’est pas populaire : presque personne n’y va, et s’ils y vont, ils n’y restent pas longtemps.
Mais les données nous disent quelque chose de plus important : lorsqu'un joueur est dans une pièce bleue, la prochaine pièce dans laquelle nous le verrons sera rouge et non verte. Même si la salle verte est plus populaire que la salle rouge, la situation change si le joueur se trouve dans la salle bleue. L'état suivant (c'est-à-dire la pièce dans laquelle le joueur ira) dépend de l'état précédent (c'est-à-dire la pièce dans laquelle se trouve actuellement le joueur). Parce que nous explorons les dépendances, nous ferons des prédictions plus précises que si nous comptions simplement les observations de manière indépendante.
La prédiction d'un état futur sur la base des données d'un état passé s'appelle un modèle de Markov, et de tels exemples (avec des pièces) sont appelés chaînes de Markov. Puisque les modèles représentent la probabilité de changements entre des états successifs, ils sont affichés visuellement sous forme de FSM avec une probabilité autour de chaque transition. Auparavant, nous utilisions FSM pour représenter l'état comportemental dans lequel se trouvait un agent, mais ce concept s'étend à n'importe quel état, qu'il soit associé ou non à l'agent. Dans ce cas, les états représentent la pièce occupée par l’agent :
Il s'agit d'un moyen simple de représenter la probabilité relative de changements d'état, donnant à l'IA une certaine capacité à prédire l'état suivant. Vous pouvez anticiper plusieurs étapes à venir.
Si un joueur se trouve dans la salle verte, il y a 50 % de chances qu'il y reste la prochaine fois qu'il sera observé. Mais quelles sont les chances qu’il soit toujours là même après ? Non seulement il y a une chance que le joueur soit resté dans la salle verte après deux observations, mais il y a aussi une chance qu'il en soit parti et y soit revenu. Voici le nouveau tableau prenant en compte les nouvelles données :
Il montre que la chance de voir le joueur dans la salle verte après deux observations sera égale à 51% - 21% qu'il viendra de la salle rouge, 5% d'entre eux que le joueur visitera la salle bleue entre eux, et 25% que le joueur ne quittera pas la salle verte.
Le tableau est simplement un outil visuel : la procédure nécessite uniquement de multiplier les probabilités à chaque étape. Cela signifie que vous pouvez regarder loin dans le futur avec une mise en garde : nous supposons que les chances d'entrer dans une pièce dépendent entièrement de la pièce actuelle. C'est ce qu'on appelle la propriété de Markov : l'état futur ne dépend que du présent. Mais ce n’est pas exact à cent pour cent. Les joueurs peuvent modifier leurs décisions en fonction d'autres facteurs : niveau de santé ou quantité de munitions. Parce que nous n’enregistrons pas ces valeurs, nos prévisions seront moins précises.
N-grammes
Qu'en est-il de l'exemple d'un jeu de combat et de la prédiction des mouvements combo du joueur ? Le même! Mais au lieu d’un état ou d’un événement, nous examinerons l’ensemble des séquences qui composent une frappe combinée.
Une façon de procéder consiste à stocker chaque entrée (telle que Kick, Punch ou Block) dans un tampon et à écrire l'intégralité du tampon en tant qu'événement. Ainsi, le joueur appuie à plusieurs reprises sur Kick, Kick, Punch pour utiliser l'attaque SuperDeathFist, le système d'IA stocke toutes les entrées dans un tampon et se souvient des trois dernières utilisées à chaque étape.
(Les lignes en gras correspondent au moment où le joueur lance l'attaque SuperDeathFist.)
L'IA verra toutes les options lorsque le joueur sélectionne Kick, suivi d'un autre Kick, puis remarquera que l'entrée suivante est toujours Punch. Cela permettra à l'agent de prédire le mouvement combo de SuperDeathFist et de le bloquer si possible.
Ces séquences d'événements sont appelées N-grammes, où N est le nombre d'éléments stockés. Dans l'exemple précédent, il s'agissait d'un 3 grammes (trigramme), ce qui signifie : les deux premières entrées sont utilisées pour prédire la troisième. En conséquence, dans un 5 grammes, les quatre premières entrées prédisent la cinquième et ainsi de suite.
Le concepteur doit choisir avec soin la taille des N-grammes. Un N plus petit nécessite moins de mémoire mais stocke également moins d'historique. Par exemple, un 2 grammes (bigramme) enregistrera Kick, Kick ou Kick, Punch, mais ne pourra pas stocker Kick, Kick, Punch, donc l'IA ne répondra pas au combo SuperDeathFist.
En revanche, des nombres plus grands nécessitent plus de mémoire et l’IA sera plus difficile à entraîner puisqu’il y aura beaucoup plus d’options possibles. Si vous aviez trois entrées possibles : Kick, Punch ou Block, et que nous utilisions un 10 grammes, cela représenterait environ 60 XNUMX options différentes.
Le modèle bigramme est une simple chaîne de Markov - chaque paire état passé/état actuel est un bigramme, et vous pouvez prédire le deuxième état en fonction du premier. Les N-grammes de 3 grammes et plus peuvent également être considérés comme des chaînes de Markov, où tous les éléments (sauf le dernier du N-gramme) forment ensemble le premier état et le dernier élément le second. L'exemple du jeu de combat montre la possibilité de passer de l'état Kick and Kick à l'état Kick and Punch. En traitant plusieurs entrées de l'historique d'entrée comme une seule unité, nous transformons essentiellement la séquence d'entrée en une partie de l'état entier. Cela nous donne la propriété de Markov, qui nous permet d'utiliser des chaînes de Markov pour prédire la prochaine entrée et deviner quel sera le prochain mouvement combo.
Conclusion
Nous avons parlé des outils et des approches les plus courants dans le développement de l'intelligence artificielle. Nous avons également examiné les situations dans lesquelles ils doivent être utilisés et où ils sont particulièrement utiles.
Cela devrait suffire pour comprendre les bases de l’IA des jeux. Mais bien sûr, ce ne sont pas toutes des méthodes. Moins populaires, mais non moins efficaces, citons :
- algorithmes d'optimisation, y compris l'escalade, la descente de pente et les algorithmes génétiques
- algorithmes de recherche/planification contradictoires (élagage minimax et alpha-bêta)
- méthodes de classification (perceptrons, réseaux de neurones et machines à vecteurs supports)
- systèmes de traitement de la perception et de la mémoire des agents
- approches architecturales de l'IA (systèmes hybrides, architectures de sous-ensembles et autres moyens de superposer des systèmes d'IA)
- outils d'animation (planification et coordination des mouvements)
- facteurs de performance (niveau de détail, à tout moment et algorithmes de découpage temporel)
Ressources associées:
1. GameDev.net a et .
2. contient de nombreuses présentations et articles sur un large éventail de sujets liés au développement de l'IA de jeux.
3. comprend des sujets du GDC AI Summit, dont beaucoup sont disponibles gratuitement.
4. Des documents utiles peuvent également être trouvés sur le site Web .
5. Tommy Thompson, chercheur en IA et développeur de jeux, réalise des vidéos sur YouTube avec une explication et une étude de l'IA dans les jeux commerciaux.
Livres sur le sujet :
1. La série de livres Game AI Pro est une collection d'articles courts qui expliquent comment implémenter des fonctionnalités spécifiques ou comment résoudre des problèmes spécifiques.
2. La série AI Game Programming Wisdom est le prédécesseur de la série Game AI Pro. Il contient des méthodes plus anciennes, mais presque toutes sont pertinentes encore aujourd'hui.
3. est l'un des textes de base pour tous ceux qui souhaitent comprendre le domaine général de l'intelligence artificielle. Ce n'est pas un livre sur le développement de jeux : il enseigne les bases de l'IA.
Source: habr.com