Le jeu de la vie

Un automate cellulaire consiste en une grille régulière de « cellules » contenant chacune un « état » choisi parmi un ensemble fini et qui peut évoluer au cours du temps. L'état d'une cellule au temps t+1 est fonction de l'état au temps t d'un nombre fini de cellules appelé son « voisinage ». À chaque nouvelle unité de temps, les mêmes règles sont appliquées simultanément à toutes les cellules de la grille, produisant une nouvelle « génération » de cellules dépendant entièrement de la génération précédente.

Les automates cellulaires sont étudiés en mathématiques et en informatique théorique. Le modèle des automates cellulaires est remarquable par l'écart entre la simplicité de sa définition et la complexité que peuvent atteindre certains comportements macroscopiques.

Système unidimensionnel

Présentation

Nous allons considérer une grille unidimensionnelle de cellules ne pouvant prendre que deux états : 0 ou 1, et nous allons définir des règles basées sur une cellule et ses deux voisines immédiates.

Exemple :

Partant de cette grille unidimensionnelle, considérons que la couleur de chaque cellule dépend de ses voisines. Voici par exemple une règle simple :

• si une cellule est noire, elle reste noire
• si une cellule est blanche, elle devient noire si elle possède au moins une voisine noire.

Sur plusieurs générations successives, nous pouvons superposer les lignes obtenues et ainsi obtenir une image qui sera une représentation graphique de la règle que nous avons considérée.

Mise en code

Nous allons utiliser Python pour automatiser le comportement de ces automates cellulaires unidimensionnels. Chaque case sera pour l'instant représentée par un élément d'un tableau, qui sera égal à 0 ou 1. Notre objectif d'ici la fin de la séance sera de générer une image pixel par pixel grâce à la librairie PIL (cf TP précédent).
L'exemple ci-dessus donnera donc, dans un premier temps, dans une sortie console :

000010000
000111000
001111100
011111110

Préparation de la matrice

À la façon d'une image numérique, nous allons ranger nos générations successives dans une matrice, c'est-à-dire pour notre exemple une liste de chaînes de caractères.

matrice = ["000010000"]
# Ici, matrice est une liste de listes. Pour l'instant, elle n'en contient qu'une seule : ["000010000"]
# Pour ajouter une génération, on fera :
matrice.append("000111000")

# On peut visualiser le résultat obtenu :
print("print(matrice) : \n", matrice)

# Ou, si on veut afficher les lignes les unes au-dessus des autres :
print("Avec une boucle for :")

for generation in matrice:
    print(generation)

Appliquer les règles

Pour pouvoir appliquer appliquer la règle à une cellule, nous devons regarder les cellules voisines. Nous allons donc utiliser une boucle for avec un index d'itération.
Par exemple, dans le code ci-dessous, pour afficher la cellule courante et ses voisines :

generation = "000010000"

for i in range(len(generation)):
    print("cellule courante : ", generation[i])
    if i > 0:
        print("cellule précédente : ", generation[i-1])
    if i+1 < len(generation):
        print("cellule suivante : ", generation[i+1])
    print("---------")

Programme complet

# définition des fonctions
# ...
# python
# python
# python
# ...

# déroulé du programme :
matrice = ["000010000"]
nb_generations = 4

for g in range(nb_generations):
    matrice.append(nouvelle_gen(matrice[g]))

Création d'images

Nous pouvons désormais utiliser notre code pour générer une image qui contiendra les générations successives de notre automate cellulaire.
Voici le code Python qui fera le nécessaire :

from PIL import Image

gen_1 = "00000000000000000000100000000000000000000"

matrice_pic = Image.new("1", (len(gen_1), len(gen_1)), color=1)

def regle_A(gen, indice):
    # définition de la fonction
    

def nouvelle_gen(generation):
    n_gen = ""
    for i in range(len(generation)):
        n_gen += regle_C(generation, i)
    
    return n_gen
    
    
def print_line(image, line):
    image.putdata(line)

# déroulé du programme :
matrice = [gen_1]

pxl_data = []

for g in range(len(gen_1)):
    matrice.append(nouvelle_gen(matrice[g]))
    
    for px in matrice[g]:
        pxl_data.append(1-int(px))
        
    print(matrice[g])


matrice_pic.putdata(pxl_data)
matrice_pic.show()

D'autres règles

Essayez le code précédent avec les règles B et C ci-dessous :

def regle_B(gen, indice):
    cur = int(gen[indice])
    if indice > 0:
        prev = int(gen[indice - 1])
    else:
        prev = 0
    if indice + 1 < len(gen):
        next = int(gen[indice + 1])
    else:
        next = 0

    if prev + next == 2 or prev + next == 0:
        return '0'
    else:
        return '1'

def regle_C(gen, indice):
    return str(1 - int(regle_B(gen, indice)))

Pour aller plus loin...

Vous pouvez lire cet article de Science étonnante dont ce TP est inspiré, et/ou regarder la vidéo associée, sur la chaîne YouTube de... Science étonnante !