L’Intelligence artificielle dans les jeux vidéo (Synthèse)

Dans cet article, nous allons synthétiser le travail effectué au cours des précédents articles, apporter une conclusion et des perspectives d’avenir en matière d’intelligence artificielle dans les jeux vidéo ; enfin, nous annoncerons le plan du rapport final du projet. Il sera possible de le télécharger via un lien.

Au cours des cinq articles qui ont jalonné ce projet, nous avons développé de nombreuses thématiques abordant des aspects variés de l’intelligence artificielle, toujours avec pour objectif d’en montrer une utilisation concrète dans le domaine des jeux vidéo. Nous avons volontairement choisi d’accroitre la complexité du contenu des articles au fur et à mesure de l’avancement du projet.

Nous avons commencé en présentant les différentes méthodes algorithmiques qui permettent de répondre aux problèmes les plus classiques. Nous avons ainsi abordé la notion d’arbre de recherche par le biais d’algorithmes tels que MinMax ou encore Alpha-beta. Ces derniers sont particulièrement utilisés dans les jeux dits « classiques » (les jeux de plateau par exemple) mais trouvent toutefois une autre application dans certains jeux de stratégie. Nous nous sommes ensuite attaqués au fameux problème du « pathfinding » en explorant différentes solutions permettant de trouver son chemin dans les pires cartes de jeux vidéo (Dijkstra et A* notamment).

Dans le quatrième article, nous avons fait une entrée en matière de la théorie des jeux. Après une rapide présentation des concepts liés à cette théorie, nous avons tenté de comprendre l’équilibre de Nash à travers un exemple simple : le dilemme des prisonniers. Cette théorie est à la base de nombreux progrès réalisés dans le domaine de l’intelligence artificielle.

Enfin, dans les troisième et cinquième articles, nous avons tenté de vous faire découvrir les méthodes les plus récentes utilisées par les PNJ (« Personnages Non Joueurs ») dans les jeux vidéo un minimum complexes : les méthodes d’apprentissage automatique. Dans un premier temps, nous nous sommes attaqués à l’apprentissage par renforcement et au système de classeur en appliquant ces concepts au jeu Counter Strike. Dans un second temps, nous avons généralisé cette forme d’apprentissage en essayant de voir plus loin. Nous avons alors étudié les réseaux de neurones et leurs applications dans les jeux vidéo. Ces derniers tendent à se développer pour augmenter le sentiment d’immersion du joueur. Ils constituent sans doute l’avenir de l’intelligence artificielle dans le monde du jeu vidéo.

Le rapport final, qui constitue une synthèse auto-suffisante des différents articles, a pour but de les restructurer en articulant correctement les différentes idées qu’ils contiennent. En voici le plan :

Introduction

  1. La théorie des jeux
    1. Un peu de théorie
    2. L’équilibre de Nash
    3. Un exemple simple : le dilemme du prisonnier
  2. Les méthodes algorithmiques de base
    1. Les arbres de recherche
    2. Le Pathfinding
  3. L’apprentissage automatique
    1. Présentation
    2. L’apprentissage par renforcement
    3. Les réseaux de neurones
  4. Les perspectives en matière d’IA pour les jeux vidéo

Voici le lien de téléchargement du rapport : pvete12_rapport_iajv.

Apprentissage automatique et réseaux de neurones

Au cours des dernières décennies, de nombreux progrès ont été fait dans le domaine de l’IA. Pourtant, il est toujours impossible, même pour la meilleure machine, de s’adapter à son environnement physique et social comme le ferait un enfant d’un an. La différence est évidente : lorsqu’un ordinateur est programmé pour réaliser des tâches prédéfinies, un bébé ne s’impose aucune contrainte dans sa technique d’apprentissage et décide lui-même de son terrain d’exploration. Il maitrise donc les situations d’apprentissage et développe ses propres représentations du milieu dans lequel il vit. Cette simple analyse est à la base d’une réflexion d’Alan Turing qui aurait dû guider les recherches en matière d’IA des 50 dernières années : plutôt que d’essayer de reproduire le fonctionnement du cerveau d’un adulte, nous devrions commencer par étudier la méthode d’apprentissage employée par les enfants.

Cette idée est mise en pratique dans l’un des champs d’étude de l’intelligence artificielle : l’apprentissage automatique. Cette discipline scientifique vise à concevoir des programmes capables de s’améliorer au cours du temps, en fonction de leurs expériences passées. Il est ainsi possible d’analyser des systèmes complexes à travers l’analyse de données empiriques. On peut également intégrer la notion de « valeur symbolique » qui vise à attribuer à un comportement une certaine valeur numérique (une probabilité par exemple). Ainsi, là où des algorithmes « classiques » auraient des difficultés pour résoudre un problème, l’apprentissage permettra de gérer un grand nombre d’entrées et de régler le problème d’explosion combinatoire. C’est le cas, par exemple, lorsque l’on crée une machine sans connaître l’environnement dans lequel elle va évoluer. Cette discipline trouve une application dans de nombreux domaines : la programmation de systèmes intégrant une perception de leur environnement, de moteurs de recherches, dans la bio-informatique, dans l’analyse financière ou encore dans le monde des jeux vidéo.

Domaine d'application de l'apprentissage automatique (1)

Domaine d'application de l'apprentissage automatique (1)

Les différentes méthodes d’apprentissage

Maintenant, la question est la suivante : un enseignant tente tant bien que mal d’apprendre une leçon à un élève avec pour contrainte un langage commun limité (on peut supposer que ce langage est l’objectif de la leçon), comment peut-il lui transférer son savoir ? A priori, il existe plusieurs méthodes d’apprentissage :

  • L’apprentissage par imitation : l’enseignant montre l’exemple à l’élève qui tente de l’imiter,
  • L’apprentissage par renforcement : l’étudiant tente de réaliser l’action de manière intuitive, et l’enseignant effectue un « feedback » sur sa prestation,
  • L’apprentissage par correction : en même temps que l’étudiant réalise l’action, l’enseignant corrige en temps réel.

A partir de cette réflexion, on définit de nombreuses classes d’algorithme d’apprentissage dont voici les principaux :

  • Apprentissage par cœur (on associe deux éléments dans une mémoire),
  • Par analogie (on établit des correspondances entre deux représentations différentes),
  • Par renforcement (système de récompense/punition suite à une action),
  • Par classification/catégorisation (vise à trier les différentes données),
  • Apprentissage supervisé/non supervisé. Nous développerons cet exemple par la suite afin de mieux intégrer les problématiques liées à l’apprentissage automatique.

Apprentissage supervisé

L’apprentissage supervisé est une catégorie d’algorithme par apprentissage qui vise à produire des règles en s’appuyant sur une base de données d’apprentissage (souvent des résultats d’expériences précédentes). Dans la plupart des catégories d’algorithmes vues dans la partie précédente, la première étape est celle de la classification durant laquelle on « étiquette » chaque donnée en l’associant à une classe. C’est le cas de l’apprentissage supervisé. Dans un premier temps, un « oracle » (personne apte à étiqueter les exemples) génère un ensemble de couples entrée-sortie : c’est la phase d’apprentissage. Ensuite, dans une phase de test, le système tente de prédire la sortie connaissant l’entrée. On retrouve ce comportement lors de diagnostics médicaux. Ceux-ci s’appuient sur une classification de couple symptômes – maladie qui est utilisée dans le but de trouver une maladie (sortie) associée à des symptômes (entrée). Voici un schéma résumant l’apprentissage supervisé :

Apprentissage supervisé (1)

Apprentissage supervisé (1)

Cette forme d’apprentissage est utilisée dans de nombreuses méthodes. En voici quelques exemples :

  • La méthode des k plus proches voisins : connaissant une entrée x, on sélectionne la sortie sur la base d’une analyse des k échantillons dont l’entrée est la plus proche de l’entrée x. On retient souvent la classe la plus représentée parmi les sorties déterminées ainsi ;
  • Les machines à vecteur de support (SVN en anglais) : elles permettent de résoudre des problèmes de régression et de discrimination ;
  • Les arbres de décision ;
  • Les réseaux bayésiens ;
  • Les réseaux de neurones.

Cette catégorie d’algorithme s’oppose à l’apprentissage non supervisé, dans lequel la machine ne dispose pas d’étiquettes mais seulement d’exemple. Le nombre de classe est alors inconnu, et c’est à l’algorithme de déterminer la structure des données.

Réseaux de Neurones

Les réseaux de neurones sont apparus en 1950 et constituent une représentation formelle des neurones biologiques. On retrouve ainsi, pour chaque synapse (connexion entre deux neurones), un coefficient synaptique (appelé « poids ») qui permettent l’induction de l’apprentissage. La base de l’étude est d’établir un algorithme qui permettra de faire évoluer ces coefficients. Le réseau pourra ainsi retrouver des similitudes avec les valeurs qui lui avaient été soumises lors de son apprentissage.

Depuis 1986 (et la mise en œuvre d’algorithmes reposant sur la rétropropagation du gradient de l’erreur dans des systèmes à plusieurs couches !), les réseaux de neurones sont de plus en plus utilisés, notamment dans le milieu des jeux vidéo (première utilisation en 1996 dans Battlecruiser 3000AD et Creatures, puis en 2001 avec Black & White de Lionhead).

Creatures (http://creatures.wikia.com/wiki/Hebe_Norn)

Creatures (http://creatures.wikia.com/wiki/Hebe_Norn)

Structure d’un réseau

Les réseaux sont basés sur une architecture multicouche, chaque couche étant composée de neurones. Une première couche récolte des informations (par des capteurs par exemple) et les transmet à la suivante, et ainsi de suite jusqu’à la dernière couche. Un neurone effectue diverses opérations sur les entrées comme le montre la figure qui suit :

Structure d'un neurone artificiel (2)

Structure d'un neurone artificiel (2)

Il additionne les entrées pondérées par leur coefficient synaptique puis leur applique une fonction dite d’activation et envoie la sortie, suite à une nouvelle pondération par le coefficient synaptique, aux neurones suivants.

Des exemples d’application

L’aspect « roaming » : les déplacements

Un tel réseau permet de traiter le problème de déplacement d’un PNJ avec toutes les caractéristiques inhérentes à celui-ci : destination, vitesse, chemin… Nous avions déjà traité ce problème dans un article précédent (« Pathfinding ») avec des algorithmes tels que A* ou Dijkstra. Cependant, ces différents algorithmes requièrent des informations à propos de l’environnement dans lequel se déplace l’IA (présence d’ennemis, de murs ou d’autres obstacles). C’est la couche de perception qui envoie ces données et c’est donc celle qui contient un éventuel réseau de neurones. Voici un schéma synthétisant les connexions entre les différentes couches du jeu vidéo :

Schéma d'association entre un réseau de neurones et un algorithme de pathfinding (2)

Schéma d'association entre un réseau de neurones et un algorithme de pathfinding (2)

L’aspect « behavior » : les décisions

Cet aspect gère le comportement de l’IA au niveau le plus basique. C’est donc lui qui prend les décisions majeures telles que : attaquer l’ennemi, aller à couvert, changer d’arme. Bien que ces choix puissent paraitre évidents, ils deviennent beaucoup plus complexes lorsque l’on rajoute des paramètres en entrée : « Est-il préférable de perdre 4 secondes pour recharger mon arme puis continuer de cribler mon ennemi de balles sachant qu’il se situe actuellement à 8 mètres et qu’il se rapproche à une vitesse estimée de 1 m/s, ou bien dois-je courir à couvert à plus de 10 mètres de ma position actuelle pour remonter ma santé qui est actuellement à 17% ? À moins de donner l’ordre à un de mes équipiers de me couvrir… ». On comprend bien que les arbres de décisions peuvent rapidement donner des maux de crânes. Par ailleurs, on peut se demander s’il est préférable de donner à l’IA un aspect humain en intégrant la possibilité de se tromper et, par conséquent, laisser au joueur une chance de gagner afin de ne pas le dégouter du jeu !

Mafia 2 – Mais qu'est-ce que je fais maintenant? (2)

Mafia 2 – Mais qu'est-ce que je fais maintenant? (2)

Il existe de nombreuses technologies permettant de répondre à cette problématique sous forme d’arbre de décision. L’une des plus efficaces étant les réseaux Bayésiens. En fonction d’informations observées, ils calculent la probabilité d’événements non observés, afin d’en déduire les actions envisageables. Il est intéressant de les associer aux réseaux de neurones qui s’occuperaient alors de percevoir les données de l’environnement et de les traiter.

Planification et stratégie

Contrairement à des jeux de plateau (Echec, Dames ou Go) où l’on peut envisager de prendre des décisions à l’aide de la logique combinatoire, certains jeux de type RTS (« Real Time Strategy ») intègrent généralement différents concepts qu’il est difficile de gérer et d’équilibrer de façon parfaitement rationnelle : la récolte de différentes ressources, la production d’énergie, la construction de bâtiments, l’évolution des recherches pour améliorer la vitesse des unités, sans oublier le fameux « brouillard de guerre » qui empêche l’ensemble des joueurs de se tenir au courant des activités de l’adversaire.

Ces jeux n’étant pas à information complète (cf. article « La Théorie des jeux »), on ne peut pas appliquer un système de gestion omniscient. Par conséquent, les développeurs utilisent le plus souvent un arbre décisionnel pour prendre en compte un maximum de ces contraintes et envoyer des ordres aux IA. Cependant, l’ergonomie offerte par cette solution n’est pas optimale et le joueur s’en rend assez vite compte. Les réseaux bayésiens pourraient combler ces déficits mais ils ne permettent pas une gestion stratégique en temps réel. La solution la plus adapté semble être les réseaux de neurones mais leur implémentation et leur utilisation pourraient s’avérer délicates. En effet, ceux-ci trouvent leur intérêt dans la classification, la perception et la reconnaissance ou encore la généralisation. Si ils sont capables d’apprendre et de changer leurs choix selon leur expérience, le mode d’apprentissage supervisé ne peut pas convenir, à moins de trouver une méthode pour que le joueur supervise inconsciemment l’apprentissage de son adversaire, et un mode d’apprentissage non-supervisé ne semble pas être adapté à nos besoins.

La solution pourrait résider dans le modèle SOM de Kohonen, qui serait alors utilisé en parallèle d’un outil décisionnel en plaçant un neurone sur chaque zone observable. Ce dernier réagirait ou se déplacerait selon l’activité observée. Il serait alors possible de transmettre des informations précises au corps décisionnel de l’agent. Enfin, l’utilisation d’un Perceptron multicouche pourrait également s’avérer intéressante, notamment pour percevoir l’orientation ou la vitesse de déplacement d’escouades ennemies. Il serait alors nécessaire, au préalable, de les entraîner correctement.

L’avenir ?

Un objectif pour les années à venir est d’augmenter encore l’immersion du joueur en donnant à l’IA une animation faciale et comportementale plus aboutie. Aujourd’hui, de nombreux jeux s’appuient sur des créatures à l’intellect limité (zombies et autres péons) afin de justifier des attitudes primaires. Cette solution risque d’atteindre ses limites aussi bien pour le joueur que pour le développeur. Aussi nous allons sans doute vers des IA capables de reproduire des mimiques du comportement humain, essayant de se rapprocher de leur modèle : nous.

Heavy Rain (2)

Heavy Rain (2)

Références :

  1. http://lipn.univ-paris13.fr/~rouveirol/enseigne/MICR_AS/Arbre-decision-1-2×2.pdf
  2. http://fabien.tschirhart.free.fr/images/Docs/memoire_V129.pdf
  3. http://fr.wikipedia.org/wiki/Apprentissage_automatique
  4. http://edesevin.free.fr/recherche/articles/dossier_candidature_2012.pdf
  5. http://fr.wikipedia.org/wiki/Architecture_cognitive
  6. https://wiki.bordeaux.inria.fr/Helene-Kirchner/lib/exe/fetch.php?media=wiki:flowers.pdf
  7. http://novamente.net/file/IRC_Learning.pdf

Licence Creative Commons Attribution

Cette œuvre est mise à disposition selon les termes de la Licence Creative Commons Attribution – Pas d’Utilisation Commerciale 3.0 non transposé.

La théorie des jeux

Dans cet article, nous présentons la théorie des jeux et aborderons le concept de solution avec, par exemple, l’équilibre de Nash.

La théorie des jeux a pour but de décrire le comportement d’un individu (ou d’un agent de façon plus générale) lors d’un jeu en partant du principe qu’il n’a aucune envie de se faire léser. Cette théorie vise donc à établir les stratégies optimales à l’aide de diverses modélisations, et d’établir « l’équilibre du jeu ». Elle est utilisée dans de nombreux domaines : l’économie, la politique ou encore la biologie. On trouve une autre application, de façon plus évidente, dans le domaine de l’intelligence artificielle.

Un peu de théorie

Afin de rentrer dans les détails, nous allons donner quelques brèves définitions qui nous permettront d’aborder des notions plus concrètes. Afin d’illustrer ces définitions, nous prendrons l’exemple du jeu Pierre-Feuille-Ciseaux (PFC).

On appelle utilité une évaluation de l’intérêt d’un coup pour un joueur. Dans PFC, l’utilité pour le gain d’une manche peut être évaluée à 1, 0 pour l’égalité et -1 pour la défaite.

Pour appliquer la théorie des jeux, il est nécessaire de catégoriser les jeux. Pour cela, il existe de nombreux critères :

  • Jeux simultanés (les joueurs jouent en même temps comme dans PFC) ou séquentiels (le jeu d’échecs, ou PFC si l’un des deux joueurs triche)
  • Jeux coopératifs ou non si les joueurs ont la possibilité de s’entraider
  • Jeux finis ou non si les joueurs ont un nombre fini de stratégies (PFC)
  • Jeux à somme nulle, si les intérêts des joueurs sont directement opposés (PFC, échecs ou poker), ou à somme non nulle si les deux joueurs peuvent trouver un intérêt commun (exemple du dilemme du prisonnier développé plus loin)
  • Jeux à répétition (PFC) : la stratégie à suivre varie considérablement si les joueurs ont une mémoire des parties précédentes
  • Jeux à information complète si les joueurs connaissent : les actions possibles, celles des autres joueurs ainsi que leurs motivations (PFC par exemple)

Il existe plusieurs méthodes de modélisation de jeux :

  • La forme stratégique (ou normale) : représentation sous forme d’une matrice

Matrice des gains (1)

  •  La forme extensive : représentation sous forme d’un arbre

Arbre représentant la forme extensive (1)

Dans les différents schémas, on retrouve l’utilité entre parenthèse. On peut également modéliser certains problèmes sous la forme de fonctions dites « caractéristiques ».

Enfin, on parle de stratégie pure lorsque la stratégie est purement déterministe. Dans PFC, la stratégie pure consisterait en la répétition du même coup tout au long de la partie. Une stratégie mixte fait intervenir la notion de hasard ; on choisit, à chaque tour, une stratégie pure de manière aléatoire.

Le concept de solution

Le concept de solution est un processus qui permet de déterminer les équilibres d’un jeu. Un concept de solution permettra donc de déterminer les stratégies les plus probables employées par les joueurs. Il existe de nombreux concepts de solution, la plupart sont des raffinements d’autres concepts (ils éliminent des équilibres peu plausibles) :

Arbre des concepts de solutions (5)

On appelle meilleure réponse l’ensemble des stratégies permettant au joueur d’être dans la meilleure position au coup suivant, sans forcément voir plus loin.

Par la suite, nous allons expliquer l’équilibre de Nash.

L’Équilibre de Nash

L’équilibre de Nash repose sur le choix, à chaque tour et pour chaque joueur, de la meilleure réponse. Par conséquent, la stratégie de chaque joueur est établie et aucun d’entre eux n’a intérêt à en sortir.

Le théorème de Nash stipule que, parmi toutes les stratégies possibles, il existe un équilibre parmi les stratégies mixtes. Dans l’exemple de PFC, l’équilibre de Nash est de jouer un coup au hasard avec équiprobabilité 1/3. A noter : dans le cas de PFC, l’ensemble des stratégies pures ne contenaient pas d’optimal, d’où l’extension aux stratégies mixtes.

Un exemple simple : le dilemme du prisonnier

Afin d’y voir plus clair et de montrer une application de toute cette belle théorie (très simplifiée par ailleurs), nous allons prendre l’exemple du dilemme du prisonnier, qui est un jeu à deux « joueurs ». Pour l’anecdote, ce jeu a été testé dans la vie réelle avec deux prisonniers pour qui ce n’était sans doute pas un jeu…

Règle du dilemme du prisonnier : les deux joueurs sont des prisonniers enfermés dans des cellules séparées. Il leur est possible de dénoncer leur ancien collègue dans le but d’obtenir un allègement de leur peine. Voici les différents cas de figure :

  • Si les deux joueurs se taisent, ils écopent tous deux d’un an de prison (ahh c’est beau l’amitié !).
  • Si l’un des deux seulement rapporte, il est libre alors que l’autre écope de 20 ans de prison !
  • Si les deux se dénoncent (cas le plus probable pour des repris de justice), ils sont condamnés à 5 ans de prison.

Pour illustrer les définitions énoncées en début d’article, nous pouvons dire que ce jeu est simultané, coopératif, fini et à somme non nulle. De plus, il devient intéressant lorsqu’il est joué avec répétition ; dans ce cas-là, il est à information complète.

Il est intéressant de constater que, suivant les peines adoptées, les réactions peuvent changer du tout au tout.

Pour résumer, nous obtenons cette matrice des gains :

Matrice des gains pour le dilemme du prisonnier

Les stratégies peuvent être diverses. Tout d’abord, de manière intuitive, on peut considérer qu’il existe plusieurs sortes de joueur : les altruistes, ceux qui vont éviter de dénoncer si possible, les « rageux » qui ne dénonceront que par vengeance, et enfin les balances. Leur équilibre de jeu variera sans doute en fonction de leur caractère. Comme nous l’avons vu précédemment avec le PFC, il est possible de déterminer des équilibres de manière plus calculatoire.

Essayons de déterminer l’équilibre du jeu à partir du théorème de Nash.

Tout d’abord, dans le cas d’une partie en une manche, on peut supposer que la sagesse imposerait aux prisonniers de dénoncer au vue du rapport 5ans/20ans.

Pour les parties avec mémoire des précédents coups, il existe deux cas de figure :

  • Si le nombre de manche N est connu : l’équilibre de Nash est « dénoncer ». La preuve se fait par récurrence (en supposant que l’équilibre pour N=1 est « dénoncer » comme l’imposerait sans doute les circonstances). On commence par s’intéresser au dernier coup. Comme il n’y aura pas de sanction au coup suivant, on peut penser qu’il est plus intéressant de dénoncer (comme pour N=1). De ce fait, au coup précédent, on peut anticiper une trahison de l’adversaire et dénoncer. Ce schéma se répète jusqu’au premier coup. On peut remarquer que l’équilibre de Nash est en fait le même pour une partie à répétition que pour une partie en une manche. En effet, la démonstration est aussi valable pour l’hypothèse de départ suivante : pour N=1, la stratégie est de se taire ; la conclusion serait alors qu’il vaut mieux se taire sans arrêt.
  • En revanche, si N est inconnu, aucun équilibre n’est établi, le jeu est alors plus intéressant, sauf si les joueurs (peut-être des prisonniers) ne prennent pas en compte la théorie des jeux ! Impensable.

Pour conclure, il semble préférable pour un prisonnier de vendre son homologue pour ce jeu de valeur !

En réalité, il n’existe pas de stratégie optimale pour ce problème. De nombreuses stratégies plus complexes les unes que les autres ont été développées. Par exemple, la stratégie « Tit for tat » (« œil pour œil ») vise à reproduire le coup précédent de l’adversaire. Au final, entre toutes les stratégies, l’altruisme semble quand même payer.

On retrouve des utilisations de cet exemple dans de nombreux domaines. Ce cas de figure est semblable à la situation suivante : deux concurrents se battent pour obtenir le marché ; dans la plupart des cas, l’un des deux va descendre ses prix pour augmenter ses parts de marché mais va réduire ses bénéfices, l’autre en fera de même pour le rattraper et les deux finiront par y perdre.

Pour en savoir plus

Cet article ne constitue absolument pas un cours sur la théorie des jeux, mais une présentation de celle-ci. Les différents liens de la partie « références » indiquent des articles plus complets sur le sujet (notamment le (4)). La partie théorique peut nécessiter des notions de probabilités ou encore de théorie des ensembles !

 

Références :

(1)    http://www2.lifl.fr/~beaufils/mri/theorie_des_jeux.bruno.pdf

(2)    http://www.cril.univ-artois.fr/~konieczny/enseignement/TheorieDesJeux.pdf

(3)    http://perso.univ-rennes1.fr/thierry.penard/biblio/manueljeux.pdf

(4)    http://www.sciences.ch/htmlfr/mathssociales/mathssthdecision01.php

(6)    http://dhenriet.perso.centrale-marseille.fr/micro/Chapitre1/Chapitre1.htm

 

Cette œuvre est mise à disposition selon les termes de la Licence Creative Commons Attribution – Pas d’Utilisation Commerciale 3.0 non transposé.

Auteurs : Brice Le Dain et Louis Banvillet.

Personnage non-joueur

Dans un jeu vidéo, un personnage non-joueur (PNJ) est un personnage actif ou passif contrôlé par l’intelligence artificielle du jeu. La raison d’être de ces PNJ (NPC pour Non-Player Character en anglais) peut varier. Ainsi, ils peuvent être des opposants aux joueurs (PJ), mais aussi des alliés accompagnant les PJ, ou simplement les habitants de l’univers du jeu vidéo dont la vie se déroule indépendamment de celle des PJ. Sans eux, la vie serait surement plus facile mais perdrait de son intérêt !

Dans cet article, nous allons nous intéresser à cet aspect de l’intelligence artificiel. Nous prendrons notamment  le cas particulier des FPS (First Person Shooters), qui sont des jeux de tir dits « à la première personne », car ils nécessitent une IA particulièrement réaliste et efficace. Dans ce genre de jeu, le niveau du PNJ doit être proche de celui du joueur et ceux-ci doivent résoudre des problèmes divers et variés dans des temps de calcul particulièrement contraignant. Pour ces raisons, les FPS constituent un défi dans le domaine de l’intelligence artificiel.

L’apprentissage par renforcement

Il existe différentes méthodes pour animer un jeu vidéo. On trouve par exemple le Dynamic Scripting dans les phases de combat du très bon jeu Neverwinter Night. Cette méthode consiste en l’adaptation de pondération pour l’activation de règle en fonction du succès du comportement du PNJ.

Moteur de combat du jeu Neverwinter Night

Moteur de combat du jeu Neverwinter Night (1)

Le domaine qui nous intéresse cependant est celui de l’apprentissage par renforcement, car il est utilisé, entre autre, dans les FPS. L’idée est de définir des dépendances entre les variables décrivant l’état du problème. Ces dépendances assurant la recherche d’une solution. Ces techniques restent limitées car il est nécessaire de fournir manuellement une description de la tâche à accomplir, opération difficilement réalisable dans le cadre d’un problème complexe. Dans certains jeux de tir, on utilise le système de classeur qui est un exemple d’utilisation de l’apprentissage par renforcement.

Système de classeur

Ce système est basé sur un ensemble de règles que l’on appelle classeur. Chacune d’entre elles est associée à un poids. Elles possèdent deux aspects : une partie « condition » et une partie « action ».

L’algorithme commence par l’initialisation (aléatoire ou non) du classeur. Alors, pour la situation en cours, on effectue un tirage aléatoire proportionnel aux poids de chaque règle. Si l’action est mauvaise, on diminue le poids de la règle ayant été sélectionnée. Si au contraire elle a été bénéfique, on augmente ce poids.

L’apprentissage consiste à exécuter un algorithme génétique qui va produire d’autres classeurs avec des règles différentes.

Voici un schéma explicatif :

Architecture d’un système de n classeurs

Architecture d’un système de n classeurs (2)

Un exemple intéressant se trouve sur la page Wikipédia.

Un exemple : Counter Strike

Nous allons maintenant présenter une méthode  d’apprentissage par renforcement pour les problèmes de grande taille. Celle-ci est adaptée de manière très intéressante dans le FPS Counter-Strike. Si ce nom ne vous revient pas (i.e. si vous habitez sur la planète mars), voici un résumé du jeu :

  • Deux équipes s’opposent : celle des terroristes (les méchants) qui ont pour objectif de poser une bombe à un certain emplacement, et celle des anti-terroristes (les gentils) qui veulent les en empêcher. Simple comme bonjour!
  • Au cours de la partie, un joueur peut donc se déplacer, sélectionner une arme, tirer, ramasser des munitions, la bombe ou des armes laissées au sol par d’autres joueurs, manger des cacahuètes et lancer des grenades.
  • La victoire est attribuée aux terroristes si la bombe explose ou s’ils déciment l’équipe adverse. Si le temps est écoulé, si la bombe est désamorcée ou encore si les terroristes ont tous été balayés, les anti-terroristes sont victorieux.
Capture d’écran du jeu Counter Strike

Capture d’écran du jeu Counter Strike (3)

Pour appliquer la méthode de l’apprentissage par renforcement, il est nécessaire de définir des récompenses pour les PNJ, en voici un exemple :

  1. -1 lorsque le PNJ est tué ;
  2. +10 lorsque le PNJ tue un adversaire ;
  3. +1 lorsque la bombe est posée.

La seconde étape consiste à établir l’ensemble des états possibles, ce qui se fera par le biais de variables aléatoires. Chaque variable aléatoire correspond à une perception de l’agent (ici le PNJ) de son environnement.

Voici une proposition:

Perceptions des PNJ (SiteA et SiteB désignent respectivement les sites de la bombe A et B, SiteT et SiteC les points de départ des terroristes et des anti-terroristes)

Perceptions des PNJ (SiteA et SiteB désignent respectivement les sites de la bombe A et B, SiteT et SiteC les points de départ des terroristes et des anti-terroristes) (4)

Un rapide calcul montre que, pour un terroriste, les perceptions assurent 480 états possibles (seulement 80 pour les anti-terroristes), ce qui permet de couvrir de nombreuses situations du jeu.

Ensuite, on établit les actions possibles, celles-ci permettent de passer d’un état à un autre.

Voici une proposition:

Liste des actions possibles

Liste des actions possibles (4)

Pour la résolution du problème défini dans le jeu Counter-Strike, il ne faut pas oublier de prendre en compte que les fonctions de récompense sont stochastiques ! Evidemment… Par exemple, pour la même perception « Le PNJ voit une cible » et la même action « Shoot », la récompense obtenue change si la cible est morte, si le PNJ est mort (il s’est fait toucher par sa cible ou un autre joueur), si la cible disparaît du champ de vision ou bien encore s’il ne reste plus de munitions.

On applique alors l’algorithme suivant : on initialise le classeur avec un certain nombre de règles (disons cent règles). On pourra les choisir de manière aléatoire ou bien assurer une liste de règles issue du “bon sens”. En pratique il est préférable d’utiliser la méthode aléatoire pour des raisons pratiques, le nombre de règles étant trop important pour que l’on puisse associer à chaque règle une définition rationnelle.

Dans notre cas, compte tenu des choix effectués pour établir l’état du système, les règles peuvent s’écrire, pour un terroriste : [a, b, c, d, e, f, g -> p] avec a, b, c, d, e, f, g qui peuvent prendre six valeurs distinctes correspondant au cas siteA, siteB, siteC, siteT, ailleurs ou indifférent ; et p désigne l’une des six actions possibles.

A chaque règle, on associe un poids pris aléatoirement. Il est à noter que le nombre de règles que l’on souhaite définir est directement lié aux performances de l’ordinateur. Plus on a de règles, meilleure sera l’analyse de la situation et, par suite, meilleure sera la réponse du PNJ, mais cela nécessitera un temps de calcul plus important.

Il faut alors mettre en œuvre un algorithme permettant les mutations des règles ainsi que le croisement de deux règles. Plus précisément, il s’agit de sélectionner des règles suivant un certain critère, les règles à forte pondération sont privilégiées, elles seront modifiées génétiquement et génèreront cent nouvelles règles dans le classeur.

Pour chaque situation, l’IA fournira la perception. Parmi les règles du classeur, on en sélectionne une de façon aléatoire (avec pondération). Ceci définit l’action à mener par le PNJ.

Le résultat de l’action implique une récompense pour la règle choisie (elle peut ainsi être bonifiée ou non suivant la réussite de l’action).

En pratique, il faut augmenter le nombre de perceptions (nombre d’ennemi et nombre d’allier) ou augmenter la sensibilité d’une perception.

Travail en binôme

Le travail en équipe, c'est beau!

Le travail en équipe, c'est beau! (3)

Cette méthode est correcte, mais ne permet pas, telle que décrite, de prendre en compte le travail d’équipe qui donne un supplément d’âme à un jeu vidéo. Pour obtenir un résultat convenable, on peut prendre en compte la perception commune aux deux éléments. De nouvelles règles propres au binôme sont alors établies.

D’autres méthodes

L’apprentissage par renforcement est aussi simple qu’efficace. Des progrès ont cependant été fait dans ce domaine. On pense par exemple à des algorithmes plus pointus tels que ceux proposés par Sutton :

http://webdocs.cs.ualberta.ca/~sutton/book/ebook/the-book.html

L’algorithme SDYNA offre également des possibilités intéressantes. Voici une vidéo de démonstration de l’algorithme SDYNA.

 

Références :

(1) http://www.gamerevolution.com/preview/neverwinter-nights

(2) http://w3.lara.univ-tlse2.fr/entrelacs/IMG/pdf/Tambellini_comportements.pdf

(3) http://www.moddb.com/games/counter-strike

(4) http://people.bordeaux.inria.fr/degris/papers/DegrisRLPNJ.pdf

 

Cette œuvre est mise à disposition selon les termes de la Licence Creative Commons Attribution – Pas d’Utilisation Commerciale 3.0 non transposé.

Auteurs : Brice Le Dain et Louis Banvillet.

Le « pathfinding » dans les jeux vidéo

Aujourd’hui, nous allons nous intéresser à un problème très courant dans les IA des jeux vidéo : la recherche de chemin (ou « pathfinding »). Le problème est simple, comment se déplacer d’un point A à un point B avec, si possible, le « meilleur » itinéraire ?

Le but est de trouver le chemin le plus court le plus vite possible! (7)

L’efficacité de l’algorithme utilisé est primordiale au niveau de la jouabilité et du réalisme. Combien de fois a-t-on vu des PNJ traverser un mur ou bien rester bloqués par une caisse ? Un exemple d’utilisation courant est celui du jeu de stratégie (comme Warcraft), où le joueur peut demander à une ou plusieurs unités de se déplacer vers un point pour qu’il défende sa citadelle au prix de sa vie. Les joueurs étant parfois nerveux, l’IA ne peut se permettre de parcourir toutes les impasses de la carte avant d’arriver sur les ruines de son ancien campement. Le pathfinding constitue donc un pan fondamental de l’IA dans les jeux vidéo.

Le PathFinding trouve des applications dans de nombreux domaines autres que les jeux vidéo (robotique, routage internet, etc.). De nombreux algorithmes permettent de résoudre ce problème et tous ont des particularités en matière de précision et de rapidité. L’univers du jeu vidéo est extrêmement contraignant, ce qui limite les algorithmes utilisables. En effet, les solutions doivent utiliser un minimum de ressources et être les plus rapides possibles, au détriment parfois de la précision. Par ailleurs, il faut parfois prendre en compte des contraintes additionnelles telles que la gestion d’un groupe d’unité, ou le fait que l’environnement soit évolutif.

Les algorithmes les plus utilisés sont sans aucun doute celui de Dijkstra et l’algorithme A*. Même si ceux-ci trouvent une application idéale dans les jeux en 2D, nous verrons par la suite qu’ils sont également très utilisés dans les jeux en 3D en complément d’autres méthodes.

L’algorithme de Dijkstra

La théorie expliquant cet algorithme étant assez compliquée, nous allons essayer de le simplifier et d’en donner les idées directrices. Pour plus de détails, un tutoriel est disponible sur le fameux site du zéro.

Tout d’abord, cet algorithme demande des notions de base en théorie des graphes. Voici un exemple de graphe :

Exemple de graphe (6)

Un graphe se compose de nœuds (ici des villes), et d’arêtes (les jointures entre différents nœuds), ces dernières étant  affectées d’un poids (ici le nombre de kilomètres séparant chaque ville l’une de l’autre). Pour plus d’information sur la théorie des graphes : Wikipedia.

Principe : il s’agit de trouver le chemin ayant le poids le plus faible (somme des poids des arêtes qui le composent) entre 2 nœuds s1 et s2.

Résolution : on cherche à construire une succession de sous graphe G’ de G tel que tout sommet s de G’ ait une distance minimale avec s1 dans G. Voici l’algorithme que l’on peut suivre :

  • On initialise le premier sous-graphe à s1 seul. Les autres sommets sont dits « non-marqués » (on affecte la valeur +∞ à leur poids).
  • Tant qu’il existe un sommet non marqué :
    • On choisit le sommet non marqué a de plus faible poids P(a)
    • On le marque
    • Pour chaque sommet b voisin de a, on lui attribue le poids P(b) = min(P(b), P(a) + dist(a,b)).

L’algorithme se termine quand G’ devient un arbre couvrant (contenant s1 et s2) ou que tous les nœuds d’intérêt (nœuds qui ont plus d’un voisin) sont dans G’.

L’algorithme A*

L’algorithme A* est de loin le plus utilisé dans les jeux vidéo car il répond bien aux contraintes imposées par ceux-ci. Il constitue une amélioration de l’algorithme de Dijkstra. On dit de cet algorithme qu’il est « informé », ce qui signifie qu’il utilise une fonction (dite « heuristique ») qui estime la distance à l’arrivée. Contrairement à l’algorithme de Dijkstra (dit « aveugle »), A* oriente sa recherche au lieu d’explorer toutes les zones. Le gain de temps est conséquent.

La question réside donc dans la façon de calculer la distance heuristique pour orienter au mieux l’algorithme. La fonction heuristique évalue d’abord les sommets proches de l’arrivée ou du départ (plus proche du raisonnement humain). La fonction heuristique est une caractéristique de la recherche « gloutonne ». Il existe deux principales heuristiques de distance dans les jeux vidéo : la distance euclidienne (vol d’oiseau) et la distance de Manhattan (jeux se déroulant sur un damier).

De gauche à droite : Dijkstra, glouton, A*. (6)

Dijkstra et A* retourne un chemin optimal contrairement à la recherche gloutonne. Cependant, Dijkstra explore beaucoup trop de cases.

Autres solutions

A* est satisfaisant pour la plupart des jeux. Cependant, avec les contraintes toujours plus importantes imposées dans les jeux vidéo (destruction de terrain par exemple), d’autres algorithmes ont été développés. Voici une courte description des principaux algorithmes :

  • D* permet de redéfinir le chemin si l’IA rencontre un obstacle
  • IDA* n’explore qu’un seul chemin à la fois (ce qui permet une économie d’énergie), il arrive cependant que certains sommets soient revisités plusieurs fois
  • HPA* établi une hiérarchie entre les différentes zones d’une carte

Voici un site qui permet de tester les différents algorithmes avec divers procédés de résolution.

Les tests permettent une excellente comparaison des différents algorithmes et fonctions heuristiques.

Cas de jeux en 3D

Ces algorithmes sont très adaptés aux graphes abstraits, mais on se voit mal proposer au joueur une carte sous forme de graphe vu dans l’exemple de Dijkstra (cf. ci-dessus).

Plus la résolution des cartes est importante, plus l’abstraction inhérente aux différents algorithmes vu précédemment semblent compromettante pour les adapter au pathfinding. La question est donc la suivante : comment adapter ces techniques aux cartes en 3D ?

Il existe deux principales méthodes :

  • Le système des waypoints : on plaque un échiquier sur la carte et chaque case constitue un sommet du graphe. On applique alors les méthodes vues précédemment.
  • Le mesh de navigation : on fabrique un graphe à partir de polygones. Les personnages peuvent se déplacer à l’intérieur de ceux-ci. Les polygones doivent être de taille suffisamment réduite pour y utiliser la méthode A*.

Exemple de navigation mesh (6)

Il existe évidemment d’autres méthodes de pathfinding qui ont plus ou moins de succès. On pense par exemple aux réseaux de neurones utilisés dans Black and White ou les algorithmes génétiques de Creatures.

PathEngine est une entreprise spécialisée dans le développement de logiciels dédiés au pathfinding !

 

Sources :

(1) Wikipedia (http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm)

(2) Site du zéro (http://www.siteduzero.com/tutoriel-3-35706-le-pathfinding-avec-dijkstra.html)

(3) Geeklab (http://geeklab.free.fr/wordpress/?p=292)

(4) GameCorp (http://www.game-corp.net/article-12-les-algorithmes-de-pathfinding.html)

(5) developpez.com (http://khayyam.developpez.com/articles/algo/astar/)

(6) Merwan Achibet (http://merwanachibet.free.fr/public/iajv.pdf)

(7) http://qiao.github.com/PathFinding.js/visual/

 

 

Cette œuvre est mise à disposition selon les termes de la Licence Creative Commons Attribution – Pas d’Utilisation Commerciale 3.0 non transposé.

Auteurs : Brice Le Dain et Louis Banvillet.

Les origines de l’intelligence artificielle

L’introduction du sujet vous avait mis l’eau à la bouche ? Vous voulez en savoir plus sur l’histoire de l’intelligence artificielle ? Cet article répondra sans doute à vos attentes.
Tout d’abord, il faut savoir que l’histoire de l’IA est liée à deux notions qui s’inscrivent dans deux périodes de l’histoire bien distinctes :

  • 17ème siècle : l’étude de la rationalisation du système de pensée humain qui commence avec la modélisation mathématique de la pensée par Pascal et Leibniz. Boole définissait ensuite le « ET », le « OU » et le « NON » qui suffisait à définir un système d’encodage de la logique.
  • A partir de 1936 : Alan Turing développe les idées fondatrices de l’informatique. S’en suit alors une croissance exponentielle dans ce domaine avec des machines toujours plus puissantes. Le premier programme se rapprochant du système de pensée humain n’apparut toutefois qu’en 1970, créé par Terry Winograd. Ce programme répond au doux nom de SHRDLU.

Cependant, malgré la croissance de la puissance des ordinateurs, l’IA n’a pas énormément évolué dans le domaine scientifique car l’intérêt d’une telle recherche n’était pas assez commercial.

C’est dans un tout autre domaine que l’IA va évoluer : l’univers des jeux vidéo. Cette industrie, née dans les années 70, s’est développée à une vitesse phénoménale, aussi bien grâce à l’évolution de la technologie que par la créativité grandissante des développeurs, condamnés à innover pour satisfaire un client toujours plus exigeant.

Dans un premier temps, les développeurs délaissaient allègrement la partie IA des jeux vidéo pour se consacrer à l’amélioration des graphismes et autres effets sonores. Ce qui pouvait avoir pour effet de réduire la sensation d’immersion des joueurs dans l’univers virtuel. Des bots qui vont toujours tout droit et qui se précipitent dans les trous, ou qui butent dans tous les murs. Un humain serait-il aussi ridicule ? Sans alcool, non.

Les Arbres de recherche

Nous allons commencer, dans cet article, par vous présenter des techniques qui ont joué un rôle de précurseur dans l’univers des IA : les arbres de recherche. Celles-ci s’adaptent tout particulièrement aux jeux « classiques » (jeux de plateau tour par tour) : échecs, dames, go, cartes…

Le principe de l’IA est simple :

  1. Elle recherche les séquences de coup jouable d’une certaine longueur
  2. Elle évalue la position résultante de la séquence
  3. Elle choisit le coup optimal

Pour expliquer les algorithmes utilisés dans ces jeux, nous allons prendre le cas particulier du jeu d’échec.

Algorithme du MinMax

Pour une position donnée des pièces sur l’échiquier, on va construire un arbre qui contient les séquences (d’une certaine longueur) de coup jouables. A partir de là, on évalue à l’aide d’une fonction d’évaluation les positions résultantes de chaque séquence. On obtient l’arbre suivant :

Arbre de recherche 1On considère ici une séquence avec deux coups. Plus la valeur de la ligne C est haute, plus la position est intéressante pour l’IA. Par conséquent, l’adversaire n’a pas intérêt à les choisir. Cet algorithme se base donc sur une hypothèse fondamentale : l’adversaire joue pour gagner et va donc maximiser son score, c’est-à-dire minimiser le score de l’IA. On remplit de cette manière la ligne B (en choisissant la valeur minimale de chaque sous arbre) :

Arbre de recherche 2Pour finir, on choisit la valeur maximale de la ligne B : 5. On obtient, avec cet exemple basique, l’idée directrice de l’algorithme MinMax : maximiser le minimum que peut nous offrir l’adversaire.

Le principal inconvénient de cette technique vient du fait que l’on explore l’arbre dans son intégralité alors que certaines branches pourraient être éliminées dès le début (sachant que chaque nœud a de l’ordre de 35 fils). Ce problème est corrigé par l’algorithme d’élagage alpha-beta.

Alpha-beta

Le principe du MinMax est conservé. On l’améliore cependant en éliminant les séquences inintéressantes.

Arbre de recherche 3Ici, par exemple, on élimine la branche verte pour la raison suivante : la valeur « 2 » de la case précédente est inférieure la valeur « 5 » de la branche bleue ; étant déjà inférieure, il n’y a aucune raison de continuer d’espérer une stratégie plus intéressante dans ce sous arbre.

L’idée s’adapte évidemment au cas suivant :

La valeur « 6 » (case précédent la case verte) est supérieure à « 5 » (case rouge).

La fonction d’évaluation

Le rôle de cette fonction est de comparée deux positions. La difficulté de développer une IA performante repose en grande partie sur la construction d’une fonction d’évaluation pertinente et performante. La difficulté réside dans le fait que le nombre de possibilité est énorme. Les algorithmes précédents fournissent un grand nombre de positions. Si la fonction d’évaluation réclame trop de calculs, cela risque de nécessiter des ressources mémoires colossales. Une autre difficulté réside dans le “calibrage” de la fonction (définir la gravité ou l’intérêt d’une position). Une position n’ayant pas la même valeur au cours de la partie.

Voici une fonction (partielle) permettant le développement d’une IA correcte :

Chaque pièce se voit attribuer une valeur. On somme les valeurs des différentes pièces de l’IA pour obtenir la force de l’IA (même opération pour l’adversaire). Ces grandeurs ne tiennent néanmoins pas compte des positions des pièces et notamment du contrôle ou de l’occupation du centre de l’échiquier ! Afin de prendre en compte ces éléments, des bonus/malus  viennent moduler la force. Par exemple une position dans laquelle une pièce majeure (pas les pions ni le roi) serait immobilisée donnera un malus. Tandis que le fait de positionné un fou sur une diagonale ouverte donnera un bonus. Egalement dans le but de privilégier la zone centrale de l’échiquier, on peut attribuer une valeur à chaque case de telle façon que, plus en s’éloigne du centre, plus la valeur diminue. Au final, l’évaluation est donnée par la force de l’IA moins la force de l’adversaire auquel on ajoute les bonus et soustrait les malus.

De plus, dans le but de démarrer efficacement la partie, l’ordinateur doit être doté d’un stock d’ouverture de telle manière que, si une position enregistrée est reconnue, alors l’ordinateur pourra lui associer le meilleur coup à jouer.

Enfin, pour terminer efficacement la fin de partie, il faut constater la complexité stratégique due au fait que les pièces sont sur un “plateau plus ouvert” et où il n’est pas rare que les séquences de coup permettant le gain dépassent la profondeur de l’arbre. Actuellement, la solution utilisée consiste en des tables qui analysent toutes les configurations avec cinq pièces majeures ou moins. Il ne reste plus qu’à implémenter une analyse rétrograde pour trouver la meilleure solution.

Bilan de l’IA dans les jeux « Classiques »

Ces stratégies ont beau être les précurseurs de la plupart des stratégies d’IA dans les jeux vidéo, le temps de calcul très important lié au nombre de coups élevé ne la rend adaptable qu’à certaines composantes des IA. On peut donc la retrouver, par exemple, dans certains jeux où il faut conquérir des zones.

Après cette entrée en matière sur les origines de l’IA dans les jeux vidéo, nous verrons, dans le prochain article, la problématique du « pathfinding » (recherche de chemin par un bot).

Références :

(1) http://bobots.e-monsite.com/pages/projet-bobots/ia-et-jeux-videos.html

(2) http://www.site-naheulbeuk.com/utbm/IA41%20CM11-12.pdf

 

 

 

Cette œuvre est mise à disposition selon les termes de la Licence Creative Commons Attribution – Pas d’Utilisation Commerciale 3.0 non transposé.

Auteurs: Brice Le Dain et Louis Banvillet.

Introduction à l’intelligence artificielle dans les jeux vidéo

Vous n’avez pas d’amis ? L’intelligence artificielle est un moyen employé par les différents concepteurs de jeux vidéo pour vous en donner l’illusion. Vous pouvez ainsi jouer tout seul dans votre chambre jusqu’à trois heure du matin, ceci afin de déjouer les plans machiavéliques des trois lignes de codes qui ont capturé la princesse Peach et qui vous lancent des tonneaux du haut de votre écran. Vous aurez reconnu le jeu Donkey Kong sorti en 1981 sur les bornes d’arcade.

Jumpman (futur Mario) tente de sauver sa bien-aimée pour la première fois d'une longue série (1)

Cela peut paraître évident, mais ce jeu n’est que l’aboutissement de la pensée philosophique de Pascal qui visait à rationaliser le « système de pensée de l’être humain » (dans cette optique, il créa la première machine à calculer).

Bien que le résultat soit satisfaisant, l’industrie du jeu vidéo ne s’est pas arrêtée là. Depuis, de nombreuses techniques ont été mises en œuvre afin de parfaire l’illusion suivante : « j’ai un ami dans ma télévision ». Cependant, si le joueur donne l’impression de combattre ses propres démons, ce n’est pas tout à fait vrai ; il se bat en réalité contre les créateurs de cette IA qui ont, de leur côté, essayé d’utiliser les techniques les plus à mêmes de rendre le joueur accro à leur jeu vidéo. Le jeu Black and White (2001, Lionhead Studios) est un précurseur et un maître dans le genre.

Black and white 2 – Ce jeu vous permet d'incarner une divinité bienveillante... ou pas ! (2)

Ces techniques varient énormément suivant le jeu en question. Notre étude visera donc, dans un premier temps, à faire un état des lieux des différentes technologies en place. Nous détaillerons les principales, des plus simples aux plus sophistiquées. Nous tenterons enfin de prévoir les évolutions à venir dans ce domaine.

Références :

(1) http://gamesdbase.com/game/arcade/donkey-kong-ii-jumpman-returns.aspx

(2) http://forum.hardware.fr/hfr/JeuxVideo/PC/tomik-black-white-sujet_65856_1.htm

Cette œuvre est mise à disposition selon les termes de la Licence Creative Commons Attribution – Pas d’Utilisation Commerciale 3.0 non transposé.

Auteurs : Brice Le Dain et Louis Banvillet.

Moteurs de jeux : synthèse et plan du rapport final

Synthèse

Dans le cadre de ce projet de veille technologique, nous avons tenté de dresser un état de l’art des moteurs de jeux-vidéos. Nos considérations ont principalement été d’ordre technique afin de bien comprendre et expliciter l’intérêt des fonctionnalités proposées par les moteurs de jeux modernes. Les fonctionnalités auxquelles nous nous sommes intéressés sont :

  • Le pipeline 3D (affichage)
  • Les moteurs physiques
  • Les langages de script
  • La recherche de chemins
  • Les systèmes de particules

Cette sélection n’est pas exhaustive (on aurait pu parler d’intelligence artificielle, de spatialisation du son, d’animations de personnages ou encore de réseau) mais elle est assez variée pour proposer un aperçu du fonctionnement global d’un moteur de jeu (ou tout simplement d’un jeu). Ce fut aussi l’occasion de revenir parfois quelques décennies en arrière pour comprendre comment certaines fonctionnalités, comme la recherche de chemins ou les langages de script, avaient atteint leur état actuel.

Au final, il semble cependant que le domaine où les moteurs évoluent le plus et qui se prête le mieux à une veille technologique ce n’est pas (plus) leur fonctionnement mais leur diffusion (et leurs modèles économiques). C’est en tout cas ce que nous avons découvert avec nos articles sur l’aspect multiplateforme de moteurs et celui sur les moteurs à faible coût.

Plan du rapport final

  1. Introduction
    • Contexte
    • Problématique
  2. Fonctionnalités d’un moteur de jeu
    • Affichage
    • Physique
    • Scripting
  3. Le marché des moteurs de jeux
    • Multiplateforme
    • AAA vs Indie

Licence Creative Commons

Particules

Après nous êtres intéréssés dans notre précédent article aux fonctionnalités de pathfinding proposées par les moteurs de jeux, nous allons aujourd’hui discuter d’une autre fonctionnalité importante : les systèmes de particules.

Pour quoi faire ?

Si vous avez lu notre article « Un moteur de jeux, ça fait quoi ? », vous savez déjà que dans les jeux les personnages et les décors sont représentés par des maillages de triangles appelés mesh sur lesquels on plaque des textures. Voici par exemple le mesh d’un petit lapin.

Un mesh de lapin

Un mesh de lapin (source : http://www.ceremade.dauphine.fr/~peyre/geodesic_computations/)

Le procédé est très versatile mais il admet tout de même ses limites : on ne peut pas décemment demander à un artiste de modéliser une flamme ou de la fumée avec uniquement des petits triangles. Dans la capture d’écran de Dark Souls ci-dessous, on imagine à peu près le maillage du personnage ou du décor mais pas celui de la flamme. Bravo, vous venez de repérer un effet de particules !

Dark Souls

Un effet de particules dans Dark Souls (source : http://www.giantbomb.com/dark-souls/61-32697/user-reviews/?review_id=21106)

D’une manière générale, les effets de particules servent à faire tout ce qu’il est difficile de modéliser avec un mesh traditionel : le feu, la fumée, l’eau (pas toujours), les effets spéciaux (magie, etc.) ou encore les explosions.

Comment ça marche ?

Un système de particules n’est pas une simulation physique du phénomène qu’il représente, le principe est le même pour tous les types d’effets (alors qu’une cascade et une flamme n’ont pas grand chose à voir physiquement). Notre explication du fonctionnement d’un système de particule va s’appuyer sur l’exemple concret de la réalisation d’un effet de particules qui ressemble à une flamme. L’outil utilisé pour cet exemple est un système de particules fait maison (en langage HaXe).

Voici la “particule” de base qui sera l’unique texture utilisée (ici sur fond noir). C’est un simple dégradé radial blanc.

Une particule

Une particule

Le principe de base consiste à definir une zone qui va émettre des particules, plusieurs centaines par seconde, et leur attribuer des paramètres de base (taille, couleur, transparence, etc.). Ces particules ont une durée de vie limitée (de l’ordre de quelques secondes) et sont soumises à toute sortes d’effets : changements de taille, de couleur ou encore déplacements. Ici on va émettre des particules de couleur orange. Pour plus de diversité on laisse une part de hasard dans l’attribution de la couleur, toutes nos particules n’auront pas exactement le même orange.

Une particule colorée

Une particule colorée

Notre zone d’emission étant un petit disque, nos particules vont démarrer leur vie proche les unes des autres et se superposer un peu pour générer une forme aléatoire. C’est l’occasion d’expliciter un principe important pour le résultat final : les modes de fusion. Habituellement, la superposition d’un pixel de couleur [R1,G1,B1,A1] (pour red, green, blue, alpha — alpha étant l’opacité) par dessus un pixel de couleur [R2,G2,B2,A2] est représentée par un pixel de couleur [R1*A1 + R2*A2*(1-A1), G1*A1 + G2*A2*(1-A1), B1*A1 + B2*A2*(1-A1), A2 + A1*(1-A1)]. Cela produit un résultat illustré par l’image ci-dessous :

Utilisation d'un canal alpha

Mode de fusion « normal » (source : http://fr.wikipedia.org/wiki/Alpha_blending)

Ici nous allons utiliser un mode de fusion additif et l’on va additionner les composantes (rouge, vert, bleu et alpha) des pixels qui se superposent. Voici ce que l’on obtient :

Modes de fusion

Modes de fusion

Ensuite, on paramètre l’émetteur pour que les particules diminuent de taille au cours de leur vie et on applique un champ de force à notre ensemble de particules pour les faire se déplacer vers le haut. Le résultat est une flamme à peu près convaincante que vous pouvez voir en mouvement ici :

Résultat final

Résultat final

Et dans un moteur ?

Dans le cas d’un moteur de jeu en 3D comme le Source Engine ou l’Unreal Engine on suit exactement le même procédé en dessinant le résultat sur un rectangle (deux triangles) qui est toujours face à la caméra. Une telle surface de dessin s’appelle un billboard et elle est surtout connue des joueurs car elle servait à faire la végétation dans les vieux jeux, comme ici Colin McRae Rally 2 sur Playstation.

De la végétation sur des billboards

De la végétation sur des billboards dans Colin McRae Rally 2 (source : http://www.romulation.net/PSX/Colin_McRae_Rally_2.0_%5BU%5D%5BNTSC-U%5D_%5BSLUS-01222%5D.rar.html/)

Les particules sont omniprésentes dans les jeux réalisés avec les moteurs modernes. Elles sont peu coûteuses à afficher et très agréables à l’oeil (bien que la plupart des joueurs ne soit même pas conscient de leur présence). Elles ont toutefois leurs limites. Puisqu’elles ne sont affichées que sur une surface en deux dimensions, elle n’ont pas de volume propre et on peut difficilement faire passer un personnage à travers de la fumée (faite en particules) de manière réaliste. Une solution à ce type de problèmes existe et s’appelle très justement le brouillard volumétrique. Si le sujet vous intéresse je vous engage à lire (ou au moins regarder les images très explicites) cet excellent article sur le sujet.

Enfin, voici une vidéo pour vous rincer l’oeil avec quelques effets de particule impressionants (et précalculés).

Licence Creative Commons

Pathfinding

« Votre épée à la main, vous franchissez fièrement le seuil de l’antre du dragon paré à affronter la bête pour piller son trésor et délivrer la princesse. Le silence se fait autour de vous et la sueur vous perle sur le front. Soudain le monstre apparaît ! Gigantesque, effrayant et véloce comme le décrivent les légendes, le dragon ne vous accorde aucune attention…et se précipite aussitôt vers le mur le plus proche qu’il tente déséspérement de traverser. »

Voici une expérience que bien des joueurs ont déjà du faire, celle d’affronter une IA qui semble avoir des difficultés à naviguer dans l’espace (comme l’illustre à merveille cette vidéo). Le pathfinding (ou « recherche de chemins » en bon français) est un problème mathématique bien plus vieux que le jeu vidéo qu’il est nécessaire de résoudre pour programmer une intelligence artificielle digne de ce nom. De nos jours, les moteurs de jeux proposent (presque) tous une solution intégrée pour faciliter la vie des développeurs et leur éviter de réinventer la roue.

Un peu d’histoire

Prenons le problème à la source :

Lievro VS cailloux

Le grand problème du pathfinding

Voici une (fausse) capture d’écran de Secret of Mana qui va servir d’illustration à notre problème. Il est du devoir des développeurs de doter le lievro (la créature jaune en bas à droite) d’une intelligence suffisante pour aller mordre sauvagement le personnage du joueur (en haut à gauche). Seulement voilà, pour que le jeu soit ne serait-ce que vaguement cohérent, il ne faut pas que le lievro marche sur les obstacles (ici des cailloux) sur lesquels le joueur ne peut pas se déplacer. C’est de cet état de fait que nait le problème du pathfinding.

A l’époque de Secret of Mana, les consoles avaient une capacité de calcul très réduite et largement insuffisante pour traiter naïvement la quantité astronomique de chemins qui vont du lievro au personnage (en considérant des déplacements de 1 pixel de long). Une simplification évidente du problème consiste à re-échantilloner l’espace comme le montre l’image ci-dessous. C’est d’autant plus facile que cette discrétisation en tiles (des carrés de taille régulière) est déjà présente et nécessaire au stockage des décors.

Discrétisation

Discrétisation

Le problème peut alors être traité avec un algorithme classique comme celui de Dijkstra. Le principe de cet algorithme est de considérer les tiles voisins du point de départ puis les voisins de ces voisins etc. Au fur et à mesure, on veille à ne pas considérer deux fois le même tile et à retenir pour chaque tile le chemin le plus court qui a permis d’y arriver. L’algorithme termine lorsque l’on en vient à considérer le tile où l’on souhaitait atterir (succès) ou lorsque l’on a plus de tiles à considérer (echec, la destination est inatteignable). Une illustration animée et une description un peu plus complètes de cet algorithme sont visibles sur Wikipedia. Dans le cas de notre lievro sauvage, on aboutit au résultat suivant :

Résultat

En blanc, le chemin obtenu

L’algorithme le plus populaire dans les jeux vidéo (en 2D comme celui-ci) est une variante de l’algorithme de Dijkstra appelée A* (à prononcer A star pour briller en société). La nuance réside dans l’étiquette attribuée aux tiles qui n’est plus seulement fonction de la distance parcourue pour les atteindre mais également de la distance (estimée) restant à parcourir. L’estimation de la distance restante (appelée heuristiques) la plus courante est la distance Manhattan entre le point courant et l’arrivée. C’est tout simplement la distance en X additionnée à la distance Y entre les deux points (comme quand vous vous déplacez dans Manhattan, il n’y a pas de diagonales).
Cette variante a l’avantage d’avoir la même complexité algorithmique (calculer des distances Manhattan, c’est à peu près gratuit en terme de complexité) et de réduire le nombre de tiles considérés dans les cas un peu labyrinthiques qui sont légion dans les jeux vidéo.

Revenons en 2012

C’est bien gentil tout ça mais en 2012, un décor de jeu vidéo ça ressemble plutôt à ceci :

Hawken

Hawken

Libéré de leurs contraintes techniques, les décors ont beaucoup changé. Ils sont devenus beaucoup plus grands, les obstacles n’ont plus tous la même taille et ils sont en 3D. Discrétiser un tel décor avec une grille en 3D n’a aucune chance de fonctionner car il faudrait un pas de discrétisation beaucoup trop petit et un nombre astronomique de tiles. Mauvaise idée.

Les algorithmes issus de la théorie des graphes (parce que, au cas où vous ne l’auriez pas remarqué, c’est de ça qu’on parle) comme Djikstra et le A* étant encore ce qu’on a de mieux sous la main, la solution est de changer la façon dont on transforme notre problème en un graphe mathématique. Il existe deux principales approches qui sont utilisées dans les jeux en 3D (et dans certains jeux modernes en 2D) : les systèmes à base de waypoints et ceux à base de navigation mesh.

Un système à base de waypoints représente le graphe de navigation par un semble de noeuds reliés par des arêtes rectilignes sur lesquels les personnages peuvent se déplacer. Il est assez relativement facile de positionner automatiquement ces points de navigation avec des algorithmes comme la triangulation de Delaunay ou de confier cette tâche à un level designer. Voici un exemple en image :

Un graphe de waypoints (source : Michael Grenier)

Un graphe de waypoints (source : Michael Grenier)

Les modèles à base de navigation mesh sont un peu plus compliqués à manipuler et à définir automatiquement mais ils ont plusieurs avantages en terme de résultat à l’écran. L’idée est de définir un graphe de navigation dont les noeuds sont des polygones convexes (des zones sans obstacles) et les arêtes sont des côtés communs à plusieurs de ces polygones. Voici une image tirée du même article qui illustre le principe :

Un navigation mesh (source : Michael Grenier)

Un navigation mesh (source : Michael Grenier)

Le principal avantage des navigation mesh est que l’on peut faire naviguer les personnages dans des polygones entiers et pas seulement le long de segments prédefinis. Une fois muni d’un tel graphe, on peut de nouveau appliquer des algorithmes de Dijkstra ou A* pour trouver des plus courts chemins. Ouf!

Notre histoire ne s’arrête cependant pas ici et les jeux modernes bénéficient de quelques fioritures qui rendent le tout plus agréable à l’oeil. Dans les jeux qui mettent en scène beaucoup de personnages, les programmeurs ajoutent des comportement de flocking qui permettent de gérer intelligement des groupes d’unités. L’approche la plus courante consiste à calculer un chemin pour le groupe en tant qu’entité unique et à déplacer chaque unité en fonction du chemin suivi par le groupe et d’une force de répulsion qui l’éloigne des autres unités du groupe (pour les empêcher de se chevaucher). Le résultat est très visible dans Starcraft II, au bout d’une minute dans cette vidéo. Un autre ajout courant aux technologies de pathfinding est le lissage des chemins calculés au moyen de courbes de Bézier.

Les moteurs de jeux les plus populaires du marché (Unreal Engine 3, Source Engine, etc.) intègrent tous leur propre technologie de pathfinding. Certaines entreprises sont entièrement dédiées au développement de middleware sur le sujet, comme par exemple PathEngine (dont la licence coûte tout de même entre 4500€ et 25000€). C’est à se demander pourquoi les dragons se plantent toujours dans les décors mais j’ai bien ma petite idée sur la question !

Sources et saines lectures :
Develop Online
AI blog
Gamasutra
Michael Grenier
Amit’s Game Programming Information

Licence Creative Commons