If you can't read please download the document
Upload
marcy
View
31
Download
0
Embed Size (px)
DESCRIPTION
Prise de décision dans les shooters. Sandrine Buendia Coralie Gallien Romain Almes Romain Richard. TER 08/09. Introduction. Les systèmes de jeux deviennent de plus en plus complexes, nécessitant que l’Intelligence Artificielle progresse elle aussi en parallèle. - PowerPoint PPT Presentation
Citation preview
Les systmes de jeux deviennent de plus en plus complexes, ncessitant que lIntelligence Artificielle progresse elle aussi en parallle.
Dans ce contexte, nous avons implment le comportement de PNJ (Personnages Non Joueurs) dans un jeu de type shooter grce un planificateur.
Quest-ce quun shooter ?
Concernant la prise de dcisionLIA caractrise donc toute prise de dcision dun ou plusieurs personnages dans un jeu, or, le but de lIA dans un jeu vido est de donner lillusion dun comportement intelligent.
Cest pourquoi nous sommes pass dune FSM (machine tats finis) un planificateur.
Organisation du travail
PathfindingSandrine B. & Romain A.PlanificateurCoralie G. & Romain R.Modlisation dans le jeuCoralie G, Sandrine B., Romain A. & Romain R.
Cahier des chargesPathfindingPlanificateurEntit rutilisableDmonstrationConclusion
Cahier des chargesPathfindingPlanificateurEntit rutilisableDmonstrationConclusionCharger lenvironnement de jeu
Construire lintelligence des personnages
Obtenir un rendu attirant et simple
Garder un droulement fluide du programme
Arriver des temps de chargement rapide
Le pathfinding cest quoi?Trouver un chemin entre deux points dans un environnement, tout cela en respectant les contraintes (environnementales, temps limite, contraintes de ressources, )Cahier des chargesPathfindingPlanificateurEntit rutilisableDmonstrationConclusion
Pathfinding existant dj dans UT2004 : Aucune interprtation de lenvironnement 3D entourant les PNJ
Systme de nuds formant un rseau
Code couleur utilis pour dcider de la pertinence dun cheminCahier des chargesPathfindingPlanificateurEntit rutilisableDmonstrationConclusion
Pathfinding ralis par nos soins : Cration de nos propres nuds
Rajout de poids
Algorithme de recherche : A*Cahier des chargesPathfindingPlanificateurEntit rutilisableDmonstrationConclusion
Choix de lalgorithme :De nombreux algorithmes existent (Dijkstra, Best-First-Search, A*, )
Actuellement, on se sert principalement de A* dans la majorit des jeux vidosCahier des chargesPathfindingPlanificateurEntit rutilisableDmonstrationConclusion
Avantages de A* Garantie dobtenir le chemin le plus court (comme lalgorithme de Dijkstra)Cahier des chargesPathfindingPlanificateurEntit rutilisableDmonstrationConclusion
Avantages de A* Cot diminu laide dune heuristique (comme lalgorithme Best-First-Search)Cahier des chargesPathfindingPlanificateurEntit rutilisableDmonstrationConclusion
Droulement de lalgorithme A*Cahier des chargesPathfindingPlanificateurEntit rutilisableDmonstrationConclusion
Lalgorithme :Sommet source (S)Sommet destination (D)Liste des sommets explorer (E) : sommet source SListe des sommets visits (V) : vide
Tant que (la liste E est non vide) et (D nest pas dans E) FaireRcuprer le sommet X de cot total F minimumAjouter X la liste VAjouter les successeurs de X (non dj visits) la liste E en valuant leur cot total F et en identifiant leur prdcesseur.
Si (un successeur est dj prsent dans E) et (nouveau cot est infrieur lancien) alorsChanger son cot totalChanger son prdcesseurFin SiFin Tant que
Cahier des chargesPathfindingPlanificateurEntit rutilisableDmonstrationConclusion
Quest-ce que la planification ? Planifier = Dcider dun plan
Simulation dun grand nombre de combinaisons dactions possibles
Recherche dans un graphe dtats
Comportement du PNJ : Orient-ButCahier des chargesPathfindingPlanificateurEntit rutilisableDmonstrationConclusion
Quelques exemples : Pathfinder, le robot de la NASA Laroport OHare de Chicago F.E.A.R et NOLF2, dvelopps par MonolithCahier des chargesPathfindingPlanificateurEntit rutilisableDmonstrationConclusion
En bref :Cahier des chargesPathfindingPlanificateurEntit rutilisableDmonstrationConclusion
Quelques concepts :Cahier des chargesPathfindingPlanificateurEntit rutilisableDmonstrationConclusion
tat et environnement :Un PNJ opre avec des senseurs le renseignant sur :
Son tat interne
Ltat de lenvironnement qui est connu partiellement, dynamique et parfois mme hostileCahier des chargesPathfindingPlanificateurEntit rutilisableDmonstrationConclusion
Parcours du graphe dtats : Recherche arrire dans le graphe dtats
Algorithme choisi : A* (o lheuristique correspond au nombre de clauses qui reste satisfaire)Cahier des chargesPathfindingPlanificateurEntit rutilisableDmonstrationConclusion
Avantages :Cahier des chargesPathfindingPlanificateurEntit rutilisableDmonstrationConclusion
Dans notre projet : 6 buts
une dizaine dactions
Nos PNJ ont un comportement relativement satisfaisant : ils se battent les uns contre les autres tout en pensant se soigner, changer darme, Cahier des chargesPathfindingPlanificateurEntit rutilisableDmonstrationConclusion
Dans un projet professionnel :Dans NOLF2 (No One Lives Forever 2), FPS bas sur lespionnage, il y a environ :
une vingtaine de buts
une cinquantaine dactions
Cela suffit pour avoir un comportement raliste.Cahier des chargesPathfindingPlanificateurEntit rutilisableDmonstrationConclusion
Quest-ce que la rutilisabilit ? Entit rutilisable = Entit ventuellement extensible, ventuellement adaptable, pouvant tre rutilise dans diffrents contextes.
Nous avons donc prvu la rutilisabilit du planificateur pour dautres types de jeux (RPG, jeu de course, etc.Cahier des chargesPathfindingPlanificateurEntit rutilisableDmonstrationConclusion
Pourquoi ?Au cours de ce projet, il a t ncessaire de :
Rcrire une partie du code existant ou crer des classes proches de celles existantes (ex : Pathnodes)
Remonter certains lments un plus haut niveauCahier des chargesPathfindingPlanificateurEntit rutilisableDmonstrationConclusion
Comment ? Design Pattern : MdiateurCahier des chargesPathfindingPlanificateurEntit rutilisableDmonstrationConclusion
Dans notre projet :Le planificateur se sert dAction et de Goal qui, dans notre cas, sont respectivement des sous-classes de AIAction et AIGoalCahier des chargesPathfindingPlanificateurEntit rutilisableDmonstrationConclusion
Configuration :Toute la configuration se fait laide dUnrealEd (diteur de map dUnreal Tournament)Cahier des chargesPathfindingPlanificateurEntit rutilisableDmonstrationConclusion
Se mettre couvert :Cahier des chargesPathfindingPlanificateurEntit rutilisableDmonstrationConclusion
Obtenir une meilleure arme et se soigner :Cahier des chargesPathfindingPlanificateurEntit rutilisableDmonstrationConclusion
Pathfinding :Cahier des chargesPathfindingPlanificateurEntit rutilisableDmonstrationConclusion
Cahier des chargesPathfindingPlanificateurEntit rutilisableDmonstrationConclusion Problmes rencontrs : Limit du fait de prendre un moteur de jeu existant
Manque de source sur lIA dans Unreal malgr une importante communaut
Cahier des chargesPathfindingPlanificateurEntit rutilisableDmonstrationConclusion Apports : Travail en groupe sur un projet important
Dcouverte et apprentissage de lUnrealScript
Matrise dalgorithmes propres lIA (A*)
tude dun planificateur
Cahier des chargesPathfindingPlanificateurEntit rutilisableDmonstrationConclusion Perspectives : Intelligence collective
Apprentissage
Implmentation de plus dAction et But pour augmenter le ralisme
*************************************