Game Life

Présentation⚓︎

Il s'agit d'un grand classique qui permet, pour des débutants, de mettre en œuvre :

la manipulation de matrices
la séparation du modèle et de la représentation
la mise en place d'une petite interface graphique (cela peut être du simple ascii art)

Rappel historique et références⚓︎

Mathématiquement, il s'agit d'un automate cellulaire dont les règles ont été définies par J. H. Conway en 1970 ¹

Les automates cellulaires et le jeu de la vie en particulier sont des systèmes complexes étudiés en mathématiques et en informatique théorique. Ainsi, l'automate de Conway a été prouvé turing-complet².

Références plus ludiques et abordables

Une vidéo de D. Louapre pour la chaine ScienceEtonnante
Une galerie étonnante
Un article d'Interstices qui présente aussi un autre automate : le compteur de parité
Un article de Pour la Science, un peu plus complexe mais montrant la puissance qui se cache derrière ce petit jeu.

Début de la modélisation⚓︎

Bon, mais on va faire des maths ?

Non, nous allons utiliser un notebook et le module ipythonblocks pour modéliser et jouer avec le jeu de la vie.

Exemples

Un planeurCanon Gosper³

planeur

canon

À faire vous-même

Installer le module ipythonblocks :
```
pip install impythonblocks
```
Manipuler avec ce notebook

Rappel des règles⚓︎

Règles du jeu

R0. VoisinageR1. Mort par isolementR2. VieR3. NaissanceR4. Mort par étouffement

Les cellules tout autours d'une cellule sont ses voisines. Normalement le jeu de la vie se joue sur une surface infinie : toutes les cellules ont donc exactement 8 voisines. Sur l'exemple de planeur, on a simulé cette infinité par une zone en boule (le côté bas et replié sur celui du haut et le côté droit sur le gauche).

Parfois, au contraire on limite la zone pour simuler l'infinité : pour l'exemple du canon à planeurs, si on faisait revenir les planeurs par le haut ils viendraient détruire la structure.

Ci-dessous une cellule et ses voisines :

voisinage

Une cellule qui n'a pas au moins 2 voisines vivantes meurt. Ci-dessous, les deux cellules sont voisines, mais n'ont chacune qu'une voisine et vont mourir au prochain tour :

isolees \(\longrightarrow\) vide

Une cellule vivante qui a 2 ou 3 voisines vivantes reste vivante au tour suivant.

Ci-dessous la cellule noire à 2 voisines vivantes (en rouge). Par contre chacune de ces deux voisines n'a qu'une seule voisine vivant et va donc mourir d'après la règle R1.

Une cellule naît à un emplacement sans cellule, entouré d'exactement 3 cellules vivantes.

Ci-dessous, les deux emplacements marqués en vert ont 3 cellules voisines vivantes et vont donc voir naître une cellule vivante au prochain tour.

Une cellule vivant qui possède 4 voisines vivantes ou plus, meurt.

Ci-dessous, la cellule vivante en rouge va mourir au prochain tour :

etouffement_1 \(\longrightarrow\) etouffement_2

Exemple

Le motif suivant, est périodique. Il s'agit du clignotant :

clignotant_1 \(\longrightarrow\) clignotant_2 \(\longrightarrow\) \(\longrightarrow\)

Classe `GameLife`⚓︎

Dans un premier temps, il s'agit de créer une classe GameLife qui aura un nom en paramètre (ce nom sera le nom, sans l'extension du fichier stockant la structure de départ).

Les attributs

height et width pour les dimensions de la matrice qui va stocker le modèle de notre jeu de la vie ie une matrice de 0 (cellule morte) et de 1 (cellule vivante).
initial et grid sont les matrices de la structure ; initiale (celle qui ne bougeara pas et pourra servir pour un éventuel reset) et courante (celle qui évolue lors des différentes générations)
block_grid sera un objet BlockGrid pour la visualisation

À faire vous-même

ÉnoncéSolution

Définissez une classe GameLife. N'hésitez pas à introduire des constantes. On pourra en plus du nom comme paralètre du constructeur, ajouter :

infini un booléen qui vaudra True si la zone de notre structure est simulée infinie (comme enroulée sur une boule)
size un entier pour la taille de la représentation des cellules avec BlockGrid.

class GameLife:

    WHITE = (230, 230, 230)
    BLACK = (0, 0, 0)
    COLORS = WHITE, BLACK
    SIZE = 5
    DELTAS = (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1)
    ALIVE = 1
    DEAD = 0
    MAX_STEPS = 500
    EXT = '.life'
    PLAIN = {'.':DEAD, 'O':ALIVE}

    def __init__(self, name=None, infini=True, size=5):
        # modele
        self.name = name
        self.infini = infini
        self.height = 0
        self.width = 0
        self.initial = [] # le motif initial, mémorisé pour un éventuel reset
        self.grid = []    # motif courant, celui qui sert à l'affichage

        # pour la visualisation
        self.size = size # taille d'une cellule carrée
        self.block_grid = None

        if name is not None:
            self.load()

Nous poursuivons la modélisation par les principales méthodes.

Charger une structure⚓︎

Il est possible de créer à la main ou aléatoirement une structure initiale. Mais au début, le plus intéressant est de partir de structures connues, stockées au préalable dans des fichiers textes. Nous utiliserons le format plain text présenté conwaylife wiki.

Les fichiers porteront l'extension .life.

Contenu de planeur.life

.................................
..O..............................
...O.............................
.OOO.............................
.................................
.................................
.................................
.................................
.................................
.................................
.................................
.................................
.................................

À faire vous-même

ÉnoncéSolution

Écrire une méthode load qui permette d'initialiser les matrices avec le nom du ficher si celui-ci n'est pas None (on réserve la posibilité de créer un jeu de la vie sans structure prédéfinie, pour la suite).

def load(self):
    """Initialise la grille avec un motif stocké dans le fichier self.name.life"""
    with open(self.name + GameLife.EXT) as motif:
        for line in motif:
            grid_line = [GameLife.PLAIN[e] for e in line.strip()]
            self.initial.append(grid_line)
            self.grid.append(grid_line.copy())
    self.height = len(self.grid)
    self.width = len(self.grid[0])
    self.init_view()

La méthode init_view initialise le block_grid pour réprésenter correctement la structure qu'on vient de charger.

Calculer la nouvelle génération⚓︎

Il s'agit de calculer la matrice grid de l'étape suivante, en appliquant les règles du jeu de la vie. Attention il faudra passer par une matrice intermédiaire.

Puisque les valeurs de la matrice sont des 0 et des 1, pour connaître le nombre de voisins vivants d'une case il suffit de sommer les valeurs des cases voisines.

À faire vous-même

ÉnoncéSolution

Définir une méthode one_step qui calcule 1 pas d'évolution et met à jour la matrice grid.

def alive(self, line_id, col_id):
    return self.grid[line_id][col_id] == GameLife.ALIVE

def new_state(self, line_id, col_id):
    nb_alive_around = sum(self.grid[i][j] for i, j in self.neighboors(line_id, col_id))
    if self.alive(line_id, col_id):
        return int(2 <= nb_alive_around <= 3)
    else:
        return int(nb_alive_around == 3)

def one_step(self):
    """Calcule 1 génération"""
    tmp = [[self.new_state(line_id, col_id) for col_id in range(self.width)] for line_id in range(self.height)]
    self.grid = [line.copy() for line in tmp]

Visualiser⚓︎

grid représente le modèle, et block_grid est la vue de notre jeu de la vie. Cette vue est donc un objet BlockGrid dont la dimension est celle de la grid, et avec deux couleurs de remplissage : GameLife.WHITE pour les cellules vides et GameLife.BLACK pour les cellules vivantes.

Là encore, on se sert du modèle des 0 et 1 pour récupérer automatiquement la bonne couleur depuis la constante GameLife.COLORS :

GameLife.COLORS[self.grid[i][j]]

donne la couleur de la cellule de coordonnées (i, j).

À faire vous-même

ÈnoncéSolution

Définir une méthode update_view qui met à jour block_grid.

def update_cell(self, line_id, col_id, color):
    self.block_grid[line_id, col_id] = color

def update_view(self):
    for line_id, col_id in self.coords():
        zero_un = self.grid[line_id][col_id]
        self.update_cell(line_id, col_id, GameLife.COLORS[zero_un])

On utilisera ensuite la méthode show d'un BlockGrid pour afficher la grille de couleurs dans la sortie de la cellule notebook.

Finaliser le projet⚓︎

Définir une méthode play pour pouvoir lancer un certain nombre de générations et provoquer un affichage sympathique : toutes les générations dans la même cellule du notebook pour donner l'illusion de mouvement.
Ajouter des méthodes on et off pour pouvoir allumer ou éteindre manuellement une cellule. Associé à la possibilité de créer une instance GameLife sans nom de fichier, on pourra créer ses propres motifs.
Ajouter la possibilité de générer un motif initial aléatoire
... imaginez ce que vous voulez

L'article est de M. Gardner : Mathematical Games -- The fantastic combinations of John Conway's new solitaire game "life", pdf version ↩
Schématiquement cela signifie que le système à la même puissance de calcul théorique qu'un ordinateur (voir Turing-complet sur wikipédia, ou pour les plus armés en mathématiques le cours de l'école Polytechnique sur les fondements de l'Informatique) ↩
Du nom de son inventeur, Bill Gosper, mathématicien et informaticien américain ↩

Game Life

Présentation⚓︎

Rappel historique et références⚓︎

Début de la modélisation⚓︎

Rappel des règles⚓︎

Classe GameLife⚓︎

Charger une structure⚓︎

Calculer la nouvelle génération⚓︎

Visualiser⚓︎

Finaliser le projet⚓︎

Classe `GameLife`⚓︎