Making of Bobots

 

Par 3emeType (Bobot Lead Coder AI)

barre-1.jpg

Navigation globale : Waypoints.

image6La navigation de personnages non joueurs (ou PNJs) dans les jeux vidéo se fait presque systématiquement à l’aide de points de passages (ou waypoints). Un graphe de waypoints est construit au préalable pour chaque aire de jeu, et lorsqu’un PNJ décide de partir de tel waypoint pour se rendre à tel autre waypoint, un algorithme de planification de type A* (ou A star) se charge de calculer le chemin le plus court (une liste de waypoints) pour y parvenir.

La stratégie de déplacement élémentaire (d’un waypoint à un autre) la plus communément employée est le déplacement en ligne droite. Pour qu’un déplacement de ce type se fasse sans encombre, il faut qu’il n’y ait aucun obstacle immobile entre chaque couple de waypoints reliés. Tout contournement d’obstacle immobile doit être décrit explicitement dans le graphe de waypoints, dont la taille peut ainsi devenir très importante. Ce système atteint son paroxysme dans le déplacement case par case

(cf. Figure ci-contre) où la surface de déplacement est entièrement tapissée de waypoints.

Figure Ci-dessus : Planification par A* où chaque case est un waypoint. Le waypoint de départ est le point vert, le waypoint d’arrivée est le point rouge. Les cases grises sont infranchissables. Les traits rouges fins font partie des chemins testés par l’A*. Les traits rouges épais constituent le chemin optimal qu’il a finalement calculé.

 barre-1.jpg

Se rapprocher de la navigation humaine.

Navigation locale : Contournement d’obstacles grâce à un réseau de neurones.

image7Une telle navigation ne copie pas parfaitement la navigation humaine. Lorsqu’un humain projette de se déplacer d’un endroit à un autre, il ne planifie pas chaque segment du chemin qu’il va emprunter. Ses prévisions se limitent à quelques waypoints significatifs, et pour le reste il fait confiance à son aptitude à contourner les obstacles entre chacun de ces waypoints. Dans le problème de la Figure ci-dessus pour contourner l’obstacle, là où le PNJ se déplaçant en case par case se donne 10 waypoints intermédiaires (les 10 cases parcourues par le chemin optimal), un humain ne s’en donnerait probablement qu’un : il prévoirait de passer au sud de l’obstacle, avant de se diriger vers l’arrivée.

Le système de navigation du bot présenté dans cet article a été conçu pour s’approcher un peu plus de la navigation humaine, en limitant le plus possible le nombre de waypoints sur une aire de jeu (cf. Figure ci-contre). La conséquence de cette simplification du graphe de waypoints est une complexification du déplacement entre deux waypoints. Le déplacement local en ligne droite a donc dû être remplacé par un mécanisme de contournement d’obstacles.

Figure Ci-dessus : Waypoints sphériques en faible nombre sur une aire de jeu (les connexions entre waypoints ne sont pas représentées). De plus ils peuvent adopter différentes tailles leur permettant de définir une zone plus ou moins vague.

barre-1.jpg

Navigation locale : Contournement d’obstacles grâce à un réseau de neurones.

 

image8
 
C’est un réseau de neurones qui est utilisé chez chaque bot pour contourner les obstacles. La détection des obstacles se fait par un système s’apparentant à celui du sonar. Le bot envoie continuellement 6 rayons devant lui, dans 6 directions différentes (cf. Figure ci-contre). Lorsqu’un rayon est stoppé par un obstacle (aussi bien mobile que fixe), sa longueur est réduite. Le bot est informé de la longueur de chaque rayon.

Les rayons sont envoyés de manière à pouvoir détecter un obstacle venant de face, de ¾ gauche, et de ¾ droit, par rapport au sens de déplacement du bot. Deux couches de rayons, un à hauteur d’yeux et un en rase motte, permettent de différencier les murs infranchissables des obstacles par-dessus lesquels il est possible de sauter.

Figure Ci-dessus : Rayons (en rouge ici, mais invisibles en cours de jeu) de détection des obstacles que le bot envoie continuellement devant lui.

 

 barre-1.jpg

La configuration du réseau de neurones utilisé (sans les poids synaptiques).

 

image9Détecter les obstacles ne suffit pas pour en déduire le sens de leur contournement. Le bot a également besoin de connaître la direction du prochain waypoint de son parcours. Ainsi il devra contourner un obstacle par la droite s’il sait que le prochain waypoint est sur la droite de son champ de vision.

Le réseau de neurone employé est un perceptron multi-couche à 7 neurones d’entrée, 2 de sortie, et une couche cachée de 12 neurones (cf. Figure ci-contre). En entrée, il perçoit les longueurs des rayons de détection d’obstacles, ainsi que l’angle entre le champ de vision courant du bot et la localisation du prochain waypoint. En sortie, il commande la correction d’angle à donner à la direction du bot, ainsi que le déclenchement d’un saut. Quant à la vitesse du bot, elle est constante et positive pendant toute la durée d’un parcours.

barre-1.jpg

Entraînement du réseau de neurones par un algorithme génétique.

 

image10L’entraînement du réseau de neurones est effectué à l’aide d’un algorithme génétique. Celui-ci est chargé de sélectionner les poids synaptiques du réseau de neurones. Une population de 30 bots, dont chacun a les poids synaptiques de son réseau de neurones initialisés au hasard, est placée dans un environnement spécialement conçu pour l’occasion (cf. Figure ci-contre).

Les 30 bots sont répartis tout autour d’une sorte de parcours du combattant dont le centre est le waypoint d’arrivée de chaque bot. Une série de waypoints intermédiaires (invisibles sur la capture d’écran) est placée le long du chemin. La durée de vie d’une génération est de 1 minute. Au bout de ce temps, un classement des bots est effectué. Chacun d’entre eux est noté principalement sur la distance qu’il a parcouru en suivant les waypoints (plus la distance est élevée, plus la note l’est aussi), et sur le nombre de collisions provoquées avec l’environnement (plus il s’est cogné, moins bien il est noté). La génération suivante est générée par croisements entre les bots de la génération en cours, en autorisant plus d’accouplements à ses meilleurs éléments.

Figure Ci-dessus : Domaine d’entraînement des bots. Ils ont à monter des escaliers, sauter des murets, contourner des murs, franchir des portes, et suivre des waypoints.

Quelques heures d’évolution (en accélérant le jeu) suffisent à obtenir un comportement satisfaisant. Les poids synaptiques du meilleur bot de la dernière génération sont alors sauvegardés et utilisés ensuite par chaque bot introduit dans le jeu.

 barre-1.jpg

Prise de décision.

 

Priorité des actions.

Plusieurs fois par secondes, le bot évalue la priorité de chaque action possible. Toutes les actions ne sont pas tout le temps évaluées. Si par exemple le niveau de santé du bot est à son maximum, rien ne lui sert de se demander s’il serait intéressant d’aller ramasser la trousse de soin qui se trouve à 30 mètres devant lui. Par contre, si son niveau de santé est à 42%, il a besoin d’évaluer l’importance d’aller ramasser la trousse de soin. Pour cela il prend en compte la valeur de son niveau de santé (42%) et la distance à la trousse (30% si son champ de vision est de 100 mètres), et calcule une priorité sur une échelle de 0 à 100 avec une méthode expliquée plus loin.

Les priorités de chaque action sont comparées, et l’action finalement choisie est celle qui a la priorité la plus élevée.

C’est en fait un peu plus complexe, car l’action en cours conserve sa priorité pendant quelques secondes même si ses éléments déclencheurs ne sont pas tous présents. Si par exemple la trousse de soin que le bot était en train d’aller ramasser se trouve occultée de son champ de vision par le passage d’un équipier, les conditions d’évaluations de la priorité de l’action ramasser la trousse de soin ne sont plus respectées. Le bot doit donc garder en tête qu’il est en train d’aller ramasser une trousse de soin même s’il ne la voit plus. Mais il ne doit pas insister trop longtemps car la raison de sa disparition peut être toute autre : quelqu’un d’autre a pu la ramasser

Calcul des priorités en logique floue.
Le choix de la logique floue.


On attend, d’une bonne intelligence artificielle, une souplesse au niveau de sa prise de décision (entre autres). Poursuivons l’étude de l’exemple de la trousse de soin posée à terre dans le champ de vision du bot. Le bot doit considérer que le ramassage de cette trousse de soin est d’autant plus important que la trousse est proche de lui et que son nombre de points de vie est faible.

Les notions de proche et de faible sont vagues, ou floues. Les règles classiques des langages de programmation (de type if then else) auraient bien du mal à rendre compte de tous les cas possibles. Par exemple, si le bot a 90% de vie il n’a à priori pas besoin de se soigner. Mais si une trousse de soin se trouve à 1 mètre de lui, il n’aurait pas de raison de se priver de la ramasser s’il n’a rien à faire de plus urgent. La priorité de l’action doit donc rester positive (mais proche de zéro) dans ce cas. Et dans le cas où le bot a 99% de vie également, mais elle doit alors être encore plus faible.

L’idéal est d’avoir une variation continue de la priorité de l’action par rapport à la distance à la trousse de soin et la santé du bot. La logique floue nous permet de l’obtenir avec un ensemble de seulement 16 règles (dans ce cas précis, et avec l’implémentation que j’en fais).

Exemple d’ensemble de règles floues.

Les 16 règles floues qui permettent au bot d’évaluer la priorité de l’action ramasser la trousse de soin la plus proche sont les suivantes (Dans cette énumération, Health représente l’état de santé du bot, Dist la distance à la trousse de soin, Priority la priorité de l’action, et VeryLow, Low, Medium, et High sont des sous-ensembles flous dont les fonctions d’appartenance sont décrites plus loin) :

– IF Health IS VeryLow AND Dist IS VeryLow THEN Priority IS High
– IF Health IS VeryLow AND Dist IS Low THEN Priority IS High
– IF Health IS VeryLow AND Dist IS Medium THEN Priority IS Medium
– IF Health IS VeryLow AND Dist IS High THEN Priority IS Low
– IF Health IS Low AND Dist IS VeryLow THEN Priority IS High
– IF Health IS Low AND Dist IS Low THEN Priority IS Medium
– IF Health IS Low AND Dist IS Medium THEN Priority IS Low
– IF Health IS Low AND Dist IS High THEN Priority IS VeryLow
– IF Health IS Medium AND Dist IS VeryLow THEN Priority IS Medium
– IF Health IS Medium AND Dist IS Low THEN Priority IS Low
– IF Health IS Medium AND Dist IS Medium THEN Priority IS VeryLow
– IF Health IS Medium AND Dist IS High THEN Priority IS VeryLow
– IF Health IS High AND Dist IS VeryLow THEN Priority IS VeryLow
– IF Health IS High AND Dist IS Low THEN Priority IS VeryLow
– IF Health IS High AND Dist IS Medium THEN Priority IS VeryLow
– IF Health IS High AND Dist IS High THEN Priority IS VeryLow

L’opérateur AND est le minimum, l’opérateur d’agrégation est le maximum, et la réalisation de la défuzzyfication se fait par la moyenne des maximums.

    

Fonctions d’appartenance des sous-ensembles flous utilisés dans les règles floues.

image11à gauche) : Fonctions d'appartenance des sous-ensembles flous utilisés dans les prémisses des règles. En abscisse se trouvent les valeurs des entrées (Health et Dist par exemple) en pourcentage, et en ordonnées leur degré d’appartenance à chaque sous-ensemble flou

 (à droite) : Fonctions d'appartenance des sous-ensembles flous utilisés dans les conclusions des règles. En abscisse se trouvent les valeurs possibles de la priorité de l’action, et en ordonnées leur degré d’appartenance à chaque sous-ensemble flou

Courbe de la priorité de l’action ramasser la trousse de soin la plus proche.

image12

 

Sur cette courbe nous pouvons observer l’augmentation continue de la priorité de l’action ramasser la trousse de soin la plus proche quand la santé du bot diminue et que la trousse de soin se rapproche.

Figure ci-contre : Priorité de l’action de ramasser la trousse de soin la plus proche en fonction du niveau de santé du bot et de la distance à la trousse de soin. La courbe est en théorie continue, mais la priorité n’est calculée ici par le moteur d’inférence que pour chaque couple d’entiers (niveau de santé, distance à la trousse de soin) entre 0 et 100

Schéma général du comportement d’un bot

image13La Figure ci-contre résume le comportement général d’un bot, avec en premier plan son mécanisme de prise de décision qui fait appel, lorsque cela est nécessaire, au module de déplacement.

Un dispositif est absent du schéma. Il consiste à donner une limite temporelle à toute action. Cela permet d’éviter des situations de blocage imprévues, comme par exemple celle où un bot essayerait indéfiniment de ramasser une trousse de soin qui lui est physiquement inaccessible.

Cet article a présenté un bot pour le jeu vidéo Wolfenstein : Enemy TerritoryTM. Il est architecturé autour d’un mécanisme de prise de décision, basé sur des ensembles de règles floues, et d’un module de déplacement faisant intervenir un réseau de neurones entraîné à l’évitement d’obstacles par un algorithme génétique.

L’orientation non professionnelle du projet a permis des expériences qu’il n’aurait pas été possible de réaliser dans le cas contraire, principalement au sujet de la navigation avec peu de waypoints. En effet, les techniques actuelles de navigation fonctionnent très bien et l’orientation prise dans cette partie du projet provient plus d’une volonté d’approcher le comportement humain que d’un souci d’efficacité.

Le module de navigation de ce bot est tout de même assez satisfaisant car il rempli l’objectif fixé : peu de waypoints (environ 200 dans une aire de jeu où autre bot en aurait probablement exigé de l’ordre de 5000). Mais un défaut est à remarquer au niveau de l’évitement d’obstacles : le réseau de neurones ne réagit pas toujours parfaitement lorsque le bot a à franchir des passages étroits. Ceci m’a amené à ajouter quelques waypoints spéciaux entre lesquels le réseau de neurones est désactivé et le déplacement en ligne droite forcé. 

Quant à l’utilisation de règles floues pour l’aide à la prise de décision, elle s’inscrit dans une approche plus commune de l’intelligence artificielle des PNJ dans les jeux vidéo [RAB, 02]. La logique floue permet ici d’apporter de la souplesse à la prise de décision sans nécessiter beaucoup de calculs. Elle permet également le peaufinage à la main du comportement des bots, ce que n’autorisent pas les réseaux de neurones, par exemple, car la description d’un tel réseau n’est qu’une liste de valeurs numériques dont le sens n’apparaît pas à leur lecture, contrairement aux règles floues qui sont écrites dans notre langage.

Ce bot est distribué gratuitement (tout comme le jeu Wolfenstein : Enemy TerritoryTM) sur ce site et autres sites Internet sous le doux nom de Bobots, et y rencontre un vif succès.

 barre-1.jpg

Conclusion et perspectives

 Une amélioration importante pourrait être faite au niveau du jeu en équipe des bots. Actuellement, ils ne prennent en compte leurs équipiers qu’à un bas niveau (ils leur apportent des soins, les protègent temporairement d’un ennemi, ...). Cela ne permet pas de comportements de groupe évolués comme l’escorte, l’organisation en petites unités, les attaques simultanées, etc. Une façon d’envisager le jeu en équipe pourrait venir d’une prise de décision stratégique centralisée. Un programme superviseur ordonnerait à chaque bot d’agir en fonction de la stratégie qu’il a prévu. Si cela pourrait fonctionner dans une équipe entièrement constituée de bots, ça ne serait plus le cas dans une équipe mixte, car le superviseur ne serait connu que des bots, pas des joueurs humains. Or l’intérêt d’un bot est de pouvoir prendre le rôle de l’équipier aussi bien que celui de l’adversaire. Une solution sans superviseur serait de permettre aux bots et aux humains de communiquer entre eux. Le protocole de communication n’aurait pas besoin d’être créé spécialement pour l’occasion puisque les joueurs humains ont déjà à leur disposition un ensemble d’une trentaine de messages préenregistrés du type « suivez-moi », « besoin d’un ingénieur », « allons-y », « besoin d’aide », etc., qu’ils peuvent déclencher d’une simple pression de touche. L’utilisation de ces messages par les bots ouvrirait la porte à l’élaboration d’un système multi-agent (SMA) autorisant des comportements de groupes évolués mêlant joueurs humains et joueurs artificiels.              

 

Auteur(s) : CAZENAVE Tristan
Date de parution: 11-2006
Langue : FRANÇAIS
230p. 15.5x23.5 Broché  

 

 

Résumé
Cet ouvrage traite de l'intelligence artificielle pour les jeux vidéo et les jeux de réflexion. Appliquée depuis longtemps aux jeux de réflexion classiques, l'intelligence artificielle connaît des résultats contrastés : meilleure que les humains aux échecs mais encore faible au jeu de Go. On assiste désormais à un développement dans le domaine des jeux vidéo avec des thématiques renouvelées. Ce livre étudie successivement les jeux de réflexion (Lines of Action, Go et Atarigo), les jeux vidéos, simulations sportives, simulations d'écosystème, jeux de combat, jeux d'action, jeux de stratégie en temps réel, jeux d'aventure, jeux en équipe ainsi que les jeux d'éveil. Il met l'accent sur l'apprentissage et sur la planification de comportements.

Sommaire
Chapitre 1. Introduction. Chapitre 2. Génération de comportements pour personnages de jeux vidéo. Chapitre 3. MHiCS, une architecture de sélection de l'action adaptative pour joueurs artificiels. Chapitre 4. Une intelligence artificielle pour un jeu vidéo Multijoueurs. Chapitre 5. Experiences d'apprentissage par renforcement dans une architecture Monte-Carlo Go. Chapitre 6. Architecture d'un programme de Lines of action. Chapitre 7. De nouvelles heuristiques de recherche appliquées à la résolution d'Atarigo. Chapitre 8. Des stratégies qui s'adaptent à la situation dans les jeux de stratégie temps réel. Chapitre 9. Exécution adaptative de trame narrative. Chapitre 10. Simulation de comportements centrée Interaction. Chapitre 11. Contrôle d'exécution des jeux par analyse du comportement du joueur.

 Intelligence Artificielle et jeux (Coll. Information, Hypermédias et communications)

 

Date de dernière mise à jour : 18/09/2014

Créer un site gratuit avec e-monsite - Signaler un contenu illicite sur ce site