Le jeu de la vie

D'après un article de Pierre Tougne, paru dans "Pour la Science", Juin 1982.

Au début des années 1970, le jeu de la vie de John Conway a conquis les États-Unis puis l'Europe, et sa vogue se poursuit encore aujourd'hui. Le jeu de la vie se prêtant particulièrement à la simulation sur ordinateur, de mauvaises langues prétendirent que les écrans graphiques auraient été conçus pour permettre aux informaticiens d'y jouer.

John Conway est un mathématicien important. Son jeu de la vie, qui appartient à la classe des jeux de simulation, cherche à modéliser l'évolution d'organismes vivants. Il se joue sur un damier infini, sur les cases duquel sont disposés des pions représentant les cellules d'un organisme. Ces cellules naissent, meurent ou survivent à chaque génération selon des règles bien précises. Conway a choisi ces règles de sorte que l'évolution de ces organismes soit imprévisible et chaotique, notamment en ce qui concerne leur disparition, leur caractère périodique ou leur croissance infinie.

Toute case d'un damier infini comporte huit voisines : quatre orthogonalement et quatre en diagonale. Cela étant, les lois de la génétique de Conway sont les suivantes :

1. SURVIE. Toute cellule ayant exactement deux ou trois cellules voisines survit à la génération suivante.

2. MORT. Toute cellule ayant quatre cellules voisines ou plus meurt par étouffement à la génération suivante. Une cellule isolée ou n'ayant qu'une seule cellule voisine meurt d'isolement à la génération suivante.

3. NAISSANCE. Sur une case vide comportant exactement trois cellules voisines, il naît une cellule à la génération suivante.

Ces règles sont simultanées pour une génération donnée : la naissance d'une cellule sur une case n'influe pas sur la survie ou la mort des cellules de la génération précédente. Autrement dit, les seules cellules que l'on doit prendre en compte pour l'établissement de la génération future sont celles de la génération "actuelle".

Choisissons maintenant quelques organismes simples ( à trois, quatre ou cinq cellules adjacentes, soit orthogonalement, soit diagonalement ) et étudions leurs générations successives. Un peu d'expérimentation montre que dans quelques cas ces organismes meurent mais que le plus souvent ils conduisent soit à des organismes stables, c'est à dire identiques de génération en génération, soit à des oscillateurs, c'est à dire des organismes qui se retrouvent identiques à eux mêmes et à la même place au bout d'un certain nombre de générations appelé la période de l'oscillateur :

(source : M2M http://www.xyzt.way.com/life.html)

Expérimenter : suivre le déroulement des genérations sur l'applet de la page http://cgi.student.nada.kth.se/cgi-bin/d95-aeh/get/life
L'on pourra en particulier essayer les configurations remarquables suivantes

stable
oscillante
glissante
autres

Ces expérimentations amènent deux remarques :

• Une modification infime dans la génération initiale peut produire d'énormes modifications dans l'évolution de l'automate : le processus relève des mécanismes du chaos.
  
• L'évolution de l'automate n'est pas prévisible de façon analytique, c'est à dire par un procédé général de calcul, un algorithme. Le mécanisme d'automate cellulaire est très simple. Pourtant pour répondre à la question "cette population va-t elle croître indéfiniment ou diparaître ?" une simulation est indispensable. Et la simulation ne donnera des réponses que dans des cas particuliers, sans garantie de réponse en un temps fini. Le problème est indécidable.

Dans notre simulation, nous allons utiliser un espace fini, rectangulaire, avec une rangée de cellules vides sur chaque bord. Pour réaliser le programme de simulation, les générations successives peuvent être représentées dans un même tableau à deux dimensions. Chaque case du tableau est un objet cellule.

Nous avons donc identifié le besoin de deux classes d'objets :

1. une classe pour l'espace, le plan composé de cellules,
   
2. une classe pour les objets cellules.

Les fonctionnalités du plan, la classe "espace cellulaire" sont de :

• encapsuler le tableau de cellules,
  
• créer une population initiale, en créant ses objets "cellule",
  
• faire tourner l'algorithme, c'est à dire boucler sur
  1. afficher l'automate,
  2. calculer la génération suivante ;
     
• et de gérer l'attirail technique nécessaire au graphisme en Java et au séquencement des affichages.

Cette classe accède aux cellules par les méthodes correspondant aux fonctionnalités de la classe "cellule" :

• encapsuler les données sur la position géographique de la cellule et son état (occupé ou vide),
  
• initialiser un objet cellule,
  
• rendre occupée une cellule qui était vide,
  
• savoir si une cellule est vide ou occupée,
  
• calculer l'état à la génération suivante d'une cellule en fonction de son état et de son nombre de voisins,
  
• mémoriser l'état d'une cellule pour que les calculs de changement de génération se fassent sur l'ancien état des cellules tout en créant le nouveau tableau des états,
  
• et l'attirail technique pour afficher graphiquement la cellule.

Le programme, comportant ces deux classes se trouve à Lifegame.java, en voici la liste. Nous allons l'examiner pour en comprendre

1. la syntaxe
2. les instructions "simples" : affectation, for, if
3. les tableaux
4. les méthodes et les classes
5. le fonctionnement algorithmique

Les mécanismes "d'interface système", comme le graphisme, les threads, l'applet, les exceptions, seront admis comme des nécessités pour que le programme fonctionne.

//* Applet du jeu de la vie Copyright Amadeus mai 1998 http://www.chez.com/theamadeus/ *// import java.awt.*; import java.applet.*; /*--------- Lifegame : automate la classe Lifegame gère la simulation d'un automate cellulaire dans un plan 10x10, (dont les bords sont toujours vides) cette classe fait appel à la classe Cellule -------------------------------------*/ public class Lifegame extends Applet implements Runnable { // début de la classe principale static int N = 10; // taille du plan Cellule[][] plan = new Cellule[N][N]; // le plan 10x10 est composé de cellules //=========================================================== // code de gestion de la tâche de séquencement des générations, à 4 Hz Thread tickTock; // tâche d'exécution pour rafraichir l'affichage public void start() { if (tickTock == null) { tickTock = new Thread(this); tickTock.start(); } public void stop() { if (tickTock != null) { tickTock.stop(); tickTock = null; } } public void run() { // calculer indéfiniment, quatre générations par seconde while (true) { try { Thread.currentThread().sleep(250); } // séquencement à 4 Hz catch (InterruptedException e) {} super.repaint(); } // pour affichage de l'automate } //=============================================================   //======== init() initialisations public void init() { // créer un plan NxN de cellules vides for (int i=0; i<N; i++) for (int j=0; j<N; j++) { plan[i][j] = new Cellule(i, j, this.getGraphics()); } /* new : instancier un objet Cellule i,j : aux coordonnées (i,j) getGraphics : initialiser le graphisme */ // placer un motif de cellule occupées = génération initiale plan[5][4].creer(); plan[5][5].creer(); plan[5][6].creer(); } // fin d'init   //=== update() passage d'une génération à la suivante ================= public final synchronized void update (Graphics g) { g.setColor(Color.white); // rend la couleur blanche g.fillRect(0,0,20*N,20*N); // dessine le fond // 1) afficher l'automate, ancienne génération for (int i=0; i<N; i++) for (int j=0; j<N; j++) plan[i][j].paint(); //affiche la cellule // 2) mémoriser l'état de l'ancienne génération for (int i=0; i<N; i++) for (int j=0; j<N; j++) plan[i][j].basculer(); // 3) calculer la génération prochaine for (int i=1; i<N-2; i++) // on parcourt le plan en long for (int j=1; j<N-2; j++) { // et en large /* nombre de cellules occupées adjacentes au point (i,j) */ int voisinage= plan[i-1][j-1].etat()+plan[i-1][j].etat()+plan[i-1][j+1].etat() +plan[i][j-1].etat()+plan[i][j+1].etat() +plan[i+1][j-1].etat()+plan[i+1][j].etat()+plan[i+1][j+1].etat(); // louvel état plan[i][j].changementGeneration(voisinage); } } // update() } // fin de la classe principale Lifegame   /*--------- Cellule ----------------------------------------------- la classe Cellule décrit les fonctionnalités d'une cellule de l'automate -----------------------------------------------------------------*/ class Cellule { int x,y; // coordonées de la cellule dans l'automate boolean celluleOccupee; // état de la cellule, true si occupée boolean ancienEtat; // état de la cellule à la génération précédente private Graphics g; // pour le graphisme  //======== etat() ========================================= // retourne l'état de la cellule, 0 si vide, 1 si occupée public int etat() { int occupe=1; int vide=0; if (ancienEtat) return occupe; // retourne 1: la cellule est occupée else return vide; // retourne 0: la cellule est vide } // etat()   //======== basculer() ====================================== // changement de génération, mémoriser l'état de la cellule public void basculer() { ancienEtat = celluleOccupee; }   //======== changementGeneration() ========================= public void changementGeneration (int nombreVoisins) { if (ancienEtat) // cellule reste occupee si exactement 2 ou 3 voisins celluleOccupee = (nombreVoisins==2) || (nombreVoisins==3); else // naissance si exactement 3 voisins celluleOccupee = (nombreVoisins==3); } //======== Cellule() ======================================= //constructeur de cellule public Cellule(int coordx, int coordy, Graphics appletG) { g=appletG; //pour le graphisme this.x=coordx; this.y=coordy; this.celluleOccupee=false; // à la génèse le monde était vide } //======== creer() ======================================== // déclarer la cellule occupée public void creer () { this.celluleOccupee=true; } //======== paint() ============================================= // graphisme : affichage de la cellule public void paint(){ int nx,ny; nx=15*x; ny=15*y; if (celluleOccupee) { // si cellule occupée g.setColor(Color.black); g.fillOval(nx+1,ny+1,15-2,15-2); } // dessiner = cercle noir else { // si cellule vide g.setColor(Color.white); g.fillRect(nx+1,ny+1,15-2,15-2);} // effacer = carré blanc } } // fin de la classe Cellule

L'appel de l'applet dans une page html se faisant par le tag (comme on pourra le voir en examinant le code html de cette page web) :

<applet code=Lifegame.class width=200 height=200> </applet>

Enfin ce tag d'appel de l'applet étant inséré dans la page web, voici l'exécution du jeu de la vie :

L'applet plus élaborée et interactive du jeu de la vie, due à Andreas Ehrencrona (http://www.student.nada.kth.se/~d95-aeh/) essayée à la page http://cgi.student.nada.kth.se/cgi-bin/d95-aeh/get/life, a son code à http://www.student.nada.kth.se/~d95-aeh/Life.class et son source à http://www.student.nada.kth.se/~d95-aeh/Life.java

NB 1 : Une étude sur la programmation du jeu de la vie en Pascal se trouve à http://dafne.mines.u-nancy.fr/~tisseran/EEIGM/exercices/exos6.shtml et le corrigé, toujours en Pascal, à http://dafne.mines.u-nancy.fr/~tisseran/cours/pascal/jeu_de_la_vie.html

NB 2 : Le web rengorge de documents, de logiciels et d'applets sur le jeu de la vie.

http://dafne.mines.u-nancy.fr/~tisseran/compilation/exposes/phan/automat/automata.html et http://dafne.mines.u-nancy.fr/~morier/java/java.htm, dans la rubrique "on n'est jamais si bien servi que par soi-même

http://www.webdo.ch/hebdo/hebdo_1996/hebdo_01/viart_01_jeu.html des explications et un logiciel

http://www.infini.fr/~tmorin/jdlv.htm une très bonne page avec de nombreux liens actualisés

http://www.tdc.bandai.co.jp/~okada/js_test_room/life/life.html une très belle réalisation en JavaScript !

On trouvera d'autres références sur http://dir.yahoo.com/Science/Artificial_Life/Cellular_Automata/Conway_s_Game_of_Life/

juin 1998