Tp2 : Le jeu de la vie
(hiver 2005)
Démonstrateur: Sébastien Gambs.
Date de remise: Mercredi 20 avril 2005 avant minuit.
A faire en équipe de 2 ou individuellement (mais pas à plus que deux!!!).
Vous devez faire un programme en Java qui résout le problème décrit plus bas.
- Respectez à la lettre le format de sortie demandé dans l'énoncé.
- Vous trouverez un exemple de classe Java illustrant comment implémenter l'interface graphique de la classe ColorGrid.java qu'on vous demande d'utiliser ici (voir l'annexe pour les détails concernant la classe ColorGrid).
- Remarque: contrairement à d'habitude, il n'y aura pas de prototype mis a disposition pour ce tp.
Problème: Le jeu de la vie
Le jeu de la vie est ce qu'on appelle un automate cellulaire. Il a été inventé par le mathématicien anglais Conway en 1970. Comme vous allez le voir, il s'agit d'un jeu aux règles très simples mais à partir desquelles on peut voir émerger des motifs complexes. Beaucoup de recherches ont été faites sur ce jeu depuis sa naissance, entre autres il a été prouvé que tout ce qui pouvait être calculé par un ordinateur moderne peut aussi l'être par un modèle aussi simple que celui du jeu de la vie (autrement dit les deux modèles sont calculatoirement équivalents).
Le jeu de la vie est un jeu à "zéro joueur" dont l'évolution est déterminée uniquement par une configuration initiale et un ensemble de règles très simples. Il n'y a pas d'intervention de l'être humain à part pour la mise en place de la configuration initiale.
Le jeu se déroule sur une grille de cellules en deux dimensions. Chaque cellule a donc 8 voisins que sont les cellules adjacentes (incluant celles en diagonale).
L'état de la grille (qui représente de facon abstraite la vie dans un milieu) évolue au fil des époques (aussi appelées générations). A chaque époque, une cellule peut-être soit vivante, soit morte.
L'état de la grille évolue de facon discrète par génération. En particulier l'état de la grille pour une époque donnée dépend
seulement de l'état de la grille à l'époque précédente et des règles. Lorsqu'on passe d'une époque à une autre toutes les cellules sont mises à jour simultanément en utilisant les règles suivantes:
- Une cellule morte avec 3 voisins vivants autour devient à son tour vivante (autrement dit il y a naissance).
- Une cellule vivante avec 2 ou 3 voisins autour reste vivante.
- Dans tous les autres cas la cellule meurt soit à de la solitude (s'il n'y a pas assez de voisins autour d'elle), soit à cause de la surpopulation (s'il y en a trop). Aussi, si la cellule était déjà morte, elle le reste.
Dans le jeu de la vie, on peut caractériser certaines motifs (ou formes de vie) qui apparaissent pendant le jeu en fonction de leur comportement. En particulier, une forme de vie peut être stable, oscillante ou encore se déplacer sur la grille.
Exemples de forme de vie stable, càd n'évoluant pas entre deux époques si isolé du reste par au moins une case vide tout autour:
- Un bloc

- Un bateau

Exemples de forme de vie oscillante, càd alternant constamment entre deux états d'une époque à l'autre:
- Un clignotant

- Un crapaud

Exemples de forme de vie se déplacant, càd bougeant sur la grille au fil des époques:
- Un glisseur

- Un vaisseau spatial

Exemple en mouvement du glisseur:

Il existe aussi des formes plus complexes qui peuvent générer des motifs se répétant à l'infini. Par exemple, c'est le cas du canon à glisseurs:

Mais que font donc les formes suivantes avec des noms si poétiques ;0)?
- Meurs difficilement

- Le gland

Instructions
Votre but dans ce tp est double. D'une part, il s'agit d'implémenter la class "GameOfLife.java" telle que décrite avec les fonctionnalités ci-dessous et d'autre part, il s'agit décrire "Tp2.java" la classe qui permettra de tester votre classe GameOfLife et de jouer avec elle.
Pour ce qui concerne l'interface graphique elle-même permettant de voir la grille du jeu de la vie, on vous fournit la classe ColorGrid. Voir l'annexe en bas de cette page pour une description de cette classe.
La class GameOfLife
Voir ci-dessous pour la liste des fonctions que vous devez implémenter dans la classe GameOfLife. Noter bien qu'il est important que vous respectiez le nom des fonctions tel que demandé et que vous en implémentiez le maximum sous peine de ne pas avoir tous les points.
Vous pouvez aussi rajouter n'importe quelle fonction qui pourrait vous être nécessaire ou vous facilitez la vie. Il est aussi permis évidemment d'appeler des fonctions de la classe à l'intérieur d'autres fonctions de la classe. Lors de la notation, l'ingéniosité avec laquelle vous avez écris et entrelacé vos fonctions sera pris en compte, ainsi que la clarté, la lisibilité et l'originalité. En particulier, vous êtes encouragé à rendre votre code clair et lisible plutôt que lourd et opaque ;0).
Voici la liste des fonctions attendues:
-
Constructeur de GameOfLife
Prend en entrée deux entiers représentant le nombre de lignes et de colonnes de la grille, doit ensuite initialiser les variables globales de la classe telle que la grille, le nombre de lignes et de colonnes ainsi que l'époque initiale.
-
Fonction randomInitialization
Initialise la grille de facon aléatoire en mettant chaque cellule comme étant morte ou vivante de manière équiprobable.
-
Fonction nbNeighboursAlive
Prend en entrée deux paramètres qui sont les coordonnées d'une cellule de la grille et renvoie en sortie le nombre de voisins vivant de cette cellule.
Remarque: lorsque vous cherchez les voisins, vous devez tenir des "effets de bord" en considérant que la grille est continue et fermée sur elle-même. En particulier par exemple, si vous dépassez en bas, vous vous retrouvez en haut et si vous partez trop à droite après la limite, vous devez considérer arriver par la gauche.
-
Fonction evolution
Fonction qui ne prend pas de paramètres en entrée et ne retourne rien. Elle doit simplement faire évoluer le jeu en le faisant avancer d'une époque et en mettant à jour la grille de facon adéquate.
-
Fonction isEmptySquare
Vérifie si une zone de la grille formant un carré est vide (càd qu'elle ne contient que des cellules mortes). Cette fonction prend trois paramètres en entrée: les coordonnées du coin supérieur gauche du carré sous forme d'entier et la longueur en nombre de cellules d'un côté du carré.
Cette fonction renvoie vrai si la zone est complètement vide et faux autrement.
-
Fonction addBlock
Cette fonction doit être implémentée sous deux variantes portant chacune exactement le même nom.
La première variante ne prend pas de paramètre en entrée et ajoute un objet de type "bloc" (voir plus haut pour la forme d'un bloc) dans la grille à un endroit choisi aléatoirement.
A noter que la fonction doit vérifier que la zone est vide avant d'ajouter un "bloc" à un endroit. Si ce n'est pas le cas, on génère un autre endroit choisi aléatoirement jusqu'à ce qu'on trouve une place de libre.
La deuxième variante de la fonction doit prendre en entrée les coordonnées d'une cellule et construire le "bloc" de telle manière à ce que cette cellule soit le coin supérieur gauche du "bloc".
Remarque 1: petit indice, vous avez le droit d'appeler la deuxième variante de la fonction à l'intérieur de la première si cela peut vous aider et simplifier le code.
Remarque 2: pour vérifier si une zone est vide ou non, vous pouvez utiliser la fonction isEmptySquare définie plus haut.
Remarque 3: juste pour rappel, souvenez vous que la case de coordonnées (0,0) correspond à celle située en haut à gauche de la grille.
-
Fonction addBoat
Mêmes instructions exactement que pour la fonction précédente sauf que cette fois vous devez ajouter un "bateau" dans la grille.
Là aussi vous devez implémenter deux variantes, une qui place le "bateau" de facon aléatoire et l'autre qui prend les coordonnées d'une cellule en paramètres d'entrée.
Comme précédemment aussi assurez vous que la zone est vide avant d'ajouter la forme "bateau" à cet endroit.
-
Fonction addBlinker
Mêmes instructions exactement que pour la fonction précédente sauf que cette fois vous devez ajouter un "clignotant" dans la grille.
Là aussi vous devez implémenter deux variantes, une qui place le "clignotant" de facon aléatoire et l'autre qui prend les coordonnées d'une cellule en paramètres d'entrée.
Comme précédemment aussi assurez vous que la zone est vide avant d'ajouter la forme "clignotant" à cet endroit.
-
Fonction addToad
Mêmes instructions exactement que pour la fonction précédente sauf que cette fois vous devez ajouter un "crapaud" dans la grille.
Là aussi vous devez implémenter deux variantes, une qui place le "crapaud" de facon aléatoire et l'autre qui prend les coordonnées d'une cellule en paramètres d'entrée.
Comme précédemment aussi assurez vous que la zone est vide avant d'ajouter la forme "crapaud" à cet endroit.
-
Fonction addGlider
Mêmes instructions exactement que pour la fonction précédente sauf que cette fois vous devez ajouter un "glisseur" dans la grille.
Là aussi vous devez implémenter deux variantes, une qui place le "glisseur" de facon aléatoire et l'autre qui prend les coordonnées d'une cellule en paramètres d'entrée.
Comme précédemment aussi assurez vous que la zone est vide avant d'ajouter la forme "glisseur" à cet endroit.
-
Fonction addSpaceShip
Mêmes instructions exactement que pour la fonction précédente sauf que cette fois vous devez ajouter un "vaisseau spatial" dans la grille.
Là aussi vous devez implémenter deux variantes, une qui place le "vaisseau spatial" de facon aléatoire et l'autre qui prend les coordonnées d'une cellule en paramètres d'entrée.
Comme précédemment aussi assurez vous que la zone est vide avant d'ajouter la forme "vaisseau spatial" à cet endroit.
-
Fonction copyGame
Cette fonction ne prend aucun paramètre en entrée mais retourne un objet de type GameOfLife qui est une copie conforme du jeu de la vie actuel tel qu'il est.
-
Fonction isWorldDead
Retourne vrai si le monde est mort, càd que toutes les cellules sont mortes, et faux autrement.
Fonction isWorldStable
Retourne vrai si le monde est stable, càd qu'il est dans une configuration telle qu'il ne bouge plus époque après époque, et faux autrement.
Remarquez que tout monde mort est un monde stable mais que tout monde stable n'est pas un monde mort.
-
Fonction isWorldOscillating
Retourne vrai si le monde est en train d'osciller, càd qu'il est dans une situation telle qu'il oscille (alterne) constamment entre deux états, et faux autrement.
Remarquez qu'un monde oscillant est par définition ni un monde mort, ni un monde stable mais que son évolution est en quelque sorte stoppée aussi puisqu'il est incapable d'arrêter d'alterner entre les deux mêmes configurations.
-
Fonction frequencyCellAlive
Fonction qui retourne la fréquence des cellules de la grille qui sont vivantes par rapport à la quantité totale de cellules.
-
Fonction clearUniverse
Fonction qui efface complètement le monde actuel en mettant toutes les cellules comme étant mortes.
Interface usager
Vous devrez faire un menu qui permettra de tester les fonctionnalités de votre classe GameOfLife. Avant de faire apparaître le menu vous devez commencer par demander à l'utilisateur le nombre de lignes et de colonnes de la grille ainsi que le nombre d'époques pendant lesquelles il voudra laisser évoluer le jeu de la vie.Par exemple:
Nombre de lignes:
Nombre de colonnes:
Nombre d'epoques:
Ensuite, votre menu devra s'afficher comme suit:
Faites votre choix:
Effacer monde(1)
Generer monde aleatoire(2)
Ajouter bloc(3)
Ajouter bateau(4)
Ajouter clignotant(5)
Ajouter crapaud(6)
Ajouter glisseur(7)
Ajouter vaisseau spatial(8)
Ajouter zoo(9)
Demarrer simulation(10)
Quitter(0)
Le numéro qui est à côté de chacune des options représente l'entrée que l'usager doit taper pour prendre ce choix. Par exemple, si l'usager veut ajouter un "crapaud" dans le monde, il doit taper "6".
Lorsque l'usager tape "1" cela efface le monde et en crée un nouveau qui est vierge, alors que si au contraire l'utilitaire tape "2", il l'initialise un nouveau monde en appelant randomInitialisation.
Les commandes de "3" à "8" correspondent tous à ajouter un objet dans le monde si c'est possible. Cet objet doit être ajouté dans un endroit déterminé au hasard.
Si jamais l'utilisateur entre "9", ce qui correspond à "ajouter un zoo" alors le programme doit rajouter dans le monde un exemplaire de chaque type:
bloc, bateau, clignotant, crapaud, glisseur et vaisseau spatial. Là aussi, il faut les ajouter au hasard. L'ordre lui-même dans lequel on le fait n'est pas vraiment important tant qu'il reste de la place libre sur la grille.
Enfin lorsque l'utilisateur entre "10", la simulation du jeu de la vie doit commencer et la grille sous forme graphique doit apparaître pour pouvoir montrer l'évolution au fur et à mesure des générations. Lors d'une époque donnée si une cellule est vivante elle doit être coloriée en noir et si elle est morte en blanc.
L'affichage de la grille graphique doit se faire de manière à ce qu'on puisse observer l'évolution du jeu. Utilisez la classe ColorGrid pour implémenter cette fonctionnalité.Par exemple en utilisant la commande "pause(0.25)" de ColorGrid (voir l'annexe ci-dessous pour plus de détails), il est possible de faire patienter la grille pendant un quart de seconde avant que l'affichage soit mis à jour ce qui est suffisant pour un être humain pour observer relativement tranquillement l'évolution.
Le nombre d'époques pendant lequel l'évolution doit se poursuivre est celui entré par l'utilisateur au départ. Une fois que ce nombre d'époques s'est écoulé, la fenêtre graphique de la grille doit disparaître d'elle même et un retour au menu doit se faire.
Lors du déroulement du jeu de la vie, le programme doit marquer en texte l'evolution du monde à chaque époque. En particulier, il faut à chaque époque indiquer le numéro de l'époque actuelle ainsi que la fréquence des cellules vivantes. Si jamais le monde devient aussi mort, stable ou oscillant, il faut aussi l'indiquer par un message.
Pour quitter la simulation, l'utilisateur doit simplement taper "0" une fois devant le menu.
Remise
Votre devoir doit être remis le mercredi 20 avril 2005 avant minuit. Tout programme remis en retard sera pénalisé de 25% par jour de retard.
Vous devez rendre votre programme grâce au programme remise. Vous devez remettre les fichiers Tp2.java et GameOfLife.java. Assurez-vous que vous avez
indiqué clairement dans un entête de ce fichier, vos deux noms et numéros d'étudiant.
La remise est faite avec la commande:
remise ift1010 tp2 Tp2.java GameOfLife.java
Vous pouvez voir ce que vous avez remis avec la commande:
remise -v ift1010 tp2
Remarque: remettre un fichier une deuxieme fois écrase la version précédente.
Barême de correction
- Le format de sortie tel que demandé par l'énoncé doit être respecté à la lettre sous peine de sanctions au niveau des points.
- La qualité du code sera grandement tenu en ligne de compte pour la correction. Attention aux commentaires, à l'indentation, à la logique, à l'efficacité ou encore l'organisation de votre programme!!!
- Si le programme ne compile pas, aucun point relatif à l'exécution ne sera accordé.
- N'hésitez pas à nous contacter et nous faire part de vos suggestions, demandes d'éclaircissement ou bugs. Et encore une fois, n'hésitez pas à poser des questions.
Annexe: Question bonus
Ajouter à votre menu la possibilité de mettre la forme "meurs difficilement" ou "le gland" ou encore "le canon à glisseurs". Si vous ajoutez les deux premières ou la troisième (ou encore toutes les trois), il y aura un petit bonus de 0.5 points pour la note.
N'hésitez pas aussi à prendre le temps d'observer comment réagissent ces formes plus complexes (pas de point bonus pour ca par contre ;0)).
Annexe: Détails de la classe ColorGrid.java
ColorGrid.java
- ColorGrid est une classe qui constitue une grille de cases pour laquelle on peut déterminer la couleur de chacune.
- Remarque importante: afin de pouvoir utiliser correctement la classe ColorGrid (et surtout la classe Color), importez les deux librairies suivantes en incluant les deux lignes suivantes tout au début de votre fichier Java où vous utilisez ColorGrid:
import java.awt.*;
import java.swing.*;
- Chacune des cases est numérotées selon la rangée et la colonne. Le système de coordonnées utilisé
est le même que celui utilisé dans les matrices. Ainsi, la case (0,0), donc (ligne = 0, colonne = 0), correspond à la case en
haut à gauche de la grille.
- Plusieurs méthodes vous sont fournies dans cette classe. Ce sont toutes des fonctions statiques.
- initialize(int cellSize, int nbRangee, int nbCols): initialise l'interface graphique. Pour ce faire, cette méthode doit recevoir la taille de chacune des cases (cellSize), le nombre de rangée de la grille (nbRangee), et le nombre de colonnes(nbCols).
- setCellColor(r, c, Color color):mets à jour la couleur de la case (rangee = r, colonne = c) en lui attribuant la couleur color
- getCellColor(r, c):récupère la couleur de la case (rangee = r ,colonne = c)
- pause(double s):pause pendant s secondes
- stop():ferme l'interface graphique
Annexe: Eléments de l'API Java: Math.random() et Color
Math.random():
=======> retourne aléatoirement
un double compris entre 0 et 1 inclusivement. Un indice pour vous aider à générer des événements selon une certaine probabilité p. La probabilité qu'un nombre donné par Math.random() soit plus petit que p, est exactement égale à p. Pensez-y un bon coup, la solution n'est pas loin derrière cet indice...
Color
(voir les champs pour les couleurs de base possibles) :
ColorGrid.getCellColor( x, y ).equals( Color.BLUE );
=======> retourne vrai si la
couleur obtenue avec getCellColor est
Color.BLUE