C++ - Projet jeu de la vie

ven. 02 avril 2010

Ce projet est destiné à vous faire manipuler l'ensemble des concepts objets abordés pendant le cours et les travaux pratiques : création de nouveaux types de données, encapsulation et protection des données, réutilisation de composant par héritage et/ou par composition, classes virtuelles, liaison dynamique et polymorphisme.

Description du sujet

Le but de ce projet est de programmer en C++ une variante du célèbre jeu de la vie de Conway qui simule l'évolution d'une population en suivant des règles de vie et de mort. Dans cette variante, la population est constituée de cellules possédant au minimum les attributs suivants : une couleur (blanc, bleu, noir, rouge ou vert), un niveau d'énergie initial (3 par défaut), un âge maximum (10 par défaut), des coordonnées dans le plan euclidien, la Population à laquelle elle est rattachée, le Substrat dans lequel elle évolue et une Fenetre (graphique) dans laquelle elle sera représentée.

Règle du jeu

La population occupe un tableau de taille n x n (lignes et colonnes indicees de 1 à n). Une case peut contenir deux cellules au maximum. Les règles d'évolution générales sont les suivantes :

  • Survie : toute cellule seule dans une case comportant de la nourriture voit son niveau d'énergie augmenter de 2 et le niveau d'énergie de la case diminué de 1.
  • Affrontement : toute case occupée par deux cellules de couleur différente voit le niveau d'énergie de chaque cellule diminué d'1 point (sauf capacité spéciale propre à chaque couleur de cellule, cf. définition des cellules).
  • Mort : toute cellule dont l'âge atteint son maximum ou dont le niveau d'énergie tombe à 0 meurt et laisse de l'énergie (0, 1 ou 2 points, aléatoirement) sur le lieu de sa mort, énergie qui servira de nourriture à d'autres cellules.
  • Reproduction : l'une des cases inoccupées adjacentes à une case occupée par deux cellules de la même couleur devient occupée par une nouvelle cellule de leur couleur. Si aucune case voisine n'est libre, la reproduction n'a pas lieu (surpopulation).

Les déplacements suivent les règles suivantes : une cellule peut, à chaque tour, se déplacer dans l'une des 8 cases adjacentes à celle qu'elle occupe sous réserve que son niveau d'énergie soit supérieur à 1 (car le déplacement coûte 1 point d'énergie) et que la case ne comporte pas plus d'une cellule, ou bien rester sur place. Le choix du type de déplacement pour une cellule donnée se fera dans l'ordre suivant :

  1. si de la nourriture se trouve sur la case qu'elle occupe, la cellule reste sur place, sinon
  2. si une case adjacente à celle qu'elle occupe comporte de la nourriture, avec une cellule de sa couleur, elle s'y rend, sinon
  3. si une case adjacente à celle qu'elle occupe comporte uniquement de la nourriture, elle s'y rend, sinon
  4. si une case adjacente à celle qu'elle occupe abrite uniquement une cellule de sa couleur, elle s'y rend, sinon
  5. si une case adjacente à celle qu'elle occupe comporte de la nourriture, avec une cellule qui n'est pas de sa couleur et de niveau d'énergie inférieur ou égal, elle s'y rend, sinon
  6. si une case adjacente à celle qu'elle occupe abrite une cellule d'une autre couleur et de niveau d'énergie inférieur à son niveau d'énergie, elle s'y rend, sinon
  7. si une case adjacente à celle qu'elle occupe est libre, elle s'y rend ; s'il existe plusieurs cases libres elle doit choisir celle dans la direction de la nourriture la plus proche, sinon
  8. elle reste sur place

Pour des raisons de simplicité, on considère que les actions ne peuvent être simultanées (par exemple, 3 cellules visant le même emplacement, ...). L'ordre de résolution des actions se fera donc de façon préetabli (par exemple, dans l'ordre des naissances puisque l'on utilisera une liste chaînée pour gérer celles-ci, cf. définition de la classe Population).

Mise en oeuvre

Avertissement : le cahier des charges suivant est volontairement restreint et comporte des imprécisions (symbolisées par trois petits points ;). En effet, la façon dont vous concevrez ce projet aura une importance aussi grande que l'implantation proprement dite ! Cependant, des conseils vous seront donnés pour chaque classe (identifiés par le symbole )

Interface

L'utilisateur fournira au programme la taille n du tableau (pour un substrat constituee de n x n cases), le nombre de cellules initiales dans chaque couleur ainsi qu'un germe pour le générateur de nombres pseudo-aléatoires qu'il faudra utiliser (ce dernier peut-être fourni par la fonction time() par exemple mais vous n'aurez alors aucun contrÎle sur le type de population générée). Une nouvelle génération s'affichera à chaque fois que l'utilisateur appuyera sur une touche dans la fenêtre de visualisation de la population. Pour stopper le programme l'utilisateur appuyera sur la touche q ou Q dans la fenêtre.

Les classes

La classe ``Cellule`` : la classe Cellule est une classe abstraite (i.e comportant une ou plusieurs méthodes virtuelles pures, conséquence : on ne peut créer d'objets de cette classe) regroupant les caractéristiques des cellules (voir ci-dessus), ainsi que leur comportement : se déplacer, manger, mourir, se reproduire, se dessiner, ...Cette classe ne comporte que très peu de méthodes virtuelles, elle regroupe a priori la majorité des attributs et méthodes de ses classes filles. En particulier, les méthodes ayant trait à l'affichage des cellules peuvent prendre place dans cette classe. Pensez immédiatement aux méthodes de consultation et de mise à jour des attributs privés (ou protégés ! ;). N'oubliez pas d'informer qui de droit de l'existence d'une nouvelle cellule (et donc de sa représentation graphique) ainsi que de sa disparition (aussi bien sur le plan "physique" que graphique). Réciproquement, l'unique instance de la classe Substrat doit être consultée pour tout ce qui touche à l'environnement immédiat d'une cellule. Personnellement, j'ai utilisé un code commun qui indique quelle case (1 = NO, 2 = Nord, 3 = NE, ...) est concernée par rapport à la case courante (codée 0).

Les classes dérivées de la classe Cellule : ces classes correspondent à une spécialisation du comportement d'une cellule. C'est en spécialisant le comportement des cellules que l'on établit les règles de vie entre les représentants de ces classes. Vous avez le choix entre deux comportements : ceux qui différencient les cellules au moment de leur affrontement ou ceux qui les différencient au niveau de leurs attributs. Vous pouvez aussi prendre en compte les deux ensembles d'idées, auquel cas il faut cumuler leurs particularités (cf. cellules rouges et vertes).

Différence lors des affrontements :

  • CelluleBlanche : cellule immunisée à l'une des 4 autres couleurs,choisie au hasard pour chaque instance de CelluleBlanche
  • CelluleBleue : celle-ci comporte une autre couleur à sa naissance, qu'elle fournira à une cellule d'une autre couleur que bleue. Si la couleur correspond, elle subit la règle de dommage lors de l'affrontement mais elle peut se reproduire et donner naissance à une cellule bleue
  • CelluleNoire : cellule ayant 25% de chance de réapparaître sur lieu de sa mort avec un niveau d'énergie maximum i.e 3 mais en conservant l'âge qu'elle avait au moment de sa mort
  • CelluleRouge : cellule enlevant 1 point d'énergie supplémentaire à une cellule d'une autre couleur (en plus du point de dommage lors de l'affrontement)
  • CelluleVerte : cellule ayant un niveau d'énergie supplémentaire (3 points de plus que les autres couleurs)

Différence concernant les attributs :

  • CelluleBlanche : son âge maximum est de 20 au lieu de 10
  • CelluleBleue : elle fait deux déplacements (actions) par tour
  • CelluleNoire : elle donne naissance à 2 cellules noires lors de la reproduction si 2 cases adjacentes sont libres
  • CelluleRouge : cellule enlevant 1 point d'énergie supplémentaire à une cellule d'une autre couleur
  • CelluleVerte : cellule ayant un niveau d'énergie supplémentaire (3 points de plus)

Les représentants de ces classes se distinguent surtout par leur représentation graphique ainsi que par leur comportement durant les affrontements et/ou les autres phases de leur courte existence.

La classe ``Population`` : cette classe est une classe superviseur. Elle gére une population d'organismes au moyen d'actions globales (dessiner la population, la faire évoluer, ...) ou locales (rechercher ou supprimer un organisme, en ajouter un nouveau, ...). Attention, afin d'assurer correctement les notions de liaison dynamique et de polymorphisme, cette classe devra donc manipuler des pointeurs sur des organismes, la structure de données servant à mémoriser les organismes étant obligatoirement la liste. Pour cela, vous utiliserez un type "liste template" fourni dans la Standard Template Library (STL), et vous l'instancierez avec un pointeur sur une cellule (ce qui permet de traiter l'ensemble des notions de la POO en C++).En tant que classe superviseur, elle gère les instances placées sous sa responsabilité i.e les cellules.Lors de son initialisation, elle doit donc créer la population initiale. Elle doit ensuite se charger de la mettre à jour à chaque tour. Une fois comprise, la classe polymorphe vous fera gagner beaucoup de temps (tout en étant robuste i.e exempte de bugs). Plus précisément, cette classe doit donc gérer les naissances ainsi que les disparitions (toujours en informant qui de droit) et les demandes d'affichage. Prêtez une attention plus particulière à la libération systématique de l'espace mémoire (i.e les cellules mortes) sous peine de désagréments.

La classe ``Substrat`` : elle a comme attribut principal un tableau d'unsigned short à deux dimensions, qui représente son état courant. Une instance de Substrat doit être capable de dire ce qu'il y a dans chaque case (rien, de l'énergie, 1 cellule, 2 cellules, ...). Elle doit également fournir les moyens de gérer l'énergie qui réside à sa surface. Pour une case (i, j) quelconque du tableau les cases adjacentes ont pour coordonnées (i-1, j-1), (i-1, j), (i-1, j+1), (i, j-1), (i, j+1), (i+1, j-1), (i +1, j), (i +1, j +1). Cependant certaines de ces cases n'existent pas si on considère une case située sur le bord du tableau. Par exemple la case (1, 1) possède uniquement 3 voisins. Trouver une solution astucieuse qui vous évitera bien des tests lors du calcul d'une nouvelle génération. Ce tableau pourra accueillir une population de taille au plus n x n avec n <= 20. D'un point de vue graphique, le tableau sera représenté par un quadrillage (invisible). Une case occupée sera symbolisée par un cercle (ou un sprite), centrée dans la case. A vous de trouver la formule qui donne en fonction de i, j et de la taille de la population les coordonnées dans votre fenêtre graphique du centre de la case (i; j).En terme de nombre de lignes de code, c'est a priori la classe la plus conséquente. En effet, elle doit gérer une matrice de codes correspondant au contenu de chaque case et garantir un isomorphisme de cette matrice sur la représentation graphique du substrat et de sa population. Pour cela, elle comporte entre autre un attribut privé statique qui correspond à une instance de Fenetre_Graphique ainsi qu'une "copie" de certaines méthode de cette classe. Elle doit être en mesure de rendre tout type de renseignement en rapport avec des coordonnées de la matrice : code, référence à une cellule, énergie résiduelle, ... Certains renseignements seront utiles aux instances des classes de cellules pour leur permettre de déterminer leur comportement. Enfin, de même que pour la classe Population, la classe Substrat comportera une méthode (par exemple : MisaAJour) qui mettra à jour l'ensemble des données dont elle a la responsabilité.

Module graphique

La classe mlgFenetre va vous permettre de visualiser graphiquement tout ce petit monde. Cette classe est fournie sous la forme d'une bibliothèque de nom libmlg.a et se trouve dans /home/partage/PUBLIC/C++ ainsi que son fichier d'en-tête et un petit programme de tests. Cette "bibliothèque", écrite en C++ et reposant sur la Xlib, la SDL et la SGE, est minimaliste mais permet de créer un fenêtre graphique, capables de prendre en compte deux évènements clavier (ESPACE et ESC) et d'afficher (via la notion de double-buffer) des "sprites" (ou lutins). A noter que les fichiers des images de sprites doivent être obligatoirement au format BMP.

Exemple de réalisation (à l'initialisation) :

screenshot

Options

Si ce projet vous passionne, vous trouverez ci-dessous des suggestions pour l'améliorer :

  • doter la classe Population d'une méthode permettant l'affichage d'une étude statistique sur la population lorsque la simulation prend fin (nombre total de cellules dans chaque couleur, répartition des âges, nombre de victoires et de défaites par couleur lors des affrontements, ...),
  • faire en sorte que la couleur des cellules change d'intensité selon le niveau de leur énergie,
  • dans la même optique, faire de même avec la taille des cellules qui serait liée à leur âge, les plus grosses étant par exemple les plus vieilles,
  • faire en sorte que "de temps en temps", des épidémies surviennent "détruisant" ainsi partiellement ou totalement certaines niches écologiques (on entend par là des groupes de cellules : par couleur, par âge, etc.)

Evaluation

Une soutenance de projet aura lieu qui permettra une première évaluation des fonctionnalités de l'application finale.

Afin d'évaluer la mise en oeuvre des principes de la programmation orientée objets, il vous est demandé : de créer une archive de vos sources (au format tar.gz), à votre nom et recopiée dans le répertoire /home/partage/PUBLIC/ProjetsC++. Dans cette archive devra être ajouté un fichier README, d'une page ou deux, qui expliquera vos choix et les grands principes de fonctionnement de votre programme

Il sera tenu compte : du nombre et de la pertinence des commentaires, de la qualité de la modularité (au minimum un fichier .h et .cc par classe définie), de la portabilité (production de l'exécutable) et de la mise en oeuvre des concepts de la POO ainsi que de la lisibilité du code fourni ("élégance" algorithmique).

Remarque : il est bien entendu que les options restent ... optionnelles. Toutefois, à condition que le reste du projet fonctionne, il sera tenu compte des efforts consentis.