Skip to topic | Skip to bottom
Home
Minfo03
Minfo03.BL1Rapportr1.34 - 10 Jun 2004 - 15:08 - BarelliNicolastopic end

Start of topic | Skip to actions

Outil de simulation de comportements réactifs

Encadreur:

  • Michel buffa

Auteurs :


Plan


Préface

Préface

Ce rapport a été rédigé à la demande de notre encadrant, MichelBuffa, de manière collaborative directement avec l'outil TWiki. Si vous êtes en train de lire une version papier, il s'agit ni plus ni moins que de la version imprimée du document électronique, ce qui peut expliquer la mise en page relativement simple. La version électronique contient de nombreux liens permettant de télécharger et d'exécuter les programmes de démonstration illustrant les propos tenus.


Introduction

Introduction

Le but de ce TER consiste à étudier les algorithmes modélisant le comportement des personnages dans les jeux vidéos de type "stratégie temps réel", dont Warcraft, Age of Empire, etc... sont des exemples.


logo.gif war3.gif

Tous ces jeux mettent en oeuvre de nombreux personnages, des armées, etc... qui agissent le plus souvent par elles-mêmes, de manière autonome. Le joueur se contente de donner des ordres à un personnage ou à un groupe de personnages : va dans telle direction, attaque les soldats adverses, va chercher de la nourriture, etc... En fonction de la classe des personnages, des comportements différents sont disponibles : un paysan ne peut pas se battre, et un soldat ne peut pas aller ramasser le blé pour fabriquer de la farine par exemple.

Néanmoins, nous le verrons, certains comportements sont communs pour tous les personnages : éviter les obstacles en se déplaçant, atteindre un but, aller dans une direction donnée, etc... On distingue par ailleurs plusieurs types de comportements : comportements individuels (éviter les obstacles) ou comportements de groupe (avancez en formation, en respectant une distance entre les personnages, suivre un leader, etc...).

Chaque personnage possède plusieurs comportements qui peuvent être activés de manière simultanée (atteint tel but en évitant les obstacles et en attaquant les ennemis éventuels qui entrent dans ton champs de vision...). En fonction des événements, des coportements peuvent changer, se désactiver ou d'autres peuvent se mettre en route (quand un personnage est mal en point, il cesse d'attaquer et de se battre, et un comportement de fuite ou un comportement de recherche de médicaments peut être activé).

Nous avons commencé par définir avec notre encadreur un ensemble de comportements à étudier, certains étant de grands classiques comme l'évitements d'obstacles ou la recherche d'un plus court chemin à l'aide du célèbre algorithme A*, puis nous avons implémenté un simulateur relativement simple permettant de tester et de règler les paramètres de chaque comportement que nous avons développé. Nous avons opté pour une architecture à base de plugins, aussi bien pour la définition des classes de personnages que pour les comportements eux-mêmes. En parallèle nous avons également développé un prototype de jeu vidéo permettant de mélanger plusieurs personnages de de classes différentes, en leur assignant plusieurs comportements. L'interface utilisateur permet, tout comme dans les "vrais" jeux vidéo, d'interagir avec les personnages, en modifiant leurs comportements en cours de simulation. Ce logiciel permet également de charger et sauvegarder des scénarios.

Dans une première partie, nous détaillerons les algorithmes que nous avons implémentés, puis nous expliquerons l'architecture logicielle du petit simulateur que nous avons développé afin de débugger et règler les paramètres de chaque comportement.

Dans une seconde partie, nous présentons le jeu, "l'arène" que nous avons développé, des scénarios exemples illustrant bien le travail réalisé.

Dans une troisième partie nous ferons le bilan de ce projet : adéquation au cahier des charges, problèmes rencontrés, etc...

Dans une quatrième partie nous effectuerons un travail de synthèse sur le projet réalisé.

Enfin dans la conclusion, nous présentons ce que ce projet nous a apporté, d'un point de vue personnel, en reliant cette expérience aux divers enseignements reçus.

Des annexes sont également disponibles, avec la description des outils et librairies utilisés, les références webographiques et bibliographiques, etc...


Cahier des charges synthétique

Première partie, présentation des algorithmes de comportements


Choix des algorithmes, motivation

Choix des algorithmes, motivation

Le comportement des unités se fait en fonction, de leur environnement (obstacles, d'autres unités , etc …) et de leurs caractéristiques (force rapidité, faim etc …). Leur comportement détermine la façon dont elles vont évoluer, la direction qu’elles vont prendre, ainsi que les actions qu’elles vont effectuer.
Pour gérer cela, il existe de nombreux algorithmes basés sur des principes bien différents.
Les travaux de Craig Renolds en sont un très bon exemple. Il propose sur son site des articles ainsi que des exemples sous forme d'applets qui illustrent son travail. Nous nous sommes d'ailleurs inspirés de certaines idées de comportements. Cependant nous n'avons pas jugé judicieux de reprendre son travail, car les comportements développés par Craig W. Reynolds sont difficilement combinables. Nous avons préféré utiliser la théorie des courbes qui consiste à choisir la meilleure direction possible en fonction de son indice de qualité.
Pour notre application nous avions besoin d’un système nous permettant à la fois de combiner les différents comportements mais aussi de les rendre indépendants les uns des autres. Et cela avec une grande rapidité lors des calculs. C'est pour cela que nous avons opté pour cette solution qui est plus adaptée à nos besoins que les travaux de Craig W. Reynolds.


Principe fondamental

Principe fondamental

Modélisation des personnages et de la carte du monde

Les personnages

Chaque personnage a une position (x, y) dans un repère à deux dimentions , un vecteur vitesse qui donne la direction ainsi que la vitesse avec laquelle il se déplace. Ensuite les individus ont des caractéristiques qui permettent une interactivité avec l'utilisateur du logiciel et une réactivité par rapport au monde dans lequel ils évoluent.

  • Des points de vie
  • Un âge
  • Des points de force
  • Des points de résistance
  • Une Vitesse maximale
  • Une capacité de freinage
  • Une capacité d'accélération

Il est important de souligner que chaque comportement étend les caractéristiques des individus. Par exemple le comportement attaquer apporte une caractérisque peur au combat, ivre apporte la caractéristique taux d'alcoolémie ...

Le monde

L'univers dans lequel évoluent les individus, est délimité par une largeur et par une hauteur, au delà desquels les personnages ne peuvent pas aller. Les éléments interactifs du décor (obstacles et personnages) sont stoqués dans une liste objets Graphiques. Les personnages sont aussi référencés dans une seconde liste qui stocke uniquement les individus objets Réactifs. Enfin certains éléments de décor de second plan comme les cadavres et traces de pieds se trouvent dans une troisième et dernière liste.

Théorie des Courbes

Sachant qu'un personnage peut aller dans plusieurs directions, nous allons donner une estimation de la meilleure trajectoire, en fonction du comportement. Par exemple, pour un comportement imaginaire intitulé "va tout droit", il est clair que c'est la direction en face du personnage qui va obtenir la meilleure estimation, les directions consistant à se diriger vers la droite et vers la gaichge ayant les estimations les plus basses. Les direction entre "tout droit" et extrême gauche auront une estimation allant du maximum au minimum, plus elles s'éloignent de la direction "en face".

Les algorithmes utilisant ces estimations utilisent donc des focntions d'évaluation dont les résultats sont compris entre 0 et 1, cette dernière valeur étant la valeur maximale pour une direction donnée. Si on dessine un graphe possèdant en abscisse les numéros des différentes directions (0 étant la direction vers la gauche, 5 tout droit et 10 le plus à droite par exemple, si on dispose de 10 directions possibles), et en ordonnée les estimations des diverses trajectoires par la fonction d'évaluation on obtient une courbe.

Pour pouvoir se déplacer dans un environement parsemé d'obstacles, il faut pouvoir choisir la bonne direction à un moment donné. Les courbes permettent donc de choisir la direction la plus appropriée ; nous allons maintenant entrer dans les détails.

Prenons qulques exemples :

Tout d’abord il est courant d'utiliser une grille qui représente le champs de vision de l’entité. Rares sont les comportements qui ne tiennent pas compte de ce paramètre (on ne peut éviter un obstacle que si on l'a vu par exemple).

logo.gif

Tous les objets présents dans cette grille seront donc vus par l'entité. Pour savoir si l'objet est présent dans cette grille on doit effectuer un changement de repère. Pour cela nous avons besoin de trois choses : la position de l'entité (l'origine du repère local), la position de l'objet dont on désire la position dans le repère local, et l'angle O par rapport à l'origine du repère globale.


logo.gif

Une fois la position de l'objet dans le repère local, il suffit de déterminer quelle case de la grille il occupe.
A chaque case de la grille on associe un tableau de direction T[LARGEURGRILLE] (c'est ce que l'on appelle la courbe). L'élément T[i] de ce tableau de direction donne une variable de qualité pour la direction i. Par exemple un comportement d'évitement va attribuer (via la fonction d'évaluation) de mauvais points lorsqu'un obstacle se trouve dans la direction i, au contraire un comportement de type attaquer ou manger va attribuer une bonne note de qualité (une bonne évaluation) lorsqu'une proie ou un ennemi se trouve dans le champs de vision.

Pour obtenir la courbe finale, il suffit de fusionner chaque courbe donnée pour les objets présents dans la grille. Pour fusionner il suffit de prendre le T[i] minimum.


Exemple :
Nous sommes dans une grille 5 x 4, un objet ce trouve en case 11 et un en 15.

logo.gif

T11 donne la courbe de direction [ 2 4 7 11 16 ]
T15 donne la courbe de direction [ 16 11 7 4 2 ]
La fusion donne la courbe de direction [2 4 7 4 2]

logo.gif
Enfin pour choisir la meilleure direction on prend le meilleur indice de qualité du tableau. Dans cet exemple nous allons donc passer au milieu, là où il n'y a pas d'obstacles.

Combinaisons de comportements

L'idée pour pouvoir combiner plusieurs comportements c'est que chaque comportement fournisse une courbe en fonction de ce qu'il y a dans le champ de vision de l'entité (comme au dessus). Pour combiner les courbes de différents comportements, on fera une moyenne sur les i éléments des courbes (chaque comportement ayant un poids ce qui influera sur la direction finale choisie).Sous l'exemple ci-aprés un personnage combine deux comportements : il évite l'obstacle et il se dirige vers la nourriture.

Il est à noté que certains comportements ne sont pas combinables, par exemple attaquer et fuir. Pour résoudre ce problème nous avons donc affecté un type à chacun de nos comportements sous la forme d'un entier. Si deux comportements on le même type il ne pevent être aplliqués en même temps.


logo.gif


Algorithmes "locaux"

Algorithmes "locaux"

Dans cette classe d'algorithmes nous trouvons les algorithmes basés sur le champs de vision des personnages. Par exemple, pour éviter des obstacles, on ne tiendra compte que de ceux qui sont devant le personnage.

Evitement d'obstacle

Un individu possédant le comportement éviter obstacles, va modifier sa vitesse et sa direction en fonction des objets qu'il y a dans son champs de vision.
Elaboration de formules pour le calcul de changement de vitesse nécessaire lorsque l'on se rapproche trop d'un obstacle.
Le changement de vitesse consiste tout simplement à réduire ou augmenter la vitesse de l’unité en question. Cela est nécessaire lorsque l’on se rapproche d’un obstacle et que la vitesse ,trop grande, va nous empêcher de prendre correctement le virage.
On pourrait très bien se dire que freiner n’est pas nécessaire, qu’il suffit de tourner plus brutalement mais l’on s’aperçoit rapidement qu’il existe de nombreuses situations ou réduire la vitesse est indispensable : par exemple lorsque l’unité est entourée d’obstacles elle doit alors s’arrêter (vitesse nulle). Tout d’abord, il faut définir à quel moment il faut freiner :

QandFreiner.JPG

On doit freiner lorsqu’un obstacle se trouve sur notre chemin, donc lorsque le vecteur indiquant la direction de l’unité « traverse » l’obstacle. Les calculs se font dans le repère local de l’unité : On freine si (obstacle.x - obstacle.rayon) <= unité.rayon), ce qui équivaut à une collision sur l’axe des abscisses (collision si on garde la même direction).

Ensuite, on doit déterminer comment freiner : On peut freiner par « pas », c’est à dire réduire la vitesse du même coefficient de freinage à chaque mouvement ou bien recalculer la nouvelle vitesse en fonction de la distance qui sépare l’unité de l’obstacle. C’est la seconde méthode que j’ai choisi car elle s’adapte à toutes les situations et permet d’adapter la vitesse en un seul mouvement. La vitesse de l’unité est bornée par 0 (arrêt) et vitesse_max (vitesse maximale possible de l’unité). Pour cela j’ai donc établi une formule (visualisable sur le graphique) qui est : Nouvelle_vitesse = (distance – vitesse) * vitesse_max / (distance_max – vitesse) Cette formule nous retourne 0 si la distance est inferieure ou egale à vitesse (le pas au prochain mouvement) et vitesse_max lorsque la distance est supérieure ou égale a distance_max (c’est a dire si il n’y a pas d’objet en vu). Lorsque la distance est entre ces deux valeurs, la vitesse est d’autant plus proche de vitesse_max que la distance est proche de distance_max et d’autant plus proche de 0 que la distance est proche de vitesse.

QandFreiner.JPG

Se nourrir

Lorsqu'un individu a faim, il doit chercher des objets comestibles afin d'assurer sa survie. Au moment où un objet comestible rentre dans le champ de vision de l'individu et que ce dernier a besoin de manger, il prend en chasse sa proie et essaye de la rattraper pour la manger. Dans le cas ou l'individu a suffisament de réserve de nourriture il continue son chemin en évitant la proie.

Fuir

Un individu ne peut fuir que si il voit un danger dans son champs de vision. Dans ce cas le comportement fuir est prioritaire par rapport à tous les autres comportements et la bête prend la fuite.

Attaquer

Pour la gestion du comportement d'attaque nous avons utilisé la même méthode que pour le comportement se nourrir. A la seule différence que nous ne gérons plus la faim ici, mais la peur. Si un individu a peur il refusera le combat et évitera le danger.

Suivre un ami

Le principe est que chaque individu regarde autour de lui et s'il voit un autre individu de la même race que lui, il ne forme pas une boucle avec lui ; il le suit jusqu'à ce qu'il le perde (obstacle,objet plus dans le champ de vision) dans ce cas il arrête de le suivre. L'algorithme calcule la position du leader éventuel dans son repère local pour déterminer la direction, ensuite si la distance entre eux est valide et que le leader ne forme pas boucle avec lui ,il prend la direction calculée auparavant.


Algorithmes "globaux"

Algorithmes "globaux"

Dans cette classe on retrouve les algorithmes ayant accès à des données ne se trouvant pas forcément dans le champs de vision. Par exemple, l'algorithme de navigation ("va au village qui se trouve à l'autre bout de la carte"), va calculer le plus court chemin pour se rendre à un endroit donné, en tenant compte de tous les obstacles fixes de la carte (arbres, murs, routes, etc...). Il s'agit en général d'algorithmes demandant un temps de calcul beaucoup plus important que les algorithmes "locaux". Ces derniers seront utilisés en complément pour éviter les obstacles (mobiles et fixes) au fur et à mesure que le personnage progresse, car un obstacle mouvant peut par exemple détourner le personnage du chemin préclaculé par l'algorithme de navigation globale.

Algorithme de calcul du plus court chemin A*

Le problème consiste ici à trouver le plus court chemin pour mener une unité de sa position actuelle à un point précis de l’arène, ,celui-ci n’étant évidement pas dans le champs de vison de l’unité, tout en évitant les obstacles. Ce problème est aussi appelé « path-finding ». Une première solution consisterait à tracer une ligne droite entre le point de départ et le point d’arrivée et de demander à l’unité de suivre cette ligne. Si elle rencontre un obstacle, elle décide alors de le contourner par la gauche (ou la droite) puis cherche par la suite à rejoindre la ligne optimale. Cela marche très bien si tous les obstacles sont convexes, en revanche, s’ils sont concaves, l’unité risque d’être bloquée et surtout de prendre un chemin complètement délirant. Mais cette solution est inopérante pour un path-finding efficace.

Il existe d’autre solutions permettant de trouver un chemin " correct ", mais le plus performant est l'algorithme A* aussi appelé A-star. Voici son fonctionnement : la zone de recherche : Pour effectuer sa recherche, l’algorithme travaille sur un quadrillage se superposant à l’arène. Il va donc se servir de « cases », dont le centre de chacune représente un point de passage (checkpoint) pour l’unité.

quadrillage.JPG

Considérons que quelqu'un veut aller d'un point A à un point B. Considérons également qu'un mur est situé entre ces deux points. Cette situation est illustrée par l'image ci-contre, où le point A (départ) est affiché en vert, le point B (arrivée) est en rouge, et où les cases en bleu représentent le mur.

astar1.gif

Le fait que la zone de recherche est divisée en cases simplifie la zone de recherche. Cette méthode particulière réduit notre zone de recherche à un simple tableau à deux dimensions. Chaque élément du tableau représente une case de notre grille, et son statut est notifié comme étant "traversable" ou "non traversable". Le chemin va être la succession de cases à parcourir pour passer de la case A à la case B. Une fois le chemin trouvé, notre unité va passer du centre d'une case au centre de la prochaine case, jusqu'à ce qu'il atteigne sa cible Ces points au centre de chaque case sont appelés "nœuds" (nodes).

Commencer la recherche

Une fois la zone de recherche simplifiée à un nombre de nœuds facilement gérable, comme nous l'avons fait avec la grille ci-dessus, la prochaine étape consiste à effectuer la recherche pour trouver le chemin le plus court. En path-finding A*, on commence cette recherche par le point A, puis en vérifiant les cases adjacentes, et en général en cherchant encore à l'extérieur jusqu'à ce que la cible soit trouvée Nous commençons notre recherche de la manière suivante :
Commençons au point de départ et ajoutons le a une "liste ouverte" (open list) de cases à étudier. La liste ouverte est une sorte de "shopping list". Pour l'instant, nous n'avons qu'un seul point à l'intérieur (le point A). En fait, c'est une liste de points que nous devrons vérifier. Regardez maintenant toutes les cases atteignables (ou "traversables") adjacentes au point de départ, en ignorant toute case qu'on ne peut pas traverser. Ajoutez les à la liste ouverte également. Pour chacune de ces cases, enregistrez la case A comme étant son "parent". Cette notion de "parent" est très importante ensuite pour pouvoir retracer le chemin. Supprimez maintenant le point A de la "liste ouverte", et ajoutez le à une "liste fermée" (closed list), qui va contenir les points que nous n'aurons plus besoin de vérifier. Toutes les cases adjacentes sont maintenant dans la "liste ouverte" de case à vérifier. Chacune d'elle possède une "pointeur" vers son parent, qui n'est autre que la case de départ. Ensuite, choisissons une case de la "liste ouverte", et répétons plus ou moins le raisonnement précédent. Mais quelle case choisir ? Celle avec le coût F le plus bas. Coût d'un chemin. La clé servant à déterminer quelle case utiliser parmi celles contenues dans la "liste ouverte" est l'équation suivante :
F = G + H

avec

G est le coût de mouvement pour aller de la case A à une case donnée sur la grille, en suivant le chemin généré jusqu'ici.

H est le coût de mouvement pour aller d'une case donnée sur la grille jusqu'au point de destination, le point B (coût estimé par ligne droite).

Le chemin est généré récursivement en parcourant notre "liste ouverte" et en y choisissant le case ayant le coût F le plus faible.

Comme décris précédemment, G est le coût de mouvement du point de départ jusqu'à la case donnée en parcourant le chemin généré jusque là.

Dans cet exemple, nous allons assigner un coût de 10 pour chaque déplacement horizontal ou vertical, et un coût de 14 pour un mouvement en diagonale. Nous utiliserons 10 et 14 pour des raisons évidentes de simplification. Le rapport est à peu prés correct. Etant donné que nous calculons le coût G le long d'un chemin donné, le moyen de trouver ce coût est de prendre le coût G de son parent, et de lui ajouter 10 ou 14 selon qu'il soit situé en diagonale ou pas par rapport à son parent. Le coût H peut être estimé d'un grand nombre de façons. Ici nous prendrons le nombre de cases séparant horizontalement la case traitée de la case d’arrivée ajouté au nombre de cases les séparant verticalement, le tout multiplié par 10 . Le coût F est calculé en ajoutant G et H. Vous pouvez constater le résultat sur le schéma ci-contre. Les coûts F, G et H sont notés dans chaque case. Comme indiqué, F est situé en haut à gauche, G en bas à gauche et H en bas à droite.

astar3.gif

Dans la case qui contient les lettres, nous avons G=10. C'est parce qu'elle est située à une case du point de départ, dans une direction horizontale. Les cases en dessous et au dessus de la case de départ, ainsi que celle située à sa gauche ont toutes le même coût de 10. Les cases en diagonales ont un coût de 14. la case située juste à droite du départ a un coût H de 30. La case située juste en dessous a un coût H de 40. Le coût F de chaque case est calculé par une simple addition de G et H. Pour continuer la recherche, nous choisissons tout simplement la case ayant le coût F le plus faible parmi les case de la "liste ouverte". Puis, avec cette case nous faisons le processus suivant : Nous la supprimons de la "liste ouverte" et la rajoutons à la "liste fermée" Nous vérifions toutes ses cases adjacentes, en ignorant celles qui font partie de la "list fermée", ainsi que celle qu'on ne peut pas traverser, que nous ajoutons à la "liste ouverte" si elles n'y sont pas déjà. Assignez la case en cours comme étant le "parent" des cases nouvellement ajoutées. Si une des cases adjacentes est déjà dans la "liste ouverte", vérifiez si le chemin pour y arriver n'est pas meilleur. En d'autres termes, vérifiez si le coût G de cette case est inférieure si nous utilisons la case en cours pour y parvenir. Si ce n'est pas le cas, ne changez rien. D'un autre côté, si le coût G du nouveau chemin est inférieur, faites que la case en cours soit le nouveau parent de cette case adjacente (dans le schéma précédent, changez la direction du pointeur pour pointer vers la case en cours). Pour finir, re-calculez les coût F et G de cette case. Puis on refait ce travail avec la prochaine case au coût le plus faible.

Maintenant, comment déterminer le chemin lui-même ? Tout simplement en partant de la case d'arrivée, et en remontant le chemin en sens inverse d'une case à sa case parent, en suivant les flèches. Cela va vous ramener à votre chemin de départ, et voila votre chemin ! Se déplacer du point A ou point B consiste maintenant à vous déplacer du centre d'une case au centre de la prochaine case de votre chemin, jusqu'à ce que vous atteignez votre destination.

astar6.gif

Voici récapitulé l’algorithme A* :
  • Ajouter le point de départ à la "liste ouverte"
  • Répéter les instructions suivantes :
    • Cherche la case ayant le coût F le plus faible dans la "liste ouverte".
    • Elle devient la case en cours.
    • Passer la case en cours de la "liste ouverte" à la "liste fermée.
    • Pour les 8 case adjacentes à la case en cours :
    • Si on ne peut pas la traverser, on l'ignore.
    • Si elle n'est pas dans la "liste ouverte", on l'y ajoute. La case en cours devient le parent de cette case. On calcule les coûts F, G et H de cette case.
    • Si elle est déjà dans la "liste ouverte", on teste si le chemin passant par la case en cours est meilleur en comparant les coûts G. Un coût G inférieur signifie un meilleur chemin. Si c'est le cas, on change le parent de la case pour devenir la case en cours, en on recalcule les coûts F et G. Si vous conservez une "liste ouverte" triée par coût F, la liste doit être retirée à ce moment là.
    • On s'arrête quand la case de destination est ajoutée à la "liste ouverte" ou si on ne trouve pas la case de destination et la "liste ouverte" est vide.
  • Enregistrez le chemin. En partant de la case de destination, remontez d'un case à son parent jusqu'à atteindre la case de départ. Vous avez votre chemin .

Suivre des points de passages (way-points)


Les way-points (ou check-points) sont des points de passage par lesquels une unité est obligée de passer pour suivre un chemin prédéfini.
Ce système va est à la base de plusieurs comportements, tels que « cible », « sentinelle », ou plus simple encore « suivre une chemin ».
Voici une explication simple pour ce dernier :
Le comportement possède une liste de points, positions jouant le rôle de way-points, ainsi que la position de l’unité concernée.
Pour chaque nouveau déplacement de l’unité il calcule les distances entre l’unité et les différents points de passages, et désigne le plus proche comme actif.
L’unité se déplace alors dans la direction du way-point actif, puis une fois franchi passe au suivant et ainsi de suite jusqu’au dernier.


Algorithmes "basique"

Algorithmes "basique"

Les comportements utilisant des Algorithmes "basiques" sont des comportements simples qui n'utilisent pas le champs de vision. Ils sont indépendant du monde extèrieur qui entoure les personnages.

Feignant

Un individu qui possède le comportement feignant se déplace en effectuant des pauses. Pour simuler ce comportement on utilise un temps de pause.


Ivre

Un individu oscille de droite à gauche en fonction de son taux d'alcolémie. Plus l'individu sera ivre et plus l'angle d'oscillation va être important. Le comportement Ivre a un poids trés faible, de façon à ce qu'un personnage puisse tout de même éviter des obstacles, fuir quand il y a un danger ou attaquer.


Tenir position

Le comportement tenir position est vraiment trivial, une bête se contente de rester sur place sans bouger. Cependant elle a la possibilité de fuir si un danger survient.


Deuxième partie

Deuxième partie : implémentation des algorithmes et test dans un simulateur


Architecture logicielle à base de plugins

Architecture logicielle à base de plugins

Il a été très vite décidé de gèrer les personnages et les comportements sous forme de plugins. Nous avons opté pour ce choix pour plusieurs raisons:

  • Une plus grande souplesse de l'application
  • Un développement séparé des différents plugins
  • Nous possédions déja les connaissances nécessaires, car nous avions étudié en cours le développement par plugins et aussi appliqué dans un mini projet
  • C'est l'occasion de faire un "vrai" gros projet mettant en oeuvre cette architecture, incontournable aujourd'hui dans les gros logiciels (photoshop, etc...)
  • Cette technologie permet une mise à jour à chaud aprés un rajout ou une suppression d'un plugin


Présentation des interfaces pour les personnages, éléments de décor et les comportments

Présentation des interfaces pour les personnages, éléments de décor et les comportments

Pour développer un nouveau personnage il suffit d'étendre la classe Individu, d'implémenter l'interface mangeable si l'objet peut-être mangé.

Simulateur.jpg

Pour développer un nouvel objet il suffit d'étendre la classe Element Decor

Simulateur.jpg

Pour développer un nouveau comportement il suffit d'étendre la classe Comportement

Simulateur.jpg


Le Simulateur

Le Simulateur

L'outil de simulation a été implémenté afin de pouvoir paramétrer au mieux les comportements et les paramètres de bases. On peut y visualiser certaines options pour le débuguage (grille, meilleure direction, ... )
Nous avons la possibilité de rajouter des individus et de leurs appliquer des comportements. Nous pouvons également ajouter différents objets.

Simulateur.jpg

Voici les différents paramètres que l'on peut configurer:

  • Taille x taille en largeur des cases utilisées par l'algorithme astar
  • Taille y taille en largeur des cases utilisées par l'algorithme astar
  • le nombre de case en hauteur de la grille du champ de vision
  • le nombre de case en largeur de la grille du champ de vision
  • le coefficiant de direction ( plus il est élevé moins l'individu tourne bien )
  • le coefficiant de déplacement ( plus il est élevé moins l'individu vas vite )
  • le champs de vision en X
  • le champs de vision en Y
  • la capacité d'un individu à freiner
  • la capacité d'un individu à accélérer

Sliders.jpg


Troisième partie

Troisième partie Développement d'une arène mettant en oeuvre plusieurs personnages avec plusieurs comportements


Description

Description

L'arène constitue le logiciel de démonstration de notre TER. Il permet le chargement de scénarios développés dans l'éditeur de niveaux afin de visulaliser des situations illustrant les comportements développés. Par ailleurs l'utilisateur a la possibilité de sauvegarder des applications en cours. D'autre part l'arène répond au principal besoin du cahier des charges c'est-à-dire pouvoir modifier en temps réel les caratéristiques des individus et des comportements. Lors de la simulation il est possible à l'utilisateur de visualiser les différents attributs des personnages ainsi que la courbe de direction donnée par la combinaison des comportements. Enfin il est aussi possible de rajouter des éléments de décor et de nouveaux individus.

La simulation permet, par le biais de certains comportements de faire apparaitre différentes interactions entre personnages comme les phases de combats, la recherche d'une proie ...

L'arène constitue une sorte de simulation de vie, les personnages peuvent perdre la vie de façon trés différentes ( mort au combat, mort due a un age trop avancé et mort due a une carence en nouriture.

logo.gif


Listing des fonctionalités

Listing des fonctionalités

Liste non exaustive des fonctionalités de l'arène

  • Sélection d'un personnage
  • Modification des comportements par type de personnages
  • Ajout d'objets ou de personnages
  • Visualisation et modifications d'attributs de comportements
  • Visualisation et modifications d'attributs de personnages
  • Rechargement des plugins
  • Chargement et sauvegarde d'une simulation
  • Aide en ligne

Pour plus d'informations sur l'utilsation des diverses fonctions consulter le Guide d'utilisation.


Quatrième partie

Quatrième partie : Synthèse du projet


Planning initiale du cahier des charges

Planning initial du cahier des charges

Initialement nous avions prévu de développer notre application en trois phases distinctes:

  • Une première phase d'une semaine d'élaboration générale, durant laquelle nous devions réfléchir sur la structure logicielle à mettre oeuvre, les problèmes d'extensibilité liés à celle-ci. Quatres étudiants devaient effectuer cette tâche.
  • Une seconde phase d'une semaine où deux étudiants bâtiraient l'ossature du projet et les deux autres devaient concevoir une boîte à outils pour débuguer les futurs plugins.
  • Enfin durant les trois dernières semaines, les quatre étudiants devaient développer des comportements
L’implémentation de l’interface graphique devait se faire en parallèle pendant les deux dernières phases, celle-ci nécessitant une idée précise de l’implémentation de l’ossature générale.

Récapitulatif des tâches:

  • Ossature globale : 2 étudiants
  • Définition en détail de toute l’architecture du projet : 4 étudiants
  • Animateur de l’application : 2 étudiants
  • Plugins (comportements, bêtes) : 4 étudiants
  • Boîte à outils : 1 étudiant
  • Editeur de niveaux : 2 étudiants
  • Interface graphique : 2 étudiants


Planning initiale du cahier des charges

Planning effectif et découpage en tâches

Durant la première phase après 3 jours de réflexion sur la structure, du 10 au 12 mai, nous nous sommes rendu compte que deux choix se présentaient à nous :

  • Faire une structure entièrement extensible par plug-in, mais à laquelle on ne pourrait rajouter que des plug-in « simples » n’apportant pas de nouvelles interactions (plug-in action) entre les différents éléments de l’arêne.
  • Faire une structure entièrement extensible par plug-in sauf au niveau des interactions (plug-in action) entre les différents éléments de l’arène. Celle-ci étant codées en brute dans le corps du programme, permettant ainsi de les rendre plus complexes.
Mais pourquoi une action sous forme de plug-in ne pourrait-elle pas être complexe comme l’est une action fixée dans le code ?
Tout simplement car le code gérant les plug-in est « général ». Il crée une instance du plug-in sans rien connaître de ce dernier. Les caractéristiques spécifiques au plug-in en question ne peuvent donc pas être utilisées par le « code de base » puisqu’au moment de la création du code qui les gères, elles n’éxistaient pas.
Un exemple : considérons une application de base constituée d’une arène, d’un type de personnage paysan », d’un type d’objet « foin », et d’un comportement « transporter ». Ces trois derniers étant des plug-in.
Lors de l’exécution le comportement « transporter » donne comme ordre au « paysan » : à chaque fois que tu trouves un objet « transportable » alors prends-le.
Ici le « foin » a été défini comme étant de type « transportable » , tout va donc se passer comme prévu.
Maintenant, nous désirons pouvoir mettre le feu au « foin ». Pour cela nous allons étendre cette application de base par un plug-in comportement « pyromane » qui donnera comme ordre au paysan : à chaque fois que tu trouves un objet « inflammable » alors brûles-le.
Mais ce comportement utilise une caractéristique, liée aux objets, « inflammable » qui n’est pas connue de l’application de base. En effet aucun objet n’as été défini comme objet « inflammable ». Si l’on veut pouvoir mettre le feu au foin, il va falloir modifier le plug-in objet « foin » pour lui donner cette caractéristique. On perd donc l’extensibilité apportée par les plug-in.
Il est évidemment possible de parer à ce problème de plusieurs façons mais toutes se font en dépit des performances.
Comme nous voulions une application se rapprochant d’un jeu de stratégie temps réel (et donc assez fournie en différents types d’objets, personnages etc…) et que seul le second choix de structure nous le permettait vraiment, c’est celui-ci que nous avons choisi.

Une fois ce choix fait, et ayant établi sur papier la base de notre architecture, nous avions tous les éléments nécessaires pour commencer l’implémentation de l’ossature. De ce fait, le jeudi 13 mai, les deux étudiants affectés à l’ossature globale ont commencé cette tâche.
Pendant ce temps, un étudiant était chargé d’étudier en détail le fonctionnement des comportements et ainsi rendre moins difficile leur implémentation. Il s’est avéré que ce fut un choix judicieux. Le dernier étudiant fût tout de suite affecté à l’interface graphique. En effet nous nous sommes dit que nous allions avoir rapidement besoin d’un début d’élément graphique pour tester les différents composants que nous allions concevoir.
L’implémentation de l’ossature a été plus rapide que prévue. Les deux étudiants qui y travaillaient se sont donc mis sur la conception de la boîte à outils. En fait, pour pouvoir les tester, nous avons incorporé chaque nouveau composant réalisé, de cette boîte à outils, à notre ossature, elle même servie par une interface graphique. Le tout s’est donc transformé, dès le 18 mai, en un simulateur permettant d’effectuer les tests nécessaires à la bonne évolution de notre application.
Durant cette semaine là (semaine 21) et la suivante, nous avions un étudiant qui travaillait à plein temps sur les comportements, un autre toujours à plein temps sur l’interface graphique, pendant que les deux autres « jonglaient » entre les comportements et les autres composants constituant notre simulateur. Ce dernier, à force de s’étoffer de nouvelles fonctionnalités, comportements et composants graphiques, prenait de plus en plus un air de prototype pour notre arène.
C’est pourquoi, à parti du 26 mai, nous avons décidé de séparer ce prototype en deux :
  • un simulateur assez dépouillé en fonctionnalités mais donnant accès à un grand nombre d’outils de test sur tous les paramètres liés aux comportements qu’il nous faudrait calibrer,
  • une arène plus étoffée graphiquement et qui serait plutôt dédiée à la visualisations des effets des comportements sur les différentes unités. Elle permettrait, entre autre, toutes les actions nécessaires telles que ajouter ou supprimer une unité, un comportement, etc …
Cette séparation s’est faite très facilement puisque nous avions conçu une architecture souple et facilement modifiable.
Pendant la quatrième semaine, nous avons donc continué sur le même schéma l’implémentation de notre application avec une certaine liberté au niveau des affectations aux différentes tâches : Même si chacun avait sa directive, il n’était pas rare que celui-ci passe quelques heures à aider celui-là, en apportant un « œil nouveau » , et ainsi débloquer la situation.
La cinquième et dernière semaine aura essentiellement servi à la finalisation du projet et à la rédaction du rapport.

Voici un tableau illustrant les modifications intervenues dans le découpage:

logo.gif

  • Remarque : Pendant toute la période de ce projet nous avons travaillé ensemble dans le même lieu pour pouvoir communiquer le plus rapidement possible et dans les meilleures conditions. A tout moment chacun devait savoir sur quoi travaillaient les autres, où ils en étaient, et après que chaque tâche soit terminée elle était incorporée à l’application et testée. Lorsque nous n’étions pas ensemble nous communiquions grâce à msn messenger ainsi que twiki.


    Planning initiale du cahier des charges

    Description du travail réalisé

    Définition en détail de toute l’architecture du projet

    Phase de réflexion sur les différentes possibilités d’implémentation de l’ossature au niveau des plugins, de la gestion des comportements et des différentes fonctionnalités liées aux comportements. Nous avons passé moins de temps que prévu initialement à cause du problème soulevé au dessus.

  • 4 étudiants du 10 au 12 mai à 100% de leur temps

    Etude de comportements

    Phase préliminaire a l’implémentation, afin de comprendre le fonctionnement et de déterminer la faisabilité de chaque comportement.

    • 3 étudiant du 13 mai au 14 mai Barelli et Maitrehut à 10% de son temps et Ould Sidina à 100%
    • 1 étudiant Ould Sidina du 17 mai au 21 mai à 80% de son temps

    Ossature globale

    Implémentation de différentes classes constituant la base de l’application : chargement de plugins, élaboration de la hiérarchie et interface de plugins permettant gestion des différents éléments utilisable dans l’arène ou dans le simulateur, utilitaires facilitant l’utilisation des courbes.

    • 2 étudiants Barelli et Maitrehut du 13 au 14 mai à 65% de leur temps
    • 1 étudiant Barelli du 17 mai au 21 mai à 30% de son temps

    Simulateur

    Développement d’outil de visualisation et de modification des différents paramètres intervenant sur les comportements. Le simulateur à bien été achevé, seulement il a été réalisé durant toute la période de conception de l’application car il a fallu le faire évoluer pour pouvoir tester certains nouveaux comportements (comme le A*).

    • 2 étudiants Barelli et Maitrehut du 13 au 14 mai à 25% de leur temps
    • 1 étudiant Barelli du 17 mai au 21 mai à 30% de son temps
    • 1 étudiant Barelli du 24 mai au 28 mai à 5% de son temps
    • 1 étudiant Maitrehut du 31 mai au 4 juin à 10% de son temps

    Implémentation des comportements

    Nous avons pris du retard à cause du problème soulevé ci aprés, de ce fait cet évènement nous a empêché d’implémenter les comportements de groupes (avancer en formation …), ce problème est survenu le samedi 22 mais.

    Le problème de combinaison des courbes était dû a une mauvaise attribution des poids des comportements et des mauvaises fonctions de précalcul. De plus certains comportements ne sont pas combinables car de même type. Par exemple une unité ne peut pas à la fois attaquer et fuir. Enfin nous avons eu un problême avec le comportement éviter et les comportement devant faire une action sur un objet graphique. En effet, prenons l'exemple de manger : l'unité se rapproche de plus en plus de la cible dans l'intention de la manger, mais elle ne pourra pas arriver sur la cible et la manger car le comportement éviter avec un poids plus important ne lui le lui permet pas, il fait s'éloigner l'unité de la cible qui est aussi un obstacle (car objet graphique). Dans le cas ou l'on met un poids plus fort au comportement manger, l'unité prendra toujours la direction de la cible à manger et n'évitera plus les obstacles qui se presenteront à elle. Nous avons résolu ce problème en demandant conseil à notre encadrant.

    • 3 étudiants du 17 mai au 21 mai Barelli à 40% de son temps, Maitrehut à 100% et Ould Sidina à 20%
    • 3 étudiants du 24 mai au 28 mai Barelli à 35% de son temps, Maitrehut à 100% et Ould Sidina à 100%
    • 3 étudiants du 31 mai au 4 juin Barelli à 30% de son temps, Maitrehut à 70% et Ould Sidina à 100%
    • 3 étudiants du 7 au 10 juin Barelli à 10% de son temps, Maitrehut à 20% et Ould Sidina à 100%

    Animateur

    L’animateur permet de gérer l’affichage à l’écran de l’ensemble des éléments évoluant dans l’arène, gestion des évènements souris, ajout et suppression des nouveaux objets et personnages.

    Pour permettre l'ajout et la suppression en temps réel d'unités et d'éléments du décord il a fallu rendre synchronized les données qui contiennent les divers éléments graphiques. D'autre part, nous n'avons pas pu résoudre un problème de ralentissement dû à l'utilisation longue du logiciel.

  • 1 étudiant du 24 mai au 28 mai Barelli à 50% de son temps

    Interface graphique

    Création et mise en place de tous les éléments graphiques ( image, bouton ,etc…) constituant le visuel de l’application. Gestion de la séquence d’introduction.

    Pour éviter que les éléments graphiques clignotent en permanence il faut utiliser la technique de double buffering, ce qui est possible en utilsant Java.Swing

    logo.gif

    • 1 étudiant Bernard du 13 au 21 mai à 100% de son temps
    • 1 étudiant Bernard du 24 au 28 mai à 40% de son temps
    • 1 étudiant Bernard du 31 mai au 4 juin à 40% de son temps
    • 2 étudiants du 7 au 10 juin Bernard à 10% de son temps et Maitrehut à 10%

    Arène

    La tâche arène a constitué essentiellement à faire le lien entre l'interface graphique et l'ossature du programme.

    • 2 étudiants du 24 au 28 mai Barelli à 10% de son temps Bernard à 20%
    • 2 étudiant du 31 mai au 4 juin Barelli à 50% de son temps et Bernard à 30%
    • 2 étudiant du 7 au 10 juin Barelli à 20% de son temps et Bernard à 50%

    Editeur de niveau

    Construction d’un petit logiciel permettant la création de scénarios mettant en scène des personnages dotés de comportements différents ainsi que l’environnement dans lequel ils vont évoluer. L'éditeur est plus complet (édition de scénarios ) que ce que nous avions prévu au départ de ce fait il s'est étendu sur une pèriode plus longue

    • 1 étudiant Bernard du 24 au 28 mai à 40% de son temps
    • 1 étudiant Bernard du 31 mai au 4 juin à 30% de son temps
    • 1 étudiant du 7 au 10 juin Bernard à 40% de son temps

    Rapport

    • 2 étudiants du 31 mai au 4 juin Barelli à 10% de son temps et Maitrehut 20%
    • 2 étudiants du 31 mai au 4 juin Barelli et Maitrehut à 70% de son temps

    Accessoires

    Mise en place du système de déploiement, ainsi que du Kit de développement de plugins. Lors de cet phase il était initiallement prévu d'utiliser des benchmark mais lors de la quatrième semaine nous sommes rendu compte que nous n'avions pas le temps nécessaire pour accomplir cette tâche.

  • 1 étudiant Barelli du 31 mai au 4 juin à 10% de son temps


    Récapitulatif

    Récapitulatif

    Travail effectué

    • Comportements individuel
    • Interface graphique
    • Mise en place d'une structure de déveullopement de plugins souple
    • Editeur de niveau
    • Fonctionnalités d’interaction sur les bêtes
    • Fonctionnalités d’édition de l’arène
    • Simulateur
    • Arène

    Travail non fait

    • Gestion de comportements de groupe
    • Utilisation de benchmark

    Pour les points non traité, nous supposons qu'il nous a manqué une bonne semaine afin de traiter ces deux points.


    Synthèse et Conseils

    Synthèse et Conseils

    Nous pensons que nous avons bien fait de mettre un étudiant dés le début pour gérer l'interface graphique. De plus l'architecture par plugins nous a été trés utile pour un développement séparé. Mais rétrospectivement nous pensons que nous aurions dû mieux définir les tâches à réaliser dans le cahier des charges, ce manque cruel de définition nous a fait perdre un temps précieux.

    Les conseils que nous pourrions donnerfo a des étudiants aprés avoir effectué ce travail d'étude sont les suivants:

    • Bien définir le cahier des charges de façon à avoir un planning structuré et une distribution des tâches selon les compétences de chaque membre du groupe
    • Essayer de nommer un "chef de projet" qui fasse respecter le cahier des charges à l'équipe et éventuellement ramène à la raison les plus utopistes
    • Bien réfléchir avant de coder, une phase de design est capitale pour l'aboutissement d'un projet
    • Ne pas hésiter à questionner le client de façon à satisfaire au mieux à ses attentes et également pouvoir définir parfaitement les fonctionalités dont devra disposer l'application finale
    • Essayer de rendre modulaire l'application par le biais de plugins par exemple
    • Etre rigoureux dans la programmation, il faut penser aux personnes qui relisent le code,un minimum de commentaire et de documentation évite de perdre un temps précieux
    • Eviter d'être trop ambitieux
    • Surtout ne rajouter pas des choses inutiles en plein milieu du développement. Même un élément le plus bénin peut engendrer une perte de temps énorme

    Enfin une dernière remarque sur les points que l'on aurait bien aimé traiter:

    • Faire des comportements plus complexes
    • Pouvoir intégrer une interactivité avec les différents bâtiments
    • Que les personnages puissent effectuer plus d'actions
    • Intégrer plus d'unités


    Conclusion

    Conclusion

    Ce que ce projet nous a apporté

    • Tout d’abord, le développement de notre application nous a permis de consolider et d’approfondir notre connaissance du langage Java. En effet nous avons pu aborder de nombreuses notions de Java, certaines déjà étudiées en cours ou en travaux pratiques, d’autres totalement nouvelles pour nous (par exemple le double buffering).
    • De plus, ce projet nous a donné l’occasion d’apercevoir les difficultés qu’il y a à travailler en équipe, même restreinte, et ainsi de mieux comprendre l’importance et la manière dont s’organise un projet. Par exemple, l’importance que peut avoir un chef de projet ou plutôt ,dans notre cas, le membre de l’équipe qui a la vision globale du projet. Nous avons, à plusieurs reprises au début du projet, eu quelque difficulté à raccorder nos différents travaux, élaborés séparément.
    • Ensuite, nous avons pu, grâce à ce projet, constater que la communication est un élément clé dans le bon développement d’une application par une équipe.
    • Enfin, la tâche étant d’une ampleur assez grande, cela nous à permis de nous faire une idée de ce qu’est le travail d’un développeur dans une entreprise, et cela de manière plus précise que celle que nous avions pu avoir jusqu’à maintenant lors de nos mini-projets.

    Ce que nous avons aimé lors de ce projet

    • Nous avons beaucoup apprécié l’outil Twiki. Il s’est révélé être d’une aide précieuse pour la communication entre les différents membres du groupe. De plus, il est très convivial et donne accès à de nombreuses fonctionnalités très pratiques comme la possibilité de voir en détail les modifications effectuées sur une page, de mettre des fichiers à disposition des autres, etc…
    • Nous étions, dès le début, très enthousiastes sur le thème du sujet et nous n’avons pas été déçus ! Travailler à la fois sur de l’intelligence artificielle, sur des outils utilisés actuellement dans le monde du jeu vidéo, et sur un logiciel prenant la forme d’un jeu est vraiment très motivant pour les étudiants que nous sommes.
    • Nous avons trouvé très agréable la liberté que nous a laissé notre encadrant au niveau de la forme de l’application. Cela nous a permis de nous orienter vers un jeu de stratégie temps réel presque complet, ce qui est, pour des étudiants, préférable à un logiciel plus sobre et moins amusant à programmer.
    • La programmation par plug-in a rendu l’implémentation du programme plus simple et moins problématique mors des modifications importantes apportées au projet.

    Ce que nous n’avons pas aimé lors de ce projet

    • La liberté que nous a laissé notre encadrant nous a beaucoup perturbé au début de ce projet. Nous ne savions pas ce qu’il attendait réellement de cette application, ni dans quelle direction nous devions nous orienter. A de nombreuses reprises nous avons du faire des choix peu évidents en étant dans le doute de faire quelque chose qui ne correspondait pas à ce qu’il désirait. Nous avons perdu beaucoup de temps à essayer de définir en détails un sujet plutôt vague, contrairement aux autres groupes qui savaient exactement ce qu’ils avaient à faire.

    Au final ce projet a été une expèrience trés enrichissante pour nous tous, et nous sommes dans l'ensemble nous sommes satisfait du travail réalisé.


    Annexes

    Annexes

    Webographie, bibliographie

    Outils utilisés

    • logo.gif ANT
    • logo.gif Java
    • logo.gif Borland Jbuilder 9
    • twikiRobot88x31.gif

    Cahier des charges

    Guide d'utilisation

    Guide de maintenance

    Guide de dévelopement


    to top

    Copyright © 1999-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
    Ideas, requests, problems regarding WIKIDeptinfo? Send feedback