Teaching - 2i002 - (TME: sujets)


2i002 : Introduction à la programmation Objet

Le jeu de la vie

Le monde est un damier de X cases sur Y appelées cellules (au départ, X=Y=20). Une cellule est soit vivante soit morte. Au départ, il y a 80% de cellules mortes. Chaque cellule a 8 voisins (même sur les bords car nous faisons l'hypothèse d'un monde torique où le haut est lié au bas et la gauche à la droite). C'est-à-dire par exemple que le voisin de droite d'une cellule du bord droit du damier a comme voisine de droite la cellule opposée du damier. Il en est de même pour toutes les cellules du bord du damier, qui ont pour voisines les cellules du bord opposé.

Exemple de monde (wikipedia):

Le monde évolue de génération en génération selon les règles suivantes:

  • une cellule meurt si elle a strictement moins de 2 voisins (mort par isolement) ou strictement plus de 3 (mort par surpopulation).
  • une cellule naît sur une case vide si celle-ci a exactement 3 voisins.

Classe Monde (et test)

Définir la classe Monde qui a quatre variables : la largeur du damier dimx, sa hauteur dimy, le numéro de la génération courante noGener et un tableau de booléens à 2 dimensions tabCells (true signifiant que la cellule est vivante, false qu'elle est morte).

Constructeur

Définir le constructeur Monde(int dimx, int dimy, double seuil) de cette classe qui crée un monde de dimx cellules sur dimy cellules avec un pourcentage approximatif de cellules vivantes déterminé par le seuil.
On pourra utiliser la méthode random de la classe Math qui génère une valeur aléatoire de type double comprise entre 0.0 inclus et 1.0 exclu.

public String toString()

Écrire la méthode public String toString() qui retourne une chaîne de caractères décrivant ce monde avec son numéro de génération et le tableau de l'état de ses cellules.

On visualisera le monde en représentant une cellule vivante par le caractère "*" et une cellule morte par le caractère ".".

Classe de test

Définir une classe TestJeuVie avec la méthode main qui crée un monde avec 20% (seuil = 0.2) de cellules mortes et le visualise.

La fonction Voisin et les modulos

Ajouter dans la classe Monde la méthode nbVoisins(int nuLign,int nuCol) qui retourne le nombre de cellules voisines vivantes de la cellule tabCells(nuLign, nuCol). Penser à utiliser la fonction % (modulo). Calculer le nombre de voisins d'une cellule revient à compter le nombre de cellules vivantes dans le carré de 3x3 dont le centre est cette cellule.

La question est délicate car la notion de voisinage boucle autour du terrain: le monde fait 20x20 (dans un premier temps)... Il propose des cases d'indice 0 à 19.

Mais le voisin de 19 c'est

  • 18 d'un coté
  • 0 de l'autre

Le monde est rond: on sort d'un coté => on rentre de l'autre

Pour compter le nombre de voisins actifs autour de (x,y), le code est donc difficile. Voici une aide

// Signature de la methode
// initialisation d'un compteur de voisin actif à 0
// pour i allant de x-1 à x+1
//   pour j allant de y-1 à y+1
//     definition des coordonnées en prenant en compte les effets de bords:
i2 = (i+dimx)%dimx;
j2 = (j+dimy)%dimy;
 

Exemple de comportement:

  • [NORMAL] x = 5 et on cherche le voisin de gauche
    • si i = 4 alors i2 = (4+20)%20 = 24%20 = 4 => inchangé !
  • [CRITIQUE] x = 0 et on cherche le voisin de gauche
    • si i = -1 alors i2 = (-1+20)%20 = 19%20 = 19 => ça marche !!! Le voisin de 0, c'est bien 19
  • [CRITIQUE] x = 19 et on cherche le voisin de droite
    • si i = 20 alors i2 = (20+20)%20 = 40%20 = 0 => ça marche !!! Le voisin de 19, c'est bien 0

Génération suivante

Ajouter, dans la classe Monde, la méthode void genSuiv() qui, à partir du tableau tabCells de la classe Monde, crée un nouveau tableau en y appliquant les règles du jeu de la vie données plus haut afin d'obtenir la génération suivante, puis bascule tabCells sur ce nouveau tableau.

Tester le jeu de la vie dans son ensemble:

  • Création d'un monde aléatoire
  • Entrée dans une boucle de générations
    • Passage à la génération suivante
    • affichage du monde (System.out.println + toString

Note: toutes les générations s'affichent d'un coup dans la console... Il peut plus agréable d'introduire une temporisation:

  • Entrée dans une boucle de générations
    • Passage à la génération suivante
    • affichage du monde (System.out.println + toString
    • temporisation

Code de la temporisation

 try {Thread.sleep(2000);} // temporisation en ms      
 catch(InterruptedException e){
    e.printStackTrace();
 }

Questions supplémentaires: les structures

La pages wikipedia suivante : lien vous donne des structures amusantes du jeu de la vie... Et nous avons envie de les tester.

Nous voulons donc créer un jeu entièrement vide puis ajouter l'une de ces structures... Ce qui va nous obliger à ajouter un constructeur.

Pour l'instant, la classe Monde compte un constructeur:

public Monde(int dimx, int dimy, double seuil)

Nouveau constructeur

Nous allons ajouter le constructeur suivant:

public Monde(int dimx, int dimy, int x, int y, boolean[][] motif)

Ce constructeur initialise un monde vide et ajoute un motif donné sous la forme d'un tableau aux coordonnées (x,y).

Dans le main, la commande suivante:

Monde m = new Monde(20, 20, 3,5,new boolean[][]{{true,true},{true,true}});

Provoquera la simulation suivante (affichage d'un bloc carré en (3,5)):

 . . . . . . . . . . . . . . . . . . . . 
 . . . . . . . . . . . . . . . . . . . . 
 . . . . . . . . . . . . . . . . . . . . 
 . . . . . * * . . . . . . . . . . . . . 
 . . . . . * * . . . . . . . . . . . . . 
 . . . . . . . . . . . . . . . . . . . . 
 . . . . . . . . . . . . . . . . . . . . 
 . . . . . . . . . . . . . . . . . . . . 
 . . . . . . . . . . . . . . . . . . . . 
 . . . . . . . . . . . . . . . . . . . . 
 . . . . . . . . . . . . . . . . . . . . 
 . . . . . . . . . . . . . . . . . . . . 
 . . . . . . . . . . . . . . . . . . . . 
 . . . . . . . . . . . . . . . . . . . . 
 . . . . . . . . . . . . . . . . . . . . 
 . . . . . . . . . . . . . . . . . . . . 
 . . . . . . . . . . . . . . . . . . . . 
 . . . . . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . . 
 . . . . . . . . . . . . . . . . . . . . 

Note: le bloc carré est stable: il ne bouge pas au fil des itérations du jeu de la vie

Interface graphique simple

La visualisation dans la console nous empêche de travailler sur des mondes plus vastes... Je vous propose d'utiliser la classe suivante SimpleInterface.java pour visualiser votre monde de manière plus agréable.

Vous devrez développer des accesseurs sur votre monde pour:

  • sa hauteur: int getH()
  • sa largeur: int getL()
  • sa case(i,j): boolean get(int i, int j)

Vous serez ensuite en mesure d'utiliser le main suivant:

import java.awt.Color;

...

 public static void main(String[]args){
        int x = 400, y = 300; // taille de la fenetre
        SimpleInterface ui = new SimpleInterface("Jeu de la Vie",x,y); // fenetre
        Monde m = new Monde(50,50,0.8); // monde 50x50

        ui.createArea( m.getH(), m.getL()); // creation de l'image dans l'interface
        ui.refresh();
        for (int t=0;t<1000;t++){ // mille pas de temps (arbitraire)
            try{Thread.sleep(100);}catch(InterruptedException e){e.printStackTrace();}
            m.genSuiv();
            for (int i=0;i<m.getH();i++)
                for (int j=0;j<m.getL();j++){
                    if(m.get(i,j))
                        ui.setRGB(i, j, Color.RED);
                    else
                        ui.setRGB(i, j, Color.WHITE);
                }
            ui.refresh();
        }
    }

Factory: création de motifs à l'aide de fonctions dédiées

On remarque rapidement que ce type de création est fastidieux et on voudrait l'améliorer. Nous allons créer la classe boite à outils : ToolsJeuDeLaVie qui contient (au moins) les méthodes suivante:

  • public static boolean[][] makeBloc();
  • public static boolean[][] makeGlisseur();

La syntaxe dans le main est alors bien plus agréable:

Monde m = new Monde(5,5,ToolsJeuDeLaVie.makeBloc());

Et pour le glisseur:

Monde m = new Monde(5,5,ToolsJeuDeLaVie.makeGlisseur());

Exemple de Glisseur évoluant de génération en génération (source: wikipedia)

Une fois les concepts de base assimilés, vous pouvez passer à des structures plus complexes comme le canon à glisseurs (source: wikipedia):

Le cannon à glisseur

Le cannon est une figure assez difficile à réaliser... Une image est disponible sur wikipedia et vous pouvez la télécharger ici.

Le motif fait 9 cases de haut et 36 de large... On ne va pas taper toutes les valeurs! Le but de cet exercice est de générer le tableau de booléen correspondant au motif directement à partir de l'image.

Gestion de l'image

Ajouter des import et une erreur possible dans la déclaration du main:

import java.awt.Color;
import java.io.File;
import java.io.IOException;
import javax.imageio.ImageIO;
import java.awt.image.BufferedImage;

...
public static void main(String[]args) throws IOException{

Lire une image sur le disque:

BufferedImage im = ImageIO.read(new File("glider_gun.png"))

Définir la méthode de création de votre tableau:

Signature:

public static boolean[][] makeFromImage(BufferedImage im, int ncase_dimh, int ncase_dimw)

Questions supplémentaires: retour aux images

Pour l'instant, l'affichage se fait sous forme de String dans la console... Il est possible de créer une méthode de conversion d'une String en Image pour visualiser une itération du jeu de la vie. NB: il s'agit d'un exercice pour mieux appréhender les String (sinon, il est bien plus simple de générer une image à partir du jeu directement).

Nous mettrons cette méthode parmi les outils développés précédemment dans la classe ToolsJeuDeLaVie. La signature de la méthode est:

import java.awt.Color;
import java.awt.image.BufferedImage;
public static  BufferedImage String2Image(String jeuStr);

L'algorithme pour créer cette image n'est pas simple. Voici une proposition:

  • Extraire le nombre de ligne de la String jeuStr (détails ci-après)
  • Extraire le nombre de colonne de la String jeuStr (détails ci-après)
  • Créer une image aux bonnes dimensions
BufferedImage im = new BufferedImage(nCol, nLigne, BufferedImage.TYPE_INT_ARGB);
  • initialiser les compteurs i et j à 0
  • parcourir tous les caractères c de jeuStr
    • si c == '\n'
      • i++; j = 0; // incrément ligne, retour à la colonne 0
    • si c == '*' // codage d'une case active
      • pixel noir aux coordonnées actuelles
im.setRGB( j,i, Color.black.getRGB());
  • j++ // passage à la colonne suivante

Note pour extraire le nombre de ligne de la String jeuStr:

  • int cpt = 0
  • Pour int c allant de 0 à jeuStr.length()
    • si str.charAt(i) == '\n'
      • cpt++

Note pour extraire le nombre de colonne de la String jeuStr:

  • int cpt = 0
  • Pour int c allant de 0 à jeuStr.length()
    • si str.charAt(i) == '\n'
      • break
    • cpt++ // décompte du nombre de caractères sur la première ligne

Cet algorithme permet de créer des images du type: