Présentation

Cet article vous présentera un large éventail de concepts d'intelligence artificielle dans les jeux («gaming AI»), afin que vous compreniez quels outils peuvent être utilisés pour résoudre les problèmes d'IA, comment ils fonctionnent ensemble et comment commencer à les implémenter dans le moteur sélectionné.

Je suppose que vous êtes familier avec les jeux vidéo, un peu familiarisé avec des concepts mathématiques tels que la géométrie, la trigonométrie, etc. La plupart des exemples de code seront écrits en pseudo-code, vous n'avez donc pas besoin de connaître une langue spécifique.

Qu'est-ce qu'une "IA de jeu"?

Le jeu AI traite principalement de la sélection des actions d'une entité en fonction des conditions actuelles. Dans la littérature traditionnelle sur l'IA, on parle de gestion des « agents intelligents ». L'agent est généralement un personnage du jeu, mais il peut s'agir d'une machine, d'un robot ou même de quelque chose de plus abstrait - un groupe entier d'entités, un pays ou une civilisation. Dans tous les cas, c'est un objet qui surveille son environnement, prend des décisions en fonction de lui et agit conformément à ces décisions. C'est ce qu'on appelle parfois le cycle perception-pensée-action (Sens / Penser / Agir):

• Perception: l'agent reconnaît - ou en est informé - des informations sur l'environnement qui peuvent affecter son comportement (par exemple, les dangers à proximité, les objets collectés, les points importants, etc.)
• Réflexion: l'agent décide comment réagir (par exemple, décide s'il est sûr de collecter des objets, s'il doit se battre ou mieux se cacher en premier)
• Action: l'agent effectue des actions pour mettre en œuvre ses décisions (par exemple, commence à se déplacer le long de la route vers l'ennemi ou vers le sujet, etc.)
• ... puis, en raison des actions des personnages, la situation change, donc le cycle doit être répété avec de nouvelles données.

Les tâches de l'IA dans le monde réel, en particulier celles qui sont pertinentes aujourd'hui, se concentrent généralement sur la «perception». Par exemple, les véhicules sans pilote devraient recevoir des images de la route devant eux, en les combinant avec d'autres données (radar et lidar) et en essayant d'interpréter ce qu'ils voient. Habituellement, cette tâche est résolue par l'apprentissage automatique, qui fonctionne particulièrement bien avec de grands tableaux de données bruyantes du monde réel (par exemple, avec des photos de la route devant la voiture ou quelques images de vidéo) et leur donne un sens, en extrayant des informations sémantiques, par exemple, «il y a 20 mètres devant moi une autre voiture. " Ces tâches sont appelées problèmes de classification .

Les jeux sont inhabituels dans la mesure où ils n'ont pas besoin d'un système complexe pour extraire ces informations, car ils font partie intégrante de la simulation. Il n'est pas nécessaire d'exécuter des algorithmes de reconnaissance d'image pour détecter l'ennemi devant vous; le jeu sait qu'il y a un ennemi et peut transmettre ces informations directement au processus décisionnel. Par conséquent, la «perception» dans ce cycle est généralement grandement simplifiée, et toute la complexité se pose dans la mise en œuvre de la «pensée» et de «l'action».

Limitations du développement de l'IA de jeu

L'IA de jeu prend généralement en compte les restrictions suivantes:

• Contrairement à l'algorithme d'apprentissage automatique, il ne s'entraîne généralement pas à l'avance; lors du développement d'un jeu, il n'est pas pratique d'écrire un réseau de neurones pour surveiller des dizaines de milliers de joueurs afin de trouver la meilleure façon de jouer contre eux, car le jeu n'est pas encore sorti et il n'a pas de joueurs!
• On suppose généralement que le jeu doit divertir et défier le joueur, et ne pas être «optimal» - par conséquent, même si vous pouvez former des agents à résister aux joueurs de la meilleure façon, les concepteurs ont le plus souvent besoin de quelque chose de différent d'eux.
• Souvent, les agents doivent avoir un comportement «réaliste» pour que les joueurs sentent qu'ils rivalisent avec des adversaires de type humain. Le programme AlphaGo s'est avéré bien meilleur que les gens, mais les mouvements qu'il choisit sont si loin de la compréhension traditionnelle du jeu que les adversaires expérimentés en parlaient comme d'un match contre un étranger. Si le jeu prétend être un adversaire humain, cela n'est généralement pas souhaitable, donc l'algorithme doit être configuré de sorte qu'il prenne des décisions plausibles , pas idéales .
• L'IA doit être exécutée en temps réel. Dans ce contexte, cela signifie que l'algorithme ne peut pas, pour une décision, monopoliser les ressources du processeur pendant longtemps. Même 10 millisecondes pour prendre une décision, c'est trop, car la plupart des jeux ne disposent que de 16 à 33 millisecondes pour terminer toutes les opérations pour la prochaine image du graphique.
• Idéalement, au moins une partie du système devrait dépendre des données et ne pas être codée en dur afin que les non-programmeurs puissent apporter des modifications plus rapidement.

Après avoir appris tout cela, nous pouvons commencer à envisager des approches extrêmement simples de la création de l'IA, qui mettent en œuvre le cycle complet de la "perception-pensée-action" de manière à garantir l'efficacité et à permettre aux concepteurs de jeux de choisir des comportements complexes similaires aux actions humaines.

Prise de décision facile

Commençons par un jeu très simple, comme Pong. La tâche du joueur est de déplacer la "raquette" de manière à ce que la balle rebondisse dessus, plutôt que de passer devant. Les règles sont similaires au tennis - vous perdez si vous manquez la balle. L'IA a une tâche relativement simple de prendre des décisions sur le choix du sens de déplacement de la raquette.

Constructions conditionnelles codées en dur

Si nous voulions écrire de l'IA pour contrôler la raquette, il existe une solution intuitive et simple - il suffit de déplacer constamment la raquette pour qu'elle soit sous la balle. Lorsque la balle atteint la raquette, elle est déjà en position parfaite et peut la frapper.

Un algorithme simple pour cela, exprimé en pseudo-code, pourrait être:

  dans chaque image / mise à jour pendant le jeu:

 si le ballon est à gauche de la raquette:

	 déplacer la raquette vers la gauche

 sinon si le ballon est à droite de la raquette:

	 déplacer la raquette vers la droite 

Si nous supposons que la raquette peut se déplacer à une vitesse non inférieure à celle de la balle, alors ce sera l'algorithme parfait pour le joueur IA à Pong. Dans les cas où il n'y a pas tellement de données de «perception» à traiter et peu d'actions que l'agent peut effectuer, nous n'avons besoin de rien de plus compliqué.

Cette approche est si simple qu'elle montre à peine tout le cycle de la «perception-pensée-action». Mais il l' est .

• Les perceptions sont deux déclarations if. Le jeu sait où sont la balle et la raquette. Par conséquent, l'IA demande au jeu sa position, «sentant» ainsi si le ballon est à gauche ou à droite.
• La réflexion est également intégrée à deux instructions if. Ils contiennent deux solutions, qui dans ce cas s'excluent mutuellement, conduisant au choix de l'une des trois actions - déplacer la raquette vers la gauche, la déplacer vers la droite ou ne rien faire si la raquette est déjà correctement positionnée.
• Une «action» consiste à «déplacer la raquette vers la gauche» ou «à déplacer la raquette vers la droite». Selon la façon dont le jeu est implémenté, cela peut prendre la forme d'un déplacement instantané de la position de la raquette ou du réglage de la vitesse et de la direction de la raquette afin qu'elle puisse être déplacée correctement dans un autre code de jeu.

De telles approches sont souvent appelées «réactives» car il existe un simple ensemble de règles (dans notre cas, ce sont des instructions «si» dans le code) qui répondent à l'état du monde et décident instantanément de la marche à suivre.

Arbres de décision

Cet exemple Pong est en fait similaire au concept formel de l'IA appelé l' arbre de décision . Il s'agit d'un système dans lequel les décisions sont organisées sous la forme d'un arbre et l'algorithme doit le contourner pour atteindre une «feuille» contenant la décision finale sur l'action choisie. Tirons une représentation graphique de l'arbre de décision pour l'algorithme de raquette Pong à l'aide d'un organigramme:


On peut voir qu'il ressemble à un arbre, seulement renversé!

Chaque partie de l'arbre de décision est généralement appelée "nœud" car en IA, la théorie des graphes est utilisée pour décrire de telles structures. Chaque nœud peut être de deux types:

1. Nœuds de solutions: le choix de deux alternatives basées sur la vérification d'une condition. Chaque alternative est présentée comme son propre nœud;
2. Noeuds finaux: action effectuée qui représente la décision finale prise par l'arbre.

L'algorithme démarre à partir du premier nœud attribué par la «racine» de l'arbre, après quoi il décide à quel nœud enfant aller en fonction de la condition, ou effectue l'action stockée dans le nœud, puis arrête de fonctionner.

À première vue, l'avantage de l'arbre de décision n'est pas évident, car il fait exactement le même travail que les instructions if de la section précédente. Mais il existe un système très général dans lequel chaque solution a exactement 1 condition et 2 résultats possibles, ce qui permet au développeur de construire une IA à partir des données représentant les solutions dans l'arborescence, et en évitant de l'écrire en dur dans le code. Il est facile d'imaginer un format de données simple pour décrire un tel arbre:

Numéro de nœud	Décision (ou "fin")	Action	Action
1	La balle à gauche de la raquette?	Hein? Vérifier le nœud 2	Non? Vérifier le noeud 3
2	La fin	Déplacer la raquette vers la gauche
3	La balle à droite de la raquette?	Hein? Aller au nœud 4	Non? Aller au nœud 5
4	La fin	Déplacer la raquette vers la droite
5	La fin	Ne fais rien

Du point de vue du code, nous devons forcer le système à lire chacune de ces lignes, créer pour chaque nœud, attacher la logique de décision basée sur la deuxième colonne et attacher des nœuds enfants basés sur les troisième et quatrième colonnes. Nous devons toujours définir manuellement les conditions et les actions, mais nous pouvons maintenant imaginer un jeu plus complexe dans lequel vous pouvez ajouter de nouvelles solutions et actions, ainsi que configurer l'intégralité de l'IA en modifiant le seul fichier texte qui contient la définition de l'arborescence. Nous pouvons transférer le fichier au concepteur de jeu, qui pourra personnaliser le comportement sans avoir besoin de recompiler le jeu et de changer le code - à condition que le code ait déjà des conditions et des actions utiles.

Les arbres de décision peuvent être très puissants lorsqu'ils sont construits automatiquement sur la base d'un grand nombre d'exemples (par exemple, en utilisant l'algorithme ID3 ). Cela en fait un outil efficace et performant pour classer la situation sur la base des données entrantes, mais ce sujet dépasse le cadre des concepteurs créant des systèmes simples pour sélectionner des actions pour les agents.

Scripting

Ci-dessus, nous avons examiné un système d'arbre de décision qui utilise des conditions et des actions pré-créées. Le développeur d'IA peut reconstruire l'arborescence de la manière dont il a besoin, mais il doit s'appuyer sur le fait que le programmeur a déjà créé toutes les conditions et actions nécessaires pour lui. Mais que se passe-t-il si nous donnons au designer des outils plus puissants qui lui permettent de créer ses propres conditions, et peut-être ses actions?

Par exemple, au lieu de forcer l'encodeur à écrire les conditions «Balle à gauche de la raquette?» et "La balle à droite de la raquette?", il peut simplement créer un système dans lequel le concepteur écrit de manière indépendante les conditions de contrôle de ces valeurs. Par conséquent, les données de l'arbre de décision peuvent ressembler à ceci:

Numéro de nœud	Décision (ou "fin")	Solution	Action
1	ball.position.x <paddle.position.x	Hein? Vérifier le nœud 2	Non? Vérifier le noeud 3
2	La fin	Déplacer la raquette vers la gauche
3	ball.position.x> paddle.position.x	Hein? Vérifier le noeud 4	Non? Vérifier le nœud 5
4	La fin	Déplacer la raquette vers la droite
5	La fin	Ne fais rien

Comme avant, mais maintenant les solutions ont leur propre code, similaire à la partie conditionnelle de l'instruction if. Le code lira les nœuds de décision de la deuxième colonne et au lieu de rechercher une condition spécifique (par exemple, "la balle à gauche de la raquette?"), Calculera l'expression conditionnelle et renverra vrai ou faux. Cela peut être implémenté en incorporant un langage de script , tel que Lua ou Angelscript, qui permet au développeur de prendre des objets du jeu (par exemple, une balle et une raquette) et de créer des variables accessibles à partir du script (par exemple ball.position). Il est généralement plus facile d'écrire dans un langage de script qu'en C ++, et il ne nécessite pas une étape de compilation complète, il est donc bien adapté pour apporter des changements rapides à la logique du jeu et permet aux membres de l'équipe moins techniquement avertis de créer des fonctions de jeu sans l'intervention d'un encodeur.

Dans l'exemple ci-dessus, le langage de script est utilisé uniquement pour évaluer l'expression conditionnelle, mais les actions finales peuvent également être décrites dans le script. Par exemple, ces actions du type «déplacer la raquette vers la droite» peuvent devenir une construction de script comme ball.position.x += 10 , c'est-à-dire que l'action est également définie dans le script sans écrire le code de fonction MovePaddleRight.

Si vous faites un autre pas en avant, vous pouvez (et cela est souvent fait) aller à sa conclusion logique et écrire tout l'arbre de décision dans un langage de script, et non comme une liste de lignes de données. Ce sera un code similaire aux constructions conditionnelles présentées ci-dessus, mais elles ne sont pas «codées en dur» - elles se trouvent dans des fichiers de script externes, c'est-à-dire qu'elles peuvent être modifiées sans recompiler tout le programme. Il est souvent même possible de modifier le fichier de script pendant l'exécution du jeu, ce qui permet aux développeurs de tester rapidement différentes approches de la mise en œuvre de l'IA.

Réaction aux événements

Les exemples montrés ci-dessus sont destinés à l'exécution d'une seule image dans des jeux simples comme Pong. L'idée est qu'ils effectuent continuellement un cycle de "perception-pensée-action" et continuent d'agir sur la base du dernier état du monde. Mais dans les jeux plus complexes, au lieu de l'informatique, il est souvent plus raisonnable de réagir aux «événements», c'est-à-dire aux changements importants dans l'environnement du jeu.

Ce n'est pas particulièrement applicable à Pong, alors choisissons un autre exemple. Imaginez un jeu de tir dans lequel les ennemis sont immobiles jusqu'à ce qu'ils trouvent un joueur, après quoi ils commencent à effectuer des actions en fonction de leur classe - les combattants de mêlée peuvent se précipiter vers le joueur et les tireurs d'élite restent à distance et tentent de viser. En substance, il s'agit d'un système réactif simple - «si nous voyons un joueur, alors nous faisons quelque chose» - mais il peut être logiquement divisé en un événement («voir un joueur») et une réaction (sélectionnez une réponse et exécutez-la).

Cela nous ramène au cycle perception-pensée-action. Nous pouvons avoir un fragment de code, qui est un code de «perception», qui vérifie dans chaque image si l'ennemi voit le joueur. Sinon, rien ne se passe. Mais s'il voit, cela crée un événement «voir le joueur». Le code aura une partie distincte, qui dit: «lorsque l'événement« voir le joueur »se produit, alors nous faisons« xyz », et« xyz »est toute réponse que nous voulons traiter la pensée et l'action. Pour un combattant de personnage, vous pouvez connecter la réponse de course et d'attaque à l'événement "voir le joueur". Pour le tireur d'élite, nous allons connecter la fonction de réponse «cacher et viser» à cet événement. Comme dans les exemples précédents, nous pouvons créer de telles associations dans le fichier de données afin qu'elles puissent être modifiées rapidement sans reconstruire le moteur. De plus, il est possible (et cela est souvent utilisé) d'écrire de telles fonctions de réponse dans un langage de script afin qu'elles puissent créer des solutions complexes lorsque des événements se produisent.

Prise de décision améliorée

Bien que les systèmes réactifs simples soient très puissants, il existe de nombreuses situations où ils ne sont pas suffisants. Parfois, nous devons prendre des décisions différentes en fonction de ce que fait l'agent en ce moment, et le présenter comme une condition n'est pas pratique. Parfois, il y a tout simplement trop de conditions pour les présenter efficacement sous la forme d'un arbre de décision ou d'un script. Parfois, nous devons réfléchir à l'avance et évaluer comment la situation va changer avant de décider du prochain coup. Pour de telles tâches, des solutions plus complexes sont nécessaires.

Machines d'état

Une machine à états finis (FSM) est un moyen de dire en d'autres termes qu'un objet - par exemple, l'un de nos agents IA - est actuellement dans l'un des états possibles et qu'il peut aller de d'un état à l'autre. Il existe un nombre fini de tels états, d'où le nom. Un exemple du monde réel est l'ensemble des feux de circulation, passant du rouge au jaune, puis au vert, et encore une fois. À différents endroits, il y a différentes séquences de lumières, mais le principe est le même - chaque état signifie quelque chose ("se tenir", "manger", "se tenir debout, si possible", etc.), à tout moment il n'y a qu'un seul état, et les transitions entre elles sont basées sur des règles simples.

Cela s'applique bien aux PNJ dans les jeux. Le gardien peut avoir les états clairement séparés suivants:

• Patrouille
• Assaut
• Vol

Et nous pouvons proposer les règles suivantes pour la transition entre les États:

• 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'échappe

Ce schéma est assez simple et nous pouvons l'écrire avec des opérateurs «si» strictement définis et une variable dans laquelle l'état du gardien de sécurité et divers contrôles seront stockés - la présence d'ennemis à proximité, le niveau de santé du gardien de sécurité, etc. Mais imaginez que nous devons ajouter quelques états supplémentaires:

• En attente (entre patrouilles)
• Recherche (lorsque l'ennemi précédemment vu s'est caché)
• Échapper à l'aide (lorsque l'ennemi est repéré, mais il est trop fort pour se battre avec lui seul)

Et les choix disponibles dans chaque état sont généralement limités - par exemple, un garde ne voudra probablement pas chercher un ennemi perdu de vue si sa santé est trop faible.

Tôt ou tard, la longue liste de «si <x et y mais pas z> alors <p>» devient trop maladroite, et une approche formalisée de la mise en œuvre des états et des transitions entre eux peut aider ici. Pour ce faire, nous considérons tous les états et sous chaque état, nous listons toutes les transitions vers d'autres états ainsi que les conditions nécessaires pour eux. Nous devons également indiquer l'état initial afin de savoir par où commencer avant d'appliquer d'autres conditions.

Condition	Condition de transition	Nouvelle condition
En attente	attendu pendant 10 secondes	Patrouille
	l'ennemi est visible et l'ennemi est trop fort	Recherche d'aide
	l'ennemi est visible et beaucoup de santé	Assaut
	l'ennemi est visible et peu de santé	Vol
Patrouille	itinéraire de patrouille terminé	En attente
	l'ennemi est visible et l'ennemi est trop fort	Recherche d'aide
	l'ennemi est visible et beaucoup de santé	Assaut
	l'ennemi est visible et peu de santé	Vol
Assaut	l'ennemi n'est pas visible	En attente
	peu de santé	Vol
Vol	l'ennemi n'est pas visible	En attente
Chercher	recherché pendant 10 secondes	En attente
	l'ennemi est visible et l'ennemi est trop fort	Recherche d'aide
	l'ennemi est visible et beaucoup de santé	Assaut
	l'ennemi est visible et peu de santé	Vol
Recherche d'aide	ami voir	Assaut
Etat initial: en attente

Un tel schéma est appelé une table de transition d'état. C'est une manière complexe (et peu attrayante) de représenter un vaisseau spatial. À partir de ces données, vous pouvez également dessiner un diagramme et obtenir une représentation graphique complexe de ce à quoi pourrait ressembler le comportement des PNJ.


Il capture l'essence même de la prise de décisions pour l'agent en fonction de la situation dans laquelle il se trouve. Chaque flèche indique une transition entre les états si la condition à côté de la flèche est vraie.

À chaque mise à jour (ou «cycle»), nous vérifions l'état actuel de l'agent, examinons la liste des transitions, et si la condition de transition est remplie, puis passons à un nouvel état. L'état en attente vérifie dans chaque trame ou cycle si le temporisateur de 10 secondes a expiré. S'il a expiré, il démarre la transition vers l'état "Patrouille". De même, l'état «Attack» vérifie si l'agent a beaucoup de santé, et si c'est le cas, il passe à l'état «Flight».

C'est ainsi que les transitions d'états sont gérées - mais qu'en est-il des comportements associés aux états eux-mêmes? Du point de vue de l'exécution des actions elles-mêmes pour un état, il existe généralement deux types d'actions d'attachement à un vaisseau spatial:

1. Des actions pour l'état actuel sont effectuées périodiquement, par exemple, dans chaque trame ou «cycle».
2. Les actions sont effectuées lors de la transition d'un état à un autre.

Un exemple du premier type: l'état «Patrouille» dans chaque trame ou cycle continue de déplacer l'agent le long de la route de patrouille. L'état "Attaque" dans chaque image ou cycle essaie de lancer une attaque ou de la déplacer vers une position d'où elle est possible. Et ainsi de suite.

Un exemple du deuxième type: considérez la transition "si l'ennemi est visible et l'ennemi est trop fort → Cherchez de l'aide." L'agent doit choisir où aller pour demander de l'aide et stocker ces informations afin que l'état «Aide à la recherche» sache où aller. De même, dans l'état «Aide à la recherche», lorsque l'aide est trouvée, l'agent revient à l'état «Attaque», mais à ce moment, il souhaite informer le personnage amical de la menace, il peut donc y avoir une action «informer un ami du danger» effectuée pendant cette transition.

Et ici, nous pouvons à nouveau considérer ce système du point de vue de la «perception-pensée-action». La perception est intégrée dans les données utilisées par la logique de transition. La réflexion est intégrée aux transitions disponibles pour chaque état. Et l'action est réalisée par des actions effectuées périodiquement dans un état ou lors de la transition entre états.

Ce système simple fonctionne bien, même si parfois les conditions de transition avec interrogation peuvent être un processus coûteux. Par exemple, si chaque agent doit effectuer des calculs complexes dans chaque image pour déterminer la visibilité des ennemis et décider de la transition de la patrouille à l'attaque, cela peut prendre beaucoup de temps au processeur. Comme nous l'avons vu précédemment, il est possible de percevoir des changements importants dans l'état du monde comme des «événements» qui sont traités après qu'ils se sont produits. Par conséquent, au lieu de vérifier explicitement la condition de transition «mon agent peut-il voir le joueur?» Dans chaque image, nous pouvons créer un système de visibilité distinct qui effectue ces vérifications un peu moins souvent (par exemple, 5 fois par seconde) et crée le «joueur voir »lorsque le test est déclenché. Il est transmis à la machine d'état, qui a désormais la condition pour la transition «Reçu l'événement« joueur voir »», et qui y répond en conséquence. Le comportement qui en résultera sera similaire, à l'exception d'un retard de réaction à peine perceptible (et même de réalisme croissant), mais la productivité augmentera en raison du transfert de la «perception» vers une partie distincte du programme.

Machines à états hiérarchiques

Tout cela est bien, mais avec de grandes machines à états, il devient très gênant de travailler. Si nous voulons étendre l'état "Attaque" en le remplaçant par des états séparés "Attaque au corps à corps" et "Attaque à distance", nous devrons changer les transitions entrantes de chaque état, présent et futur, qui doit pouvoir passer à l'état "Attaque".

Vous avez probablement également remarqué que dans notre exemple, il existe de nombreuses transitions en double. La plupart des transitions dans l'état "En attente" sont identiques aux transitions dans l'état "Patrouille", et il serait bon d'éviter la duplication de ce travail, surtout si nous voulons ajouter des états encore plus similaires. Il sera logique de combiner «Attente» et «Patrouille» dans un groupe «États non combattants», qui n'a qu'un seul ensemble commun de transitions pour combattre les États. Si nous présentons ce groupe comme un état, nous pouvons considérer «l'attente» et la «patrouille» comme des «sous-états» de cet état, ce qui nous permettra de décrire plus efficacement l'ensemble du système. Un exemple d'utilisation d'une table de conversion distincte pour un nouveau sous-état sans combat:

Les principales conditions:

Condition	Condition de transition	Nouvelle condition
Non-combat	l'ennemi est visible et l'ennemi est trop fort	Recherche d'aide
	l'ennemi est visible et beaucoup de santé	Assaut
	l'ennemi est visible et peu de santé	Vol
Assaut	l'ennemi n'est pas visible	Non-combat
	peu de santé	Vol
Vol	l'ennemi n'est pas visible	Non-combat
Chercher	recherché pendant 10 secondes	Non-combat
	l'ennemi est visible et l'ennemi est trop fort	Recherche d'aide
	l'ennemi est visible et beaucoup de santé	Assaut
	l'ennemi est visible et peu de santé	Vol
Recherche d'aide	ami voir	Assaut
État initial: non-combat

Statut de non-combat:

Condition	Condition de transition	Nouvelle condition
En attente	attendu pendant 10 secondes	Patrouille
Patrouille	terminé la route de patrouille	En attente
Etat initial: en attente

Et sous forme de graphique:


En fait, c'est le même système, seulement maintenant il y a un état de non-combat qui remplace "Patrouille" et "Attente", qui est en soi une machine d'état avec deux sous-états de patrouille et d'attente. Si chaque état peut potentiellement contenir une machine d'état de sous-états (et ces sous-états peuvent également contenir sa propre machine d'état, etc.), alors nous avons une machine d'état hiérarchique (HFSM). En regroupant les comportements hors combat, nous supprimons un tas de transitions inutiles, et nous pouvons faire de même pour tous les nouveaux états qui peuvent avoir des transitions communes. Par exemple, si à l'avenir nous étendons l'état "Attaque" aux états "Attaque en mêlée" et "Attaque par projectile", ils peuvent être des sous-états, dont la transition est basée sur la distance à l'ennemi et la présence de munitions, qui ont des transitions de sortie communes basées sur les niveaux de santé et d'autres choses. Ainsi, avec un minimum de transitions dupliquées, des comportements et sous-comportements complexes peuvent être représentés.

Arbres de comportement

Avec HFSM, nous avons eu la possibilité de créer des ensembles de comportements assez complexes d'une manière plutôt intuitive. Cependant, on remarque immédiatement que la prise de décision sous forme de règles de transition est étroitement liée à l'état actuel. De nombreux jeux nécessitent juste cela. Et une utilisation prudente de la hiérarchie des états réduit le nombre de transitions en double. Mais parfois, nous avons besoin de règles qui s'appliquent quel que soit l'état actuel, ou s'appliquent dans presque tous les États. Par exemple, si la santé de l'agent est tombée à 25%, il peut vouloir s'enfuir, qu'il soit au combat, ou qu'il attend ou parle, ou qu'il se trouve dans un autre état. Nous ne voulons pas nous rappeler que nous devons ajouter cette condition à chaque état que nous pourrons ajouter au personnage à l'avenir. Ainsi, lorsque le concepteur dira plus tard qu'il souhaite modifier la valeur seuil de 25% à 10%, nous n'aurions pas à trier et à modifier chaque transition correspondante.

Dans une telle situation, l'idéal était un système dans lequel les décisions concernant l'état dans lequel il se trouve existent séparément des États eux-mêmes, de sorte que nous ne pouvons changer qu'un seul élément, et que les transitions sont toujours traitées correctement. C'est là que les arbres de comportement sont utiles.

Il existe plusieurs façons de mettre en œuvre des arbres comportementaux, mais l'essentiel est le même pour la plupart et très similaire à l'arbre de décision mentionné ci-dessus: l'algorithme commence à fonctionner à partir du «nœud racine», et il y a des nœuds dans l'arbre qui indiquent des décisions ou des actions. Cependant, il existe des différences clés:

• Les nœuds renvoient désormais l'une des trois valeurs suivantes: «réussi» (si le travail est terminé), «sans succès» (si le travail n'a pas été terminé) ou «exécuté» (si le travail est toujours en cours et n'a pas complètement réussi ou échoué).
• Maintenant, nous n'avons pas de nœuds de décision dans lesquels nous choisissons parmi deux alternatives, mais il existe des nœuds décorateurs avec un seul nœud enfant. S'ils «réussissent», ils exécutent leur seul nœud enfant. Les nœuds décorateurs contiennent souvent des conditions qui déterminent si l'exécution s'est terminée avec succès (ce qui signifie que vous devez exécuter leur sous-arbre) ou l'échec (alors rien ne doit être fait). Ils peuvent également revenir "en cours".
• Les noeuds effectuant des actions renvoient une valeur "en cours d'exécution" pour indiquer ce qui se passe.

Un petit ensemble de nœuds peut être combiné, créant un grand nombre de comportements complexes, et souvent ce schéma est très bref. Par exemple, nous pouvons réécrire l'autorité de certification hiérarchique de la garde de l'exemple précédent sous la forme d'un arbre de comportement:


Lors de l'utilisation de cette structure, il n'est pas nécessaire de faire une transition explicite des états "En attente" ou "Patrouille" aux états "Attaque" ou tout autre - si l'arbre est traversé de haut en bas et de gauche à droite, la décision correcte est prise en fonction de la situation actuelle. Si l'ennemi est visible et que le personnage a peu de santé, alors l'arbre terminera la course sur le nœud "Flight", quel que soit le nœud terminé précédemment ("Patrol", "Waiting", "Attack", etc.).

Vous remarquerez peut-être que nous n'avons pas encore de transition pour revenir à l'état "En attente" de "Patrouille" - et ici, les décorateurs inconditionnels seront utiles. Le nœud décorateur standard est «Répéter» - il n'a pas de conditions, il intercepte simplement le nœud enfant qui retourne «avec succès» et exécute à nouveau le nœud enfant, en retournant «exécuté». Le nouvel arbre ressemble à ceci:


Les arbres comportementaux sont assez complexes car il existe souvent de nombreuses manières différentes de créer un arbre, et trouver la bonne combinaison de nœuds décorateurs et de composants peut être une tâche ardue. Il y a aussi des problèmes avec la fréquence à laquelle nous devons vérifier l'arbre (voulons-nous le parcourir à chaque image ou quand quelque chose se produit qui peut affecter les conditions?) Et comment stocker l'état par rapport aux nœuds (comment savons-nous que nous avons attendu 10 secondes? Comment allons-nous savoir combien de nœuds ont été exécutés pour la dernière fois afin de terminer correctement la séquence?) Par conséquent, il existe de nombreuses implémentations différentes. Par exemple, sur certains systèmes, comme le système d'arborescence des comportements d'Unreal Engine 4, les nœuds de décorateur sont remplacés par des décorateurs de chaîne qui vérifient l'arborescence uniquement lorsque les conditions du décorateur changent et fournissent des «services»,qui peut être connecté aux nœuds et fournir des mises à jour périodiques même lorsque l'arborescence n'est pas vérifiée à nouveau. Les arbres comportementaux sont des outils puissants, mais apprendre à les utiliser correctement, en particulier avec autant d'implémentations différentes, peut être une tâche ardue.

Systèmes basés sur les services publics

Certains jeux nécessitent l'existence de nombreuses actions différentes, ils nécessitent donc des règles de transition centralisées plus simples, mais ils n'ont pas besoin de la puissance nécessaire pour implémenter complètement l'arbre de comportement. Au lieu de créer un ensemble explicite de choix ou un arbre d'actions potentielles avec des positions de repli implicites définies par la structure de l'arbre, peut-être vaut-il mieux simplement examiner toutes les actions et choisir celle qui est la plus applicable en ce moment?

C'est ce que font les systèmes basés sur l'utilité - ce sont des systèmes dans lesquels l'agent a de nombreuses actions à sa disposition, et il choisit d'effectuer une basée sur l' utilité relativechaque action. L'utilité ici est une mesure arbitraire d'importance ou de désirabilité pour un agent d'effectuer cette action. En écrivant des fonctions utilitaires pour calculer l'utilité d'une action en fonction de l'état actuel de l'agent et de son environnement, l'agent peut vérifier les valeurs de l'utilitaire et sélectionner l'état le plus approprié à l'heure actuelle.

Cela ressemble aussi beaucoup à une machine à états finis, sauf que les transitions sont déterminées par une évaluation de chaque état potentiel, y compris l'actuel. Il convient de noter que dans le cas général, nous choisissons la transition vers l'action la plus précieuse (ou y sommes si nous effectuons déjà cette action), mais pour une plus grande variabilité, il peut s'agir d'un choix aléatoire pondéré (donnant la priorité à l'action la plus précieuse, mais permettant le choix des autres) , un choix d'action aléatoire parmi les cinq premiers (ou toute autre quantité), etc.

Le système standard basé sur l'utilité attribue une certaine plage arbitraire de valeurs d'utilité - disons de 0 (complètement indésirable) à 100 (absolument souhaitable), et chaque action peut avoir un ensemble de facteurs qui influencent la façon dont la valeur est calculée. Pour revenir à notre exemple avec le gardien, on peut imaginer quelque chose comme ça:

Action	Calcul de l'utilité
Recherche d'aide	Si l'ennemi est visible et que l'ennemi est fort et que sa santé est faible, renvoyez 100, sinon retournez 0
Vol	Si l'ennemi est visible et qu'il y a peu de santé, renvoyez 90, sinon retournez 0
Assaut	Si l'ennemi est visible, renvoyez 80
En attente	Si nous sommes dans un état d'attente et attendons déjà 10 secondes, retournez 0, sinon 50
Patrouille	Si nous sommes à la fin de la route de patrouille, retournez 0, sinon 50

L'un des aspects les plus importants de ce schéma est que les transitions entre les actions sont exprimées implicitement - de n'importe quel état, vous pouvez complètement légitimement vous rendre dans un autre. De plus, les priorités d'action sont implicites dans les valeurs d'utilité renvoyées. Si l'ennemi est visible, et s'il est fort, et que le personnage a peu de santé, les valeurs non nulles renvoient Flight and Help Search , mais Help Search a toujours une note plus élevée. De même, les actions non-combat ne retournent jamais plus de 50, ils sont donc toujours vaincus par les combats. Dans cette optique, des actions et leurs calculs d'utilité sont créés.

Dans notre exemple, les actions renvoient une valeur d'utilité constante ou l'une des deux valeurs d'utilité constantes. Un système plus réaliste utilise une valeur de retour à partir d'une plage continue de valeurs. Par exemple, l'action Getaway peut renvoyer des valeurs d'utilité plus élevées si la santé de l'agent est inférieure, et l'action Attack peut renvoyer des valeurs d'utilité plus faibles si l'ennemi est trop fort. Cela permettra à Getaway de l' emporter sur Assault.dans toute situation où l'agent estime qu'il n'est pas en assez bonne santé pour combattre l'ennemi. Cela vous permet de modifier les priorités relatives des actions sur la base d'un certain nombre de critères, ce qui peut rendre cette approche plus flexible qu'un arbre de comportement ou un vaisseau spatial.

Chaque action a généralement plusieurs conditions qui influencent le calcul de l'utilité. Afin de ne pas tout mettre en dur dans le code, vous pouvez les écrire dans un langage de script ou sous la forme d'une série de formules mathématiques, assemblées de manière compréhensible. Beaucoup plus d'informations à ce sujet sont dans les conférences et présentations de Dave Mark ( @IADaveMark ).

Dans certains jeux qui tentent de simuler la vie quotidienne du personnage, par exemple, dans Les Sims, une autre couche de calculs est ajoutée dans laquelle l'agent a des «aspirations» ou des «motivations» qui affectent les valeurs d'utilité. Par exemple, si un personnage a la motivation Hunger, alors elle peut augmenter avec le temps, et le calcul de l'utilité de l'action Eat renverra des valeurs de plus en plus élevées jusqu'à ce que le personnage puisse effectuer cette action, réduisant le niveau de faim, et l'action " Eat ”est réduit à une valeur d'utilité nulle ou presque nulle.

L'idée de choisir des actions basées sur le système de points est assez simple, il est donc évident que vous pouvez utiliser la prise de décision basée sur l'utilité dans d'autres processus décisionnels de l'IA, et non les remplacer complètement par elle. L'arbre de décision peut interroger la valeur d'utilité de ses deux nœuds enfants et sélectionner le nœud avec la valeur la plus élevée. De même, un arbre de comportement peut avoir un nœud utilitaire composite qui compte l'utilitaire pour sélectionner le nœud enfant à exécuter.

Mouvement et navigation

Dans nos exemples précédents, il y avait soit une simple raquette, que nous avions ordonnée de déplacer de gauche à droite, soit un personnage de garde, qui avait toujours l'ordre de patrouiller ou d'attaquer. Mais comment contrôlons-nous exactement le mouvement d'un agent sur une période de temps? Comment régler la vitesse, éviter les obstacles, planifier un itinéraire lorsqu'il est impossible d'atteindre directement le point final? Nous allons maintenant examiner cette tâche.

Direction

Au niveau le plus simple, il est souvent sage de travailler avec chaque agent comme s'il avait une valeur de vitesse qui détermine la vitesse et la direction de son mouvement. Cette vitesse peut être mesurée en mètres par seconde, en miles par heure, en pixels par seconde et ainsi de suite. Si nous rappelons notre cycle «perception-pensée-action», nous pouvons imaginer que la «pensée» peut choisir la vitesse, après quoi «l'action» applique cette vitesse à l'agent, le déplaçant à travers le monde. Habituellement, dans les jeux, il existe un système de physique qui effectue cette tâche de manière indépendante, étudie la valeur de la vitesse de chaque entité et modifie sa position en conséquence. Par conséquent, il est souvent possible d'affecter un tel travail à ce système, ne laissant à l'IA que la tâche de choisir la vitesse de l'agent.

Si nous savons où l'agent veut être, alors nous devons utiliser notre vitesse pour déplacer l'agent dans cette direction. Sous une forme triviale, nous obtenons l'équation suivante:

 desire_travel = destination_position - position_agent 

Imaginez un monde 2D dans lequel l'agent est situé aux coordonnées (-2, -2), et le point cible est approximativement au nord-est, aux coordonnées (30, 20), c'est-à-dire que pour vous y rendre, vous devez vous déplacer (32, 22). Supposons que ces positions soient indiquées en mètres. Si nous décidons que l'agent peut se déplacer à une vitesse de 5 m / s, réduisons alors l'échelle du vecteur de déplacement à cette valeur et constatons que nous devons régler la vitesse approximativement (4.12, 2.83). En se basant sur cette valeur, l'agent arrivera au point final en un peu moins de 8 secondes, comme prévu.

Les calculs peuvent être effectués à tout moment. Par exemple, si l'agent est à mi-chemin de la cible, le mouvement souhaité sera deux fois moins élevé, mais après la mise à l'échelle à la vitesse maximale de l'agent de 5 m / s, la vitesse reste la même. Cela fonctionne également pour les cibles mobiles (dans des limites raisonnables), ce qui permet à l'agent de faire de petits ajustements en cours de route.

Cependant, nous avons souvent besoin de plus de contrôle. Par exemple, nous devrons peut-être augmenter lentement la vitesse, comme si le personnage restait d'abord immobile, puis passait à une étape, puis courait. D'un autre côté, nous devrons peut-être le ralentir à l'approche de la cible. Souvent, ces tâches sont résolues en utilisant les soi-disant « comportements de pilotage»"ayant leurs propres noms comme Seek, Flee, Arrival, etc. (Sur Habré, il y a une série d'articles à leur sujet: https://habr.com/post/358366/ .) Leur idée est que vous pouvez appliquer la vitesse de l'agent des forces d'accélération basées sur une comparaison de la position de l'agent et de la vitesse actuelle de déplacement vers la cible, créant différentes façons de se déplacer vers la cible.

Chaque comportement a son propre objectif légèrement différent. Seek et Arrive sont utilisés pour déplacer l'agent vers sa destination. L'évitement et la séparation des obstacles aident l'agent à effectuer de petits mouvements correctifs pour contourner les petits obstacles entre l'agent et sa destination. L'alignement et la cohésion forcent les agents à se déplacer ensemble, imitant les animaux du troupeau. Toutes les variations de différents comportements de pilotage peuvent être combinées ensemble, souvent sous la forme d'une somme pondérée, pour créer une valeur totale qui prend en compte tous ces différents facteurs et crée un seul vecteur résultant. Par exemple, un agent peut utiliser le comportement d'arrivée ainsi que les comportements de séparation et d'évitement d'obstacles pour rester à l'écart des murs et d'autres agents. Cette approche fonctionne bien dans des environnements ouverts qui ne sont pas trop complexes et encombrés.

Cependant, dans des environnements plus complexes, le simple fait d'ajouter les valeurs de sortie du comportement ne fonctionne pas très bien - parfois le mouvement près de l'objet est trop lent, ou l'agent se coince lorsque le comportement d'arrivée veut passer à travers l'obstacle, et le comportement d'évitement d'obstacle pousse l'agent du côté d'où il vient. . Par conséquent, il est parfois judicieux d'envisager des variations de comportement de direction plus compliquées que de simplement additionner toutes les valeurs. L'une des familles de ces approches consiste en une mise en œuvre différente - nous ne considérons pas chacun des comportements qui nous orientent, suivi de leur combinaison pour obtenir un consensus (qui en soi peut être inadéquat). Au lieu de cela, nous considérons le mouvement dans plusieurs directions différentes - par exemple, dans huit directions de la boussole, ou à 5-6 points devant l'agent,après quoi nous choisissons le meilleur.

Cependant, dans des environnements complexes avec des impasses et des options de virage, nous aurons besoin de quelque chose de plus avancé, et nous allons passer à cela bientôt.

Recherche de chemin

Les comportements de direction sont parfaits pour les mouvements simples dans une zone assez ouverte, comme un terrain de football ou une arène, où vous pouvez vous rendre de A à B en ligne droite avec de légers ajustements pour éviter les obstacles. Mais que se passe-t-il si l'itinéraire vers le point final est plus compliqué? Ensuite, nous avons besoin d'un «repérage» - explorer le monde et tracer un chemin le long de celui-ci afin que l'agent atteigne le point final.

Le moyen le plus simple est de tracer une grille sur le monde, et pour chaque cellule à côté de l'agent, regardez les cellules voisines dans lesquelles nous pouvons nous déplacer. Si l'un d'eux est notre dernier point, alors revenez sur l'itinéraire, de chaque cellule à la précédente, jusqu'à ce que nous arrivions au début, obtenant ainsi un itinéraire. Sinon, répétez le processus avec les voisins accessibles des voisins précédents jusqu'à ce que nous trouvions le point final ou que nous manquions de cellules (cela signifiera qu'il n'y a pas de route). Formellement, cette approche est appelée l'algorithme Breadth-First Search (BFS), car à chaque étape, il regarde dans toutes les directions (c'est-à-dire "large") avant de déplacer les recherches. L'espace de recherche est comme un front d'onde qui se déplace jusqu'à ce qu'il tombe sur l'endroit que nous recherchions.

Ceci est un exemple simple de recherche en action. La zone de recherche se développe à chaque étape jusqu'à ce qu'un point final y soit inclus, après quoi vous pouvez suivre le chemin vers le début.


En conséquence, nous obtenons une liste de cellules de grille, constituant l'itinéraire que vous devez parcourir. Habituellement, cela s'appelle un "chemin", un chemin (d'où la "recherche de chemins", la recherche de chemins), mais vous pouvez aussi l'imaginer comme un plan, car c'est une liste de lieux que vous devez visiter pour atteindre votre objectif, c'est-à-dire le point final.

Maintenant que nous connaissons la position de chaque cellule dans le monde, vous pouvez utiliser les comportements de direction décrits ci-dessus pour vous déplacer le long de l'itinéraire - d'abord du nœud de départ au nœud 2, puis du nœud 2 au nœud 3, etc. L'approche la plus simple consiste à se déplacer vers le centre de la cellule suivante, mais il existe également une alternative populaire - se déplacer vers le milieu de la nervure entre la cellule actuelle et la suivante. Cela permet à l'agent de couper les coins des virages serrés pour créer un mouvement plus réaliste.

Comme vous pouvez le voir, cet algorithme peut gaspiller des ressources car il examine autant de cellules dans la «mauvaise» direction que dans la «bonne». De plus, il ne permet pas de prendre en compte les coûts de déplacement, auxquels certaines cellules peuvent être «plus chères» que d'autres. Nous arrivons ici à l'aide d'un algorithme plus complexe appelé A *. Cela fonctionne à peu près de la même manière que la recherche en largeur, mais au lieu d'explorer aveuglément les voisins, puis les voisins des voisins, puis les voisins des voisins, les voisins, etc., il place tous ces nœuds dans une liste et les trie de sorte que le prochain nœud examiné soit toujours celui conduit très probablement à l'itinéraire le plus court. Les nœuds sont triés sur la base d'heuristiques (c'est-à-dire, en fait, une hypothèse raisonnable),qui prend en compte deux aspects - le coût d'une route hypothétique vers la cellule (prenant ainsi en compte tous les coûts nécessaires au déplacement) et une estimation de la distance de cette cellule par rapport au point final (déplaçant ainsi la recherche dans la bonne direction).


Dans cet exemple, nous avons montré qu'il examine une cellule à la fois, en choisissant à chaque fois une cellule voisine qui a les meilleures (ou l'une des meilleures) perspectives. Le chemin résultant est similaire au chemin de recherche en largeur, mais moins de cellules sont examinées dans le processus, ce qui est très important pour les performances du jeu à des niveaux complexes.

Mouvement sans maille

Dans les exemples précédents, une grille superposée au monde a été utilisée, et nous avons tracé un parcours autour du monde à travers les cellules de cette grille. Mais la plupart des jeux ne chevauchent pas la grille, et donc la superposition de la grille peut conduire à des modèles de mouvement irréalistes. En outre, cette approche peut nécessiter des compromis concernant la taille de chaque cellule - si elle est trop grande, elle ne sera pas en mesure de décrire correctement les petits couloirs et les virages, si elle est trop petite, la recherche dans des milliers de cellules peut être trop longue. Quelles sont les alternatives?

La première chose que nous devons comprendre est que, d'un point de vue mathématique, la grille nous donne un " graphique"de nœuds connectés. Les algorithmes A * (et BFS) fonctionnent avec des graphiques, et la grille n'est pas importante pour eux. Par conséquent, nous pouvons placer des nœuds dans des positions arbitraires du monde, et s'il y a une ligne droite entre deux nœuds connectés, mais il y a une ligne entre le début et la fin s'il n'y a qu'un seul nœud, notre algorithme fonctionnera comme avant, et en fait c'est encore mieux, car il y aura moins de nœuds. Ceci est souvent appelé le système de waypoints, car chaque nœud indique une position importante dans le monde qui peut créer partie d'un nombre quelconque de pu hypothétique s.


Exemple 1: un nœud dans chaque cellule de la grille. La recherche commence par le nœud dans lequel se trouve l'agent et se termine par la cellule finale.


Exemple 2: un nombre beaucoup plus petit de nœuds, ou waypoints . La recherche commence par l'agent, passe par le nombre requis de points de cheminement et se déplace vers le point de terminaison. Notez que le déplacement vers le premier point du chemin au sud-ouest du lecteur est un itinéraire inefficace, donc un certain post-traitement du chemin généré est généralement nécessaire (par exemple, pour remarquer que le chemin peut aller directement au waypoint au nord-est).

Il s'agit d'un système assez flexible et puissant, mais il nécessite une localisation soigneuse des points de cheminement, sinon les agents peuvent ne pas voir le point de cheminement le plus proche pour démarrer la route. Ce serait formidable si nous pouvions en quelque sorte générer automatiquement des points de cheminement basés sur la géométrie du monde.

Et puis navmesh vient à la rescousse. C'est l'abréviation de maillage de navigation. Essentiellement, il s'agit (généralement) d'un maillage bidimensionnel de triangles, chevauchant approximativement la géométrie du monde aux endroits où le jeu permet à l'agent de se déplacer. Chacun des triangles du maillage devient un nœud du graphique et comporte jusqu'à trois triangles adjacents qui deviennent des nœuds adjacents du graphique.

Voici un exemple du moteur Unity. Le moteur a analysé la géométrie du monde et créé navmesh (bleu), qui est une approximation de la géométrie. Chaque polygone nammesh est une zone dans laquelle un agent peut se tenir et un agent peut se déplacer d'un polygone à un polygone adjacent. (Dans cet exemple, les polygones sont plus étroits que le sol sur lequel ils se trouvent pour tenir compte du rayon de l'agent, qui s'étend au-delà de la position nominale de l'agent.)



Nous pouvons à nouveau rechercher l'itinéraire à travers le maillage en utilisant A *, ce qui nous donnera un itinéraire idéal à travers le monde qui prend en compte toute la géométrie et ne nécessite pas un nombre excessif de nœuds supplémentaires (comme ce serait le cas avec la grille) et la participation humaine à la génération de points le chemin.

La recherche de chemins est un sujet vaste, auquel il existe de nombreuses approches, surtout si vous devez programmer vous-même des détails de bas niveau. L'une des meilleures sources d'informations complémentaires est le site d'Amit Patel (traduction de l'article sur Habré: https://habr.com/post/331192/ ).

Planification

En utilisant la recherche de chemins comme exemple, nous avons vu que parfois il ne suffit pas simplement de choisir une direction et de commencer à s'y déplacer - nous devons choisir un itinéraire et effectuer plusieurs mouvements avant d'atteindre le point final souhaité. Nous pouvons généraliser cette idée à un large éventail de concepts dans lesquels l'objectif n'est pas seulement la prochaine étape. Pour y parvenir, vous devez prendre une série d'étapes, et pour savoir quelle devrait être la première étape, vous devrez peut-être regarder en avant. Cette approche est appelée planification . La recherche de chemins peut être considérée comme l'une des applications spécifiques de la planification, mais ce concept a de nombreuses autres applications. Revenant au cycle «perception-pensée-action», cette planification est une phase de réflexion qui tente de planifier plusieurs phases d'action pour l'avenir.

Regardons le jeu Magic: The Gathering. Vous avez votre premier coup, il y a plusieurs cartes entre vos mains, dont «Swamp», qui donne 1 point de mana noir, et «Forest», qui donne 1 point de mana vert, «Exorcist», qui nécessite 1 point de mana bleu pour appeler, et « Elven Mystic ”, pour appeler ce dont vous avez besoin de 1 point de mana vert. (Par souci de simplicité, nous omettons les trois cartes restantes.) Les règles stipulent qu'un joueur peut jouer une carte de terrain par tour, peut "toucher" ses cartes de terrain pour en obtenir du mana, et peut lancer autant de sorts (y compris les créatures invoquées) combien de mana il a. Dans cette situation, le joueur est susceptible de jouer à «Forest», de le toucher pour obtenir 1 point de mana vert, puis d'appeler «Elven Mystic». Mais comment une IA de jeu sait-elle qu'une telle décision doit être prise?

"Planificateur" simple

Une approche naïve peut être de simplement répéter chaque action dans l'ordre, jusqu'à ce qu'il y en ait une appropriée. En regardant la main, l'IA voit qu'elle peut jouer à «Swamp», et donc elle le fait. Y a-t-il d'autres actions après ce tour? Il ne peut invoquer ni Elven Mystic ni Exile Wizard, car cela nécessite du mana vert ou bleu, et le marais joué ne donne que du mana noir. Et nous ne pouvons pas jouer à «Forest» car nous avons déjà joué à «Swamp». Autrement dit, le joueur IA fera le déplacement selon les règles, mais ce ne sera pas très optimal. Heureusement, il existe une meilleure solution.

De la même manière que la recherche de chemins trouve une liste de positions pour se déplacer dans le monde afin d'arriver au bon point, notre planificateur peut trouver une liste d'actions qui mettent le jeu dans le bon état. Tout comme chaque position sur le chemin a un ensemble de voisins, qui sont des options potentielles pour choisir l'étape suivante le long du chemin, chaque action du plan a des voisins, ou «héritiers», qui sont candidats à l'étape suivante du plan. Nous pouvons rechercher ces actions et les actions suivantes jusqu'à atteindre l'état souhaité.

Supposons, pour notre exemple, que le résultat souhaité soit «invoque une créature, si possible». Au début du mouvement, nous n'avons que deux actions potentielles autorisées par les règles du jeu:

 1. Jouez "Swamp" (résultat: "Swamp" quitte la main et entre dans le jeu)
2. Jouez à "Forest" (résultat: "Forest" quitte la main et entre dans le jeu) 

Chaque action entreprise peut ouvrir d'autres actions ou les fermer, également conformément aux règles du jeu. Imaginez que nous avons choisi de jouer à "Swamp" - cela ferme la possibilité de jouer cette carte comme une action d'héritage potentielle (parce que "Swamp" a déjà été joué), ferme la possibilité de jouer à "Forest" (parce que les règles du jeu vous permettent de jouer une seule carte de terrain par tour) et ajoute la possibilité de toucher le «marais» pour obtenir 1 point de mana noir - et c'est en fait la seule action héritée. Si nous faisons un pas de plus et sélectionnons "toucher" Marais "", nous obtiendrons 1 point de mana noir avec lequel nous ne pouvons rien faire, donc c'est inutile.

 1. Jouez "Swamp" (résultat: "Swamp" quitte la main et entre dans le jeu)
            1.1 Touchez «Swamp» (résultat: nous avons touché «Swamp», +1 mana noir est disponible)
                        Aucune action restante - FIN
2. Jouez à "Forest" (résultat: "Forest" quitte la main et entre dans le jeu) 

Cette courte liste d'actions ne nous a pas donné grand-chose et a conduit à une «impasse», si nous utilisons l'analogie avec la recherche de chemins. Par conséquent, nous répétons le processus pour l'étape suivante. Nous choisissons de jouer à Forest. Cela supprime également la possibilité de «jouer à Forest» et de «jouer à Swamp», et ouvre comme une prochaine étape potentielle (et unique) «toucher la forêt». Cela nous donne 1 point de mana vert, qui à son tour ouvre la troisième étape - "appelez" Elven Mystic "."

 1. Jouez "Swamp" (résultat: "Swamp" quitte la main et entre dans le jeu)
            1.1 Touchez «Swamp» (résultat: nous avons touché «Swamp», +1 mana noir est disponible)
                        Aucune action restante - FIN
2. Jouez à "Forest" (résultat: "Forest" quitte la main et entre dans le jeu)
            2.1 Touchez «Forêt» (résultat: nous avons touché «Marais», +1 de mana vert est disponible)
                        2.1.1 Appelez "Elven Mystic" (résultat: "Elven Mystic" dans le jeu, -1 mana vert est disponible)
                                    Aucune action restante - FIN 

Maintenant, nous avons étudié toutes les actions et actions possibles résultant de ces actions, en trouvant un plan qui nous permet d'invoquer la créature: "jouer la forêt", "toucher la forêt", "appeler le" Elven Mystic "".

De toute évidence, ceci est un exemple très simplifié, et généralement vous devez choisir le meilleurun plan, et pas seulement un plan qui satisfait certains critères (par exemple, «invoquer une créature»). Vous pouvez généralement évaluer les plans potentiels en fonction du résultat final ou des avantages cumulatifs de l'utilisation du plan. Par exemple, vous pouvez vous donner 1 point pour une carte terrestre aménagée et 3 points pour appeler une créature. "Jouer" Swamp "" sera un plan court donnant 1 point, et le plan "jouer" Forest "→ toucher" Forest "→ appeler" Elven Mystic "" donne 4 points, 1 pour le sol et 3 pour la créature. Ce sera le plan le plus rentable disponible, vous devriez donc le choisir si nous avons nommé de tels points.

Ci-dessus, nous avons montré comment la planification fonctionne dans le même mouvement Magic: The Gathering, mais elle peut également être appliquée à des actions dans une série de mouvements (par exemple, "déplacer un pion pour donner de la place au développement de l'évêque" aux échecs ou "courir à couvert pour une unité"). pourrait tirer le tour suivant, en étant en sécurité "dans XCOM) ou à la stratégie générale de tout le jeu (par exemple," construire des pylônes pour tous les autres bâtiments protoss "dans Starcraft, ou" boire une potion Fortify Health avant d'attaquer l'ennemi "dans Skyrim).

Planification améliorée

Parfois, il y a trop d'actions possibles à chaque étape, et évaluer chaque option est déraisonnable. Revenons à l'exemple de Magic: The Gathering - imaginez que nous avons plusieurs créatures en main, de nombreux terrains ont déjà été joués, afin que nous puissions appeler n'importe quelle créature, plusieurs créatures avec leurs capacités jouées, et il y a quelques autres cartes de terrain en main - le nombre de permutations la terre, l'utilisation des terres, l'invocation de créatures et l'utilisation des capacités des créatures peuvent représenter des milliers, voire des dizaines de milliers. Heureusement, il existe deux façons de résoudre ce problème.

Le premier est appelé chaînage arrière"(" Aller-retour "). Au lieu de vérifier toutes les actions et leurs résultats, nous pouvons commencer par chacun des résultats finaux souhaités et voir si nous pouvons trouver un chemin direct vers eux. Vous pouvez comparer cela en essayant d'atteindre une feuille spécifique dans un arbre - c'est beaucoup plus logique partir de cette feuille et revenir en arrière, en établissant un itinéraire le long du tronc (et cet itinéraire nous pouvons ensuite aller dans l'ordre inverse), que de partir du tronc et d'essayer de deviner quelle branche choisir à chaque étape. Si vous partez de la fin et allez dans la direction opposée, puis créé e plan sera beaucoup plus rapide et plus facile.

Par exemple, s'il reste 1 point de vie à l'ennemi, il peut être utile d'essayer de trouver un plan pour «infliger 1 ou plusieurs points de dégâts directs à l'ennemi». Notre système sait que pour atteindre cet objectif, il doit lancer un sort de dégâts directs, ce qui signifie qu'il doit être entre nos mains et nous avons besoin de suffisamment de mana pour le prononcer. Cela signifie que nous devons toucher suffisamment de terrain pour recevoir ce mana, ce qui peut vous obliger à jouer une carte de terrain supplémentaire.

Une autre façon consiste à rechercher par la première meilleure correspondance. Au lieu de parcourir toutes les permutations pendant une longue période, nous mesurons la qualité de chaque plan partiel (similaire à la façon dont nous avons choisi les options de plan ci-dessus) et calculons le plus beau à chaque fois. Souvent, cela vous permet de créer un plan optimal, ou du moins assez bon, sans avoir à considérer chaque réarrangement possible des plans. A * est une variante de la recherche du premier meilleur match - il explore d'abord les itinéraires les plus prometteurs, de sorte qu'il peut généralement trouver le chemin vers l'objectif sans avoir à monter trop loin dans d'autres directions.

Une option de recherche intéressante et de plus en plus populaire pour la première meilleure correspondance est la recherche d'arbre Monte Carlo .. Au lieu de deviner quels plans sont meilleurs que d'autres lors du choix de chaque action subséquente, cette méthode choisit des actions subséquentes aléatoires à chaque étape jusqu'à ce qu'elle atteigne la fin où aucune action n'est plus possible - probablement parce que le plan hypothétique a conduit à un état de victoire ou de perte. - et utilise ce résultat pour donner plus ou moins de poids aux options sélectionnées précédentes. Si le processus est répété plusieurs fois, la méthode peut créer une bonne évaluation de la meilleure étape suivante, même si la situation change (par exemple, si l'ennemi essaie de contrecarrer nos plans).

Enfin, aucune discussion sur la planification dans les jeux ne serait complète sans mentionner la planification des actions basée sur les objectifs(Planification des actions axées sur les objectifs, GOAP). Il s'agit d'une technique largement utilisée et largement discutée, mais si vous ignorez quelques détails d'implémentation spécifiques, il s'agit essentiellement d'un planificateur aller-retour qui commence par un objectif et essaie de sélectionner une action menant à cet objectif, ou, plus probablement, une liste d'actions qui mène à au but. Par exemple, si le but était de «tuer le joueur» et que le joueur était à couvert, alors le plan pourrait être: «Fumer le joueur avec une grenade» → «Sortir une arme» → «Attaquer».

Il y a généralement plusieurs objectifs, et chacun a sa propre priorité. Si les objectifs avec la priorité la plus élevée ne peuvent pas être atteints, par exemple, aucun ensemble d'actions ne peut former le plan "Tuer le joueur" parce que le joueur n'est pas visible, alors le système revient aux objectifs avec des priorités plus faibles, par exemple, "Patrouille" ou "Garde sur place".

Formation et adaptation

Au début de l'article, nous avons mentionné que l'IA de jeu n'utilise généralement pas le «machine learning» car elle n'est généralement pas adaptée au contrôle en temps réel d'agents intelligents dans le monde du jeu. Cependant, cela ne signifie pas que nous ne pouvons pas emprunter quelque chose dans ce domaine où cela a du sens. Nous pourrions avoir besoin d'un adversaire informatique dans le jeu de tir pour trouver les meilleurs endroits où se déplacer pour obtenir le plus de victimes. Ou nous pourrions vouloir l'adversaire dans un jeu de combat. par exemple, dans Tekken ou Street Fighter, il a appris à reconnaître un joueur utilisant les mêmes combos pour commencer à les bloquer, forçant le joueur à utiliser des tactiques différentes. Autrement dit, il y a des moments où un certain pourcentage de l'apprentissage automatique est utile.

Statistiques et probabilités

Avant de passer à des exemples plus complexes, il convient de déterminer jusqu'où nous pouvons aller en prenant simplement des mesures et en utilisant ces données pour prendre des décisions. Par exemple, disons que nous avons un jeu dans le genre de la stratégie en temps réel, et nous devons comprendre si le joueur commencera à se précipiter dans les premières minutes pour décider de construire plus de défense. Nous pouvons extrapoler le comportement antérieur du joueur pour comprendre quel pourrait être le comportement futur. Au début, nous ne disposons pas de données extrapolables, mais chaque fois que l'IA joue contre un ennemi vivant, elle peut enregistrer l'heure de la première attaque. Après quelques matchs, ce temps peut être moyenné, et nous obtiendrons une assez bonne approximation du temps d'attaque du joueur à l'avenir.

Le problème avec la moyenne simple est qu'elle converge généralement avec le temps au centre. Par conséquent, si un joueur a utilisé la stratégie rush les 20 premières fois et que les 20 prochaines fois sont passés à une stratégie beaucoup plus lente, la valeur moyenne sera quelque part au milieu, ce qui ne nous donnera aucune information utile. Une façon d'améliorer les données consiste à utiliser une fenêtre de calcul de moyenne simple qui ne prend en compte que les 20 derniers points de données.

Une approche similaire peut être utilisée pour évaluer la probabilité de certaines actions, en supposant que les préférences précédentes du joueur continueront à l'avenir. Par exemple, si un joueur a attaqué cinq fois avec une boule de feu, deux fois avec la foudre et au corps à corps une seule fois, il préférerait probablement une boule de feu 5 fois sur 8. En extrapolant à partir de ces données, nous pouvons voir que la probabilité d'utiliser une arme est: Fireball = 62,5%, Lightning = 25% Melee = 12,5%. Nos personnages de l'IA se rendront compte qu'ils feraient mieux de trouver une armure ignifuge!

Une autre méthode intéressante consiste à utiliser le Naive Bayes Classifier pour étudier de grands volumes de données d'entrée afin de classer la situation actuelle afin que l'agent AI puisse répondre en conséquence. Les classificateurs bayésiens sont probablement mieux connus pour leur utilisation dans les filtres de courrier indésirable, où ils évaluent les mots dans le courrier électronique, les comparent avec les mots qui ont été le plus souvent trouvés dans le spam et les messages normaux dans le passé. Sur la base de ces calculs, ils décident de la probabilité que le dernier message reçu soit du spam. Nous pouvons faire quelque chose de similaire, mais avec moins d'entrée. En enregistrant toutes les informations utiles observables (par exemple, les unités ennemies créées,sorts utilisés ou technologies de recherche) et en suivant la situation qui en résulte (guerre / paix, stratégie de rush / stratégie de défense, etc.), nous pouvons sélectionner le comportement approprié en fonction de cela.

L'utilisation de toutes ces techniques d'enseignement peut être suffisante et souvent et de préférence appliquée aux données collectées pendant les tests de jeu avant la sortie du jeu. Cela permet à l'IA de s'adapter aux différentes stratégies utilisées par les testeurs de jeu et de ne pas changer après la sortie du jeu. Une IA qui s'adapte à un joueur après la sortie d'un jeu peut devenir trop prévisible ou même trop complexe pour être vaincue.

Adaptation facile basée sur le poids

Allons plus loin. Au lieu d'utiliser simplement les données d'entrée pour choisir entre des stratégies prédéfinies discrètes, vous pouvez modifier l'ensemble de valeurs qui influencent la prise de décision. Si nous comprenons bien le monde du jeu et les règles du jeu, alors nous pouvons faire ce qui suit:

• ( );
• «» ;
• .

Imaginez un agent informatique qui peut sélectionner des pièces sur une carte dans un jeu de tir à la première personne. Chaque pièce a un poids qui détermine l'opportunité de visiter cette pièce. Au départ, toutes les chambres ont la même signification. Lors du choix d'une pièce, l'IA la sélectionne au hasard, mais avec l'influence de ces poids. Imaginez maintenant que lorsqu'un agent informatique est tué, il se souvienne dans quelle pièce cela se produit et réduit son poids afin qu'il soit moins susceptible d'y retourner à l'avenir. De même, imaginez qu'un agent informatique a commis un meurtre. Ensuite, il peut augmenter le poids de la pièce dans laquelle il se trouve afin de le soulever dans la liste des préférences. Donc, si une pièce devient particulièrement dangereuse pour le joueur IA, alors il commence à l'éviter à l'avenir, et si une autre pièce permet à l'IA d'obtenir beaucoup de tueries,puis il y retournera.

Modèles Markov

Et si nous voulions utiliser les données que nous avons collectées pour faire des prévisions? Par exemple, si nous enregistrons chaque pièce dans laquelle nous voyons un joueur pendant une certaine période de temps, nous pouvons raisonnablement prédire dans quelle pièce il peut passer. En suivant à la fois la pièce actuelle dans laquelle se trouve le joueur et la précédente, et en enregistrant ces paires de valeurs, nous pouvons calculer la fréquence à laquelle chacune des situations précédentes mène à la situation suivante et utiliser ces connaissances pour les prévisions.

Imaginez qu'il y ait trois salles - rouge, verte et bleue, et que pendant la session de jeu nous avons reçu de telles observations:

La première pièce dans laquelle le joueur est vu	Total des observations	Chambre suivante	Combien de fois vu	Pourcentage
Rouge	10	Rouge	2	20%
		Vert	7	70%
		Bleu	1	10%
Vert	10	Rouge	3	30%
		Vert	5	50%
		Bleu	2	20%
Bleu	8	Rouge	6	75%
		Vert	2	25%
		Bleu	0	0%

Le nombre de détections dans chacune des chambres est assez uniforme, donc cela ne nous permet pas de savoir laquelle des chambres peut être un bon endroit pour une embuscade. Les données peuvent être déformées par le fait que les joueurs apparaissent uniformément sur la carte, avec une probabilité égale d'apparaître dans l'une de ces trois salles. Mais les données sur la visite de la pièce voisine peuvent être utiles et nous aider à prévoir le mouvement du joueur sur la carte.

Nous pouvons immédiatement remarquer que la salle verte est très attrayante pour les joueurs - la plupart des joueurs de la salle rouge sont passés au vert, et 50% des joueurs vus dans la salle verte restent là lors du prochain contrôle. On peut également remarquer que la chambre bleue est un endroit plutôt peu attrayant. Les gens passent rarement des pièces rouges ou vertes au bleu et il semble que personne n'aime s'y attarder longtemps.

Mais les données nous disent quelque chose de plus spécifique - elles disent que lorsqu'un joueur est dans la salle bleue, puis la suivant, il est plus susceptible de choisir le rouge plutôt que le vert. Malgré le fait que la salle verte est un endroit beaucoup plus populaire que la rouge, la tendance est légèrement opposée si le joueur est dans la salle bleue. Il semble que l'état suivant (c'est-à-dire la pièce dans laquelle il décide d'aller plus loin) dépend de l'état précédent (c'est-à-dire la pièce dans laquelle il se trouve maintenant), donc ces données nous permettent de créer de meilleures prévisions sur le comportement des joueurs qu'avec un comptage d'observation indépendant.

Cette idée que nous pouvons utiliser la connaissance de l'état précédent pour prédire l'état futur s'appelle le modèle de Markov, et des exemples similaires dans lesquels nous avons mesuré avec précision des événements (par exemple, "dans quelle pièce le joueur est") sont appelés chaînes de Markov. Puisqu'ils représentent la probabilité d'une transition entre états successifs, ils sont souvent représentés graphiquement sous la forme d'une machine à états finis, à proximité de chaque transition dont sa probabilité est indiquée. Auparavant, nous utilisions une machine à états pour représenter l'état de comportement dans lequel se trouve l'agent, mais ce concept peut être étendu à toutes sortes d'états, qu'ils soient associés ou non à l'agent. Dans notre cas, les États indiquent les chambres occupées par l'agent. Cela ressemblera à ceci:


Il s'agit d'une approche simple pour indiquer la probabilité relative de transition vers différents états, ce qui donne à l'IA la capacité de prédire l'état suivant. Mais nous pouvons aller plus loin en créant un système qui envisage l'avenir en deux ou plusieurs étapes.

Si un joueur a été repéré dans la salle verte, nous utiliserons des données qui nous indiquent qu'il y a 50% de chances qu'il soit toujours dans la salle verte lors de la prochaine observation. Mais quelle est la probabilité qu'il y reste pour la troisième fois? Ce n'est pas seulement la probabilité qu'il reste dans la salle verte pour deux observations (50% * 50% = 25%), mais aussi la probabilité qu'il le quitte et revienne. Voici un nouveau tableau avec des valeurs précédentes appliquées à trois observations: une actuelle et deux hypothétiques dans le futur.

Observation 1	Observation hypothétique 2		3
		30%		20%	6%
				70%	21%
				10%	3%
		50%		30%	15%
				50%	25%
				20%	10%
		20%		75%	15%
				25%	5%
				0%	0%
				:	100%

Ici, nous voyons que la probabilité de voir un joueur dans la salle verte après 2 observations est de 51% - 21% de ce qu'il viendra de la salle rouge, 5% de ce que nous voyons le joueur visiter la salle bleue et 25% de ce qu'il est tout le temps restera dans la salle verte.

Un tableau n'est qu'un indice visuel; une procédure ne nécessite qu'une multiplication des probabilités à chaque étape. Cela signifie que nous pouvons regarder loin dans l'avenir, mais avec une mise en garde importante: nous faisons l'hypothèse que la probabilité d'entrer dans une pièce dépend entièrement de la pièce dans laquelle nous nous trouvons en ce moment. Cette idée que l'état futur ne dépend que du courant est appelée la propriété Markov. Bien qu'il nous permette d'utiliser des outils puissants tels que les chaînes de Markov, ce n'est généralement qu'une approximation. Les joueurs peuvent décider de visiter les salles en fonction d'autres facteurs, tels que leur niveau de santé et la quantité de munitions, et comme nous n'enregistrons pas ces informations dans le cadre de la condition, nos prévisions seront moins précises.

N grammes

Revenons à notre exemple avec la reconnaissance combinée dans un jeu de combat. Il s'agit d'une situation similaire dans laquelle nous voulons prédire l'état futur en fonction du passé (afin de décider comment bloquer une attaque ou l'esquiver), mais au lieu d'étudier un seul état ou événement, nous considérerons des séquences d' événements qui créent un mouvement combo.

Une façon de procéder consiste à enregistrer chaque entrée de joueur (par exemple, coup de pied , main ou bloc ) dans le tampon et à écrire le tampon entier en tant qu'événement. Imaginez qu'un joueur appuie constamment sur un coup de pied , un coup de pied , un coup de pied pour utiliser l'attaque « Death Cancer » ", et le système d'IA enregistre toutes les entrées du joueur dans le tampon et se souvient des 3 dernières entrées utilisées à chaque étape.

Entrer	Une séquence d'entrée existante	Nouvelle mémoire d'entrée
Coup de pied	Coup de pied	non
Coup de main	Kick, Kick	non
Coup de pied	Kick, Kick, Kick	Kick, Kick, Kick
Coup de pied	Kick, Kick, Kick, Kick	Kick, Kick, Kick
Coup de main	Coup de pied, coup de pied, coup de pied, coup de pied, coup de pied	Kick, Kick, Kick
Bloquer	Coup de pied, coup de pied, coup de pied, coup de pied, coup de pied, bloc	Kick, Kick, Block
Coup de pied	Coup, Coup, Coup, Coup, Coup, Coup, Bloc, Coup	Coup de pied, blocage, coup de pied
Coup de pied	Coup, Coup, Coup, Coup, Coup, Coup, Bloc, Coup, Coup	Bloquer, botter, botter
Coup de main	, , , , , , , ,	, ,

(En gras, le joueur effectue l'attaque «Superbuck of Death».)

Vous pouvez regarder toutes ces fois où le joueur a choisi un coup de pied dans le passé , suivi d'un autre coup de pied , et notez que la prochaine entrée est toujours un coup de pied . Cela permet à l'agent de l'IA de prédire que si un joueur vient de choisir un coup de pied, suivi d'un coup de pied, il sélectionnera très probablement un coup de pied suivant , lançant ainsi le Death Superkulak . Cela permet à l'IA de décider de choisir une action qui contrecarre ce coup, comme bloquer ou esquiver.

De telles 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 de 3 grammes, également appelés trigrammes, c'est-à-dire que les 2 premiers éléments sont utilisés pour prédire le troisième. Dans le 5 grammes, le cinquième est prévu pour les 4 premiers éléments, et ainsi de suite.

Les développeurs doivent soigneusement choisir la taille des N-grammes (parfois appelée commande). Plus le nombre est petit, moins la mémoire est nécessaire, car plus le nombre de permutations autorisées est petit, mais moins l'historique est sauvegardé, ce qui signifie que le contexte est perdu. Par exemple, un 2 grammes (également appelé «bigramme») contiendra des enregistrements de coups de pied , coups de pied et des enregistrements de coups de pied , coups de pied , mais ne peut pas enregistrer un coup de pied .coup de pied , coup de main , par conséquent, ne peut pas suivre ce combo.

En revanche, plus la commande est grande, plus la mémoire est importante et le système sera probablement plus difficile à entraîner, car nous aurons beaucoup plus de permutations possibles, ce qui signifie que nous ne pourrons jamais nous rencontrer deux fois de la même manière. Par exemple, s'il y a trois entrées possibles ( coup de pied , main et bloc ) et que nous utilisons un 10 grammes, il y aura près de 60 000 permutations différentes.

Le modèle de bigramme est essentiellement une chaîne triviale de Markov - chaque paire «état futur / état actuel» est un bigramme et nous pouvons prédire le deuxième état en fonction du premier. Les trigrammes et les grands N-grammes peuvent également être considérés comme des chaînes de Markov, où tous les éléments du N-gramme, à l'exception du dernier, forment le premier état, et le dernier élément est le deuxième état. Dans notre exemple de jeu de combat, la probabilité de transition de l'état de coups de pied et de coups de pied à l'état de coups de pied, puis de coups de pied est présentée. En percevant plusieurs éléments de l'historique d'entrée comme un seul élément, nous transformons essentiellement la séquence d'entrée en un fragment de l'état, ce qui nous donne une propriété Markov, nous permettant d'utiliser des chaînes de Markov pour prédire l'entrée suivante, c'est-à-dire en devinant quel mouvement combo suivra.

Représentation des connaissances

Nous avons discuté de plusieurs façons de prendre des décisions, de créer des plans et des prévisions, et toutes sont basées sur les observations de l’agent sur l’état du monde. Mais comment observer efficacement l'ensemble du monde du jeu? Ci-dessus, nous avons vu que la façon de représenter la géométrie du monde affecte grandement le mouvement le long de celui-ci, il est donc facile d'imaginer que cela est vrai pour d'autres aspects de l'IA du jeu. Comment collecter et organiser toutes les informations nécessaires de manière optimale (afin qu'elles soient souvent mises à jour et accessibles à de nombreux agents) et pratiques (afin que les informations puissent être facilement utilisées dans le processus décisionnel)? Comment transformer des données simples en informations ou en connaissances ? Pour différents jeux, les solutions peuvent être différentes, mais il existe plusieurs approches les plus populaires.

Tags / Tags

Parfois, nous avons déjà une énorme quantité de données utiles, et la seule chose dont nous avons besoin est un bon moyen de les classer et de les rechercher. Par exemple, dans le monde du jeu, il peut y avoir de nombreux objets, et certains d'entre eux sont un bon abri contre les balles ennemies. Ou, par exemple, nous avons un tas de dialogues audio enregistrés qui sont applicables dans des situations spécifiques, et nous avons besoin d'un moyen de les comprendre rapidement. L'étape évidente consiste à ajouter une petite information supplémentaire que vous pouvez utiliser pour effectuer une recherche. Ces fragments sont appelés balises ou balises.

Revenons à l'exemple du refuge; dans le monde du jeu, il peut y avoir un tas d'objets - des boîtes, des tonneaux, des tas d'herbe, des grillages. Certains d'entre eux conviennent à l'abri, par exemple, des boîtes et des barils, d'autres non. Par conséquent, lorsque notre agent effectue l'action «Déplacer vers un abri», il doit rechercher des objets à proximité et identifier les candidats appropriés. Il ne peut pas simplement rechercher par nom - peut-être que le jeu a Crate_01, Crate_02, jusqu'à Crate_27, et nous ne voulons pas chercher tous ces noms dans le code. Nous ne voulons pas ajouter un autre nom au code chaque fois que l'artiste crée une nouvelle variation de la boîte ou du baril. Au lieu de cela, vous pouvez rechercher n'importe quel nom contenant le mot "Crate", mais un jour, un artiste peut ajouter "Broken_Crate" avec un énorme trou, inadapté comme abri.

Par conséquent, au lieu de cela, nous allons créer une balise «COVER» et demander aux artistes et aux designers d'attacher cette balise à tous les objets qui peuvent être utilisés comme abri. S'ils ajoutent une balise à tous les barils et boîtes (entières), alors la procédure AI n'aura qu'à trouver des objets avec cette balise, et elle saura que les objets conviennent à cet effet. La balise fonctionnera même si les objets sont renommés ultérieurement, et elle peut être ajoutée aux objets à l'avenir sans apporter de modifications inutiles au code.

Dans le code, les balises sont généralement représentées sous forme de chaînes, mais si toutes les balises utilisées sont connues, vous pouvez convertir des chaînes en nombres uniques pour économiser de l'espace et accélérer la recherche. Dans certains moteurs, les balises sont des fonctionnalités intégrées, par exemple, dans Unity et dans Unreal Engine 4 , par conséquent, il suffit de déterminer le choix des balises et de les utiliser conformément à leur destination.

Objets intelligents

Les balises sont un moyen d'ajouter des informations supplémentaires à l'environnement de l'agent, pour l'aider à comprendre les options disponibles, afin que les demandes comme «Trouvez-moi tous les endroits les plus proches où se cacher» ou «Trouvez-moi tous les ennemis à proximité qui peuvent lancer des sorts» soient exécutées efficacement et avec un minimum d'effort travaillé pour de nouvelles ressources de jeu. Mais parfois, les balises ne contiennent pas suffisamment d'informations pour leur utilisation complète.

Imaginez un simulateur d'une ville médiévale dans laquelle les aventuriers errent où ils veulent, si nécessaire, s'entraînent, se battent et se détendent. Nous pouvons organiser des sites d'entraînement dans différentes parties de la ville et leur attribuer le tag "FORMATION" afin que les personnages puissent facilement trouver un lieu d'entraînement. Mais imaginons que l'un d'eux soit un champ de tir pour les archers, et l'autre une école de sorciers. Dans chacun de ces cas, nous devons montrer notre animation, car sous le nom général de "formation", ils représentent différentes actions, et tous les aventuriers ne sont pas intéressés par les deux types de formation. Vous pouvez aller encore plus loin et créer des tags ARCHERY-TRAINING et MAGIC-TRAINING, séparer les procédures d'entraînement les unes des autres et les intégrer dans chaque animation différente. Cela vous aidera à résoudre le problème. Mais imaginezque les concepteurs déclareront plus tard "Ayons une école Robin Hood où vous pourrez apprendre le tir à l'arc et le combat à l'épée"! Et puis, lorsque nous ajoutons le combat à l'épée, ils demandent la création de l'Académie des sorts et du combat à l'épée de Gandalf. En conséquence, nous devrons stocker plusieurs balises pour chaque endroit et rechercher différentes animations en fonction de l'aspect de la formation dont le personnage a besoin, etc.

Une autre façon consiste à stocker des informations directement dans l'objet ainsi que l'influence qu'elle a sur le joueur, afin que l'acteur IA puisse simplement lister les options possibles et choisir parmi celles-ci en fonction des besoins de l'agent. Après cela, il peut se déplacer à l'endroit approprié, effectuer les animations appropriées (ou toute autre action obligatoire), comme indiqué dans l'objet, et recevoir la récompense appropriée.

	Animation en cours	Résultat utilisateur
Champ de tir	Flèche de tir	+10 compétence tir à l'arc
École de magie	Duel à l'épée	+10 Compétence Épées
École Robin Hood	Flèche de tir	+15 compétence tir à l'arc
	Duel à l'épée	+8 Compétence Épées
Académie Gandalf	Duel à l'épée	+5 Compétence Épée
	Lancer un sort	+10 compétence magique

Le personnage archer à côté de ces 4 emplacements aura 6 options, dont 4 ne lui sont pas applicables s'il n'utilise pas d'épée ou de magie. En comparant le résultat dans ce cas avec une amélioration des compétences, plutôt qu'un nom ou une étiquette, nous pouvons facilement élargir les possibilités du monde avec de nouveaux comportements. Vous pouvez ajouter des hôtels pour vous reposer et satisfaire votre faim. Vous pouvez laisser les personnages aller à la bibliothèque et découvrir les sorts et les techniques avancées de tir à l'arc.

Le nom de l'objet	Animation en cours	Résultat final
Hôtel	Acheter	-10 à la faim
Hôtel	Dormir	-50 à la fatigue
La bibliothèque	Lire le livre	+10 Compétence de lanceur de sorts
La bibliothèque	Lire le livre	+5 Compétence de tir à l'arc

Si nous avons déjà le comportement "pratique du tir à l'arc", alors même si nous marquons la bibliothèque comme un endroit pour la FORMATION À L'ARCHERIE, alors nous avons très probablement besoin d'un cas spécial pour traiter l'animation du livre lu au lieu de l'animation habituelle de combat à l'épée. Ce système nous donne plus de flexibilité en déplaçant ces associations vers des données et en stockant des données dans le monde.

L'existence d'objets ou de lieux - bibliothèques, hôtels ou écoles - nous renseigne sur les services qu'ils proposent, sur le personnage qui peut les obtenir, vous permet d'utiliser un petit nombre d'animations. La capacité de prendre des décisions simples sur les résultats vous permet de créer une variété de comportements intéressants. Au lieu d'attendre passivement une demande, ces objets peuvent fournir une mine d'informations sur comment et pourquoi les utiliser.

Courbes de réaction

Il y a souvent une situation où une partie de l'état du monde peut être mesurée comme une valeur continue. Exemples:

• Le «pourcentage de santé» varie généralement de 0 (mort) à 100 (absolument sain)
• La "distance à l'ennemi le plus proche" varie de 0 à une valeur positive arbitraire

De plus, le jeu peut avoir un aspect du système AI, nécessitant la saisie de valeurs continues dans un autre intervalle. Par exemple, pour prendre la décision de fuir, un système d’évaluation de l’utilité peut exiger à la fois la distance de l’ennemi le plus proche et la santé actuelle du personnage.

Cependant, le système ne peut pas simplement additionner deux valeurs de l'état du monde afin d'obtenir un certain niveau de «sécurité», car ces deux unités de mesure sont incomparables - les systèmes supposeront qu'un personnage presque mort à 200 mètres de l'ennemi est dans la même sécurité qu'il est absolument sain. personnage à 100 mètres de l'ennemi. De plus, bien que la valeur en pourcentage de la santé au sens large soit linéaire, la distance ne l'est pas - la différence de distance par rapport à l'ennemi 200 et 190 mètres est moins significative que la différence entre 10 mètres et zéro.

Idéalement, nous avons besoin d'une solution qui prend deux indicateurs et les convertit en intervalles similaires afin qu'ils puissent être comparés directement. Et nous avons besoin que les concepteurs puissent contrôler la façon dont ces transformations sont calculées pour contrôler l'importance relative de chaque valeur. À cet effet, des courbes de réaction (courbes de réponse) sont utilisées.

La façon la plus simple d'expliquer la courbe de réaction est un graphique avec une entrée le long de l'axe X, des valeurs arbitraires, par exemple, «la distance à l'ennemi le plus proche» et une sortie le long de l'axe Y (généralement une valeur normalisée dans la plage de 0,0 à 1,0). Une ligne ou une courbe sur le graphique détermine la liaison de l'entrée à la sortie normalisée, et les concepteurs ajustent ces lignes pour obtenir le comportement dont ils ont besoin.

Pour calculer le niveau de "sécurité", vous pouvez maintenir la linéarité des valeurs de pourcentage de santé - par exemple, 10% de santé en plus - c'est généralement bon lorsque le personnage est gravement blessé et lorsqu'il se blesse facilement. Par conséquent, nous attribuons ces valeurs à l'intervalle de 0 à 1 de manière simple:


La distance par rapport à l'ennemi le plus proche est légèrement différente, donc nous ne sommes pas du tout gênés par les ennemis au-delà d'une certaine distance (disons 50 mètres), et nous sommes beaucoup plus intéressés par les différences à courte distance qu'à longue distance.

Ici, nous voyons que la sortie de «sécurité» pour les ennemis à 40 et 50 mètres est presque la même: 0,96 et 1,0.


Cependant, il y a une différence beaucoup plus grande entre l'ennemi à 15 mètres (environ 0,5) et l'ennemi à 5 mètres (environ 0,2). Un tel calendrier reflète mieux l'importance pour l'ennemi de se rapprocher.

En normalisant ces deux valeurs dans la plage de 0 à 1, nous pouvons calculer la valeur de sécurité totale comme la moyenne de ces deux valeurs d'entrée. Un personnage avec 20% de santé et un ennemi à 50 mètres auront un score de sécurité de 0,6. Un personnage avec 75% de santé et un ennemi à seulement 5 mètres auront un score de sécurité de 0,47. Un personnage gravement blessé avec 10% de santé et un ennemi de 5 mètres auront un indice de sécurité de seulement 0,145.

Les éléments suivants doivent être pris en compte ici:

• — , .
• — , , 50 — , , .
• , ( ) . , — , Unity AnimationCurve , .

Blackboards

Souvent, nous nous trouvons dans une situation où l'IA de l'agent doit commencer à surveiller les connaissances et les informations obtenues au cours du jeu afin qu'elles puissent être utilisées dans la prise de décision. Par exemple, un agent peut avoir besoin de se souvenir du dernier personnage qu'il a attaqué afin de se concentrer sur les attaques de ce personnage pendant une courte période. Ou il doit se rappeler combien de temps s'est écoulé après avoir entendu un bruit, de sorte qu'après un certain temps, il cesse de chercher ses raisons et retourne à ses études précédentes. Très souvent, le système d'enregistrement des données est fortement séparé du système de lecture des données, il doit donc être facilement accessible depuis l'agent et ne pas être intégré directement dans divers systèmes d'IA. La lecture peut avoir lieu un certain temps après l'écriture, les données doivent donc être stockées quelque part,afin qu'ils puissent être récupérés plus tard (et non calculés sur demande, ce qui peut ne pas être possible).

Dans un système d'IA codé en dur, la solution peut être d'ajouter les variables nécessaires dans le processus du besoin. Ces variables se rapportent à des instances du personnage ou de l'agent, soit en s'intégrant directement dans celui-ci, soit en créant une structure / classe distincte pour stocker ces informations. Les procédures d'IA peuvent être adaptées pour lire et écrire ces données. Dans un système simple, cela fonctionnera bien, mais à mesure que de plus amples informations sont ajoutées, elles deviennent lourdes et nécessitent généralement de reconstruire le jeu à chaque fois.

Une meilleure approche consiste à transformer l'entrepôt de données en une structure qui permet aux systèmes de lire et d'écrire des données arbitraires. Cette solution vous permet d'ajouter de nouvelles variables sans avoir besoin de changer la structure des données, offrant ainsi la possibilité d'augmenter le nombre de modifications qui peuvent être apportées à partir des fichiers de données et des scripts sans avoir besoin de réassemblage. Si chaque agent stocke simplement une liste de paires clé-valeur, chacune étant un élément de connaissance distinct, différents systèmes d'IA peuvent coopérer en ajoutant et en lisant ces informations si nécessaire.

Dans le développement de l'IA, de telles approches sont appelées «tableaux noirs» («tableaux noirs»), car chaque participant - dans notre cas, les procédures d'IA (par exemple, la perception, trouver un chemin et prendre des décisions) - peut écrire sur le «tableau noir», lu à partir duquel les données pour l'exécution de leur tâche peuvent être n'importe quel autre participant. Vous pouvez l'imaginer comme une équipe d'experts réunis autour du tableau et écrire quelque chose d'utile que vous devez partager avec le groupe. En même temps, ils peuvent lire les notes précédentes de leurs collègues jusqu'à ce qu'ils parviennent à une décision ou à un plan conjoint. Une liste codée en dur de variables communes dans le code est parfois appelée «tableau noir statique» (car les éléments dans lesquels les informations sont stockées sont constants pendant l'exécution du programme), et une liste arbitraire de paires clé-valeur est souvent appelée «tableau noir dynamique».Mais ils sont utilisés à peu près de la même manière - comme un lien intermédiaire entre les parties du système d'IA.

Dans l'IA traditionnelle, l'accent est généralement mis sur la collaboration de différents systèmes pour la prise de décision conjointe, mais relativement peu de systèmes sont présents dans l'IA de jeu. Cependant, un certain degré de coopération peut encore exister. Imaginez ce qui suit dans un RPG d'action:

• Le système de «perception» balaye régulièrement la zone et écrit les entrées suivantes dans le tableau noir:
  
  • Ennemi le plus proche: gobelin 412
    
  • "Distance à l'ennemi le plus proche": 35,0
    
  • "Ami proche": "Guerrier 43"
    
  • «Distance à l'ami le plus proche»: 55,4
    
  • "Heure du dernier bruit remarqué": 12h45
• Des systèmes comme un système de combat peuvent enregistrer des événements clés sur un tableau noir, par exemple:
  
  • Dernier dommage subi: 12h34

Beaucoup de ces données peuvent sembler redondantes - au final, vous pouvez toujours obtenir la distance de l'ennemi le plus proche, en sachant simplement qui est cet ennemi et en répondant à une demande de position. Mais lorsqu'elle est répétée plusieurs fois par image, afin de décider si un agent menace ou non quelque chose, cela devient une opération potentiellement lente, surtout si elle doit effectuer une requête spatiale pour déterminer l'ennemi le plus proche. Et les horodatages du «dernier bruit remarqué» ou du «dernier dommage reçu» ne pourront toujours pas être instantanés - vous devez enregistrer l'heure à laquelle ces événements ont eu lieu, et le tableau noir est un endroit pratique pour cela.

Unreal Engine 4 utilise un système de tableau noir dynamique pour stocker les données transmises par les arbres de comportement. Grâce à cet objet de données commun, les concepteurs peuvent facilement écrire de nouvelles valeurs sur le tableau noir en fonction de leurs plans (scripts visuels), et l'arbre de comportement peut plus tard lire ces valeurs pour sélectionner le comportement, et tout cela ne nécessite pas de recompilation du moteur.

Cartes d'influence

La tâche standard dans l'IA est de décider où l'agent doit se déplacer. Dans le jeu de tir, nous pouvons choisir l'action "Déplacer vers un abri", mais comment décider où se trouve l'abri dans les conditions de déplacement des ennemis? Comme pour l'action "Escape" - où est le moyen le plus sûr de s'échapper? Ou dans RTS, nous pouvons avoir besoin des troupes pour attaquer un point faible dans la défense de l'ennemi - comment pouvons-nous déterminer où ce point faible est?

Toutes ces questions peuvent être considérées comme des tâches géographiques, car nous posons une question sur la géométrie et la forme de l'environnement et la position des entités dans celui-ci. Dans notre jeu, toutes ces données sont probablement déjà disponibles, mais leur donner du sens n'est pas une tâche facile. Par exemple, si nous voulons trouver un point faible dans la défense de l'ennemi, il ne suffit pas de choisir simplement la position du bâtiment ou de la fortification le plus faible s'ils ont deux puissants systèmes de canons sur les flancs. Il nous faut un moyen de prendre en compte le territoire et de mieux analyser la situation.

C'est à cela que sert la structure de données «carte d'influence». Il décrit «l'influence» qu'une entité peut avoir sur la zone qui l'entoure. En combinant l'influence de plusieurs entités, nous créons un regard plus réaliste sur l'ensemble du paysage. Du point de vue de la mise en œuvre, nous rapprochons le monde du jeu en lui superposant une grille 2D, et après avoir déterminé dans quelle cellule de la grille se trouve l'entité, nous appliquons une évaluation d'impact à celle-ci et aux cellules environnantes, indiquant l'aspect du gameplay que nous voulons simuler. Pour obtenir l'image complète, nous accumulons ces valeurs dans la même grille. Après cela, nous pouvons effectuer diverses requêtes de grille afin de comprendre le monde et décider du positionnement et des points cibles.

Prenons, par exemple, "le point le plus faible de la défense de l'ennemi". Nous avons un mur défensif, à l'attaque duquel nous voulons envoyer des fantassins, mais il y a 3 catapultes derrière lui - 2 proches les unes des autres à gauche, 1 à droite. Comment choisissons-nous une bonne position d'attaque?

Pour commencer, nous pouvons attribuer +1 points de protection à toutes les cellules de la grille dans l'attaque de catapulte. Le dessin de ces points sur la carte d'influence d'une catapulte ressemble à ceci:


Le rectangle bleu limite toutes les cellules dans lesquelles vous pouvez lancer une attaque contre le mur. Les carrés rouges indiquent +1 influence de catapulte. Dans notre cas, cela signifie la zone de leur attaque et la menace pour les unités attaquantes.

Maintenant, nous ajoutons l'effet de la deuxième catapulte:


Nous avons une zone sombre dans laquelle se forme l'influence de deux catapultes, ce qui confère à ces cellules une protection +2. La cellule +2 à l'intérieur de la zone bleue peut être un endroit particulièrement dangereux pour attaquer le mur! Ajoutez l'influence de la dernière catapulte:


[Icônes: CC-BY: https://game-icons.net/heavenly-dog/originals/defensive-wall.html ]

Nous avons maintenant une désignation complète de la zone couverte par les catapultes. Dans la zone d'attaque potentielle, il y a une cellule avec +2 influences de catapulte, 11 cellules avec +1 influence, et 2 cellules avec 0 influence de catapulte - ce sont les principaux candidats pour la position d'attaque, en eux nous pouvons attaquer le mur sans crainte d'un incendie de catapulte.

L'avantage des cartes d'influence est qu'elles transforment un espace continu avec un ensemble presque infini de positions possibles en un ensemble discret de positions approximatives, à propos desquelles nous pouvons prendre des décisions très rapidement.

Cependant, nous n'avons obtenu cet avantage qu'en choisissant un petit nombre de positions d'attaque potentielles. Pourquoi devrions-nous utiliser la carte d'influence ici au lieu de vérifier manuellement la distance de chaque catapulte à chacune de ces positions?

Premièrement, le calcul d'une carte d'influence peut être très peu coûteux. Une fois les points d'influence placés sur la carte, il n'est pas nécessaire de la modifier avant que les entités commencent à se déplacer. Cela signifie que nous n'avons pas besoin d'effectuer constamment des calculs de distance ou d'interroger de manière itérative toutes les unités possibles - nous «incorporons» ces informations dans la carte et pouvons lui envoyer des demandes autant de fois que nécessaire.

Deuxièmement, nous pouvons chevaucher et combiner différentes cartes d'influence pour répondre à des requêtes plus complexes. Par exemple, pour sélectionner un endroit sûr pour s'échapper, nous pouvons prendre une carte de l'influence de nos ennemis et soustraire la carte de nos amis - les cellules de la grille avec la plus grande valeur négative seront considérées comme sûres.


Le plus rouge, le plus dangereux et le plus vert, le plus sûr. Les zones dans lesquelles les chevauchements d'influence peuvent être complètement ou partiellement neutralisés pour refléter les zones d'influence conflictuelles.

Enfin, les cartes d'influence sont faciles à visualiser lors du rendu dans le monde. Ils peuvent être un indice précieux pour les concepteurs qui ont besoin de personnaliser l'IA en fonction des propriétés visibles, et ils peuvent être regardés en temps réel pour comprendre pourquoi l'IA choisit ses décisions.

Conclusion

J'espère que l'article vous a donné un aperçu des outils et des approches les plus populaires utilisés dans l'IA de jeu, ainsi que des situations dans lesquelles ils peuvent être appliqués. L'article ne tenait pas compte de nombreuses autres techniques (elles sont utilisées moins souvent, mais pourraient être tout aussi efficaces), notamment les suivantes:

• algorithmes de tâche d'optimisation, y compris la montée vers le haut, la descente de gradient et les algorithmes génétiques.
• des algorithmes de recherche / planification compétitifs tels que l'écrêtage minimax et alpha beta
• les techniques de classification, par exemple les perceptrons, les réseaux de neurones et la méthode des vecteurs de support
• systèmes de perception d'agents et de traitement de la mémoire
• approches architecturales de l'IA, telles que les systèmes hybrides, les architectures prédicatives (architectures Brooks) et d'autres façons de décomposer les systèmes d'IA en couches
• des outils d'animation tels que la planification et la mise en correspondance des mouvements
• tâches liées aux performances telles que le niveau de détail, les algorithmes à tout moment et la synchronisation

Pour en savoir plus sur ces sujets, ainsi que sur les sujets abordés dans cet article, vous pouvez étudier les sources suivantes.

• GameDev.net propose des articles et des tutoriels sur l'intelligence artificielle , ainsi qu'un forum sur l'intelligence artificielle .
• Sur AiGameDev.com ont de nombreuses présentations et articles sur un large éventail de sujets d'intelligence artificielle dans le contexte du développement de jeux
• GDC Vault a des rapports avec GDC AI Summit, dont beaucoup sont disponibles gratuitement: https://www.gdcvault.com/
  
• De plus, la AI Game Programmers Guild a un tas de liens vers les anciens articles et présentations de ce sommet: http://gameai.com/
  
• Le chercheur en intelligence artificielle et développeur de jeux Tommy Thompson dispose d'une chaîne YouTube dédiée à l'explication et à l'exploration de l'IA dans les jeux commerciaux: https://www.youtube.com/user/tthompso

Beaucoup de matériaux de la plus haute qualité se trouvent dans les livres, notamment les suivants:

• La série Game AI Pro est une collection de courts articles expliquant comment implémenter des fonctionnalités spécifiques ou résoudre des problèmes spécifiques. À http://www.gameaipro.com/ publié des extraits gratuits de livres précédents.
  
  • Game AI Pro: la sagesse des professionnels de Game AI
    
  • Game AI Pro 2: Sagesse collectée des professionnels de Game AI
    
  • Game AI Pro 3: Sagesse collectée des professionnels de Game AI
    
  
  
• AI Game Programming Wisdom Game AI Pro. , . , !
  
  
  • AI Game Programming Wisdom 1
    
  • AI Game Programming Wisdom 2
    
  • AI Game Programming Wisdom 3
    
  • AI Game Programming Wisdom 4
    
• Artificial Intelligence: A Modern Approach — , . , , , .

En outre, il existe plusieurs bons livres sur l'IA de jeu en général, écrits par des professionnels de l'industrie. Il est difficile de privilégier qui que ce soit - lisez les avis et choisissez celui qui vous convient.