Automates cellulaires 2D : généralités #

Ce document est le plus grand dénominateur commun entre les différents travaux pratiques concernant les automates cellulaires en dimension 2. Vous devez avoir compris ce document avant de consulter les spécificités de tel ou tel automate :

Jeu de la vie
Simulation de feux de forêt
Propagation d’une épidémie

Vous pouvez aussi consulter la documentation sur les automates cellulaires 1D. Cette page doit cependant être suffisante pour comprendre de quoi il retourne.

Il est vivement recommandé de lire tout le sujet avant de commencer. Vous n’aurez pas ainsi à défaire ce que vous aurez fait…

Qu’est-ce qu’un automate cellulaire ? #

Nous ne prétendons pas ici donner une définition exacte ou exhaustive de ce qu’est un automate cellulaire. Nous parlerons seulement du type d’automate 2D utilisé dans les TPs de programmation.

Cellules et états #

Un automate cellulaire est une grille à maillage carré. Nous représenterons cette grille par un tableau en deux dimensions. Chaque case du tableau est appelé cellule. Chaque cellule peut être dans un certain état.

En ce qui nous concerne, l’état pourra être représenté par un nombre entier et le tableau représentant la grille sera donc un tableau d’entiers. Le nombre d’états différents que peut prendre une cellule est une caractéristique de l’automate considéré. Par exemple, dans le jeu de la vie, il y a deux états (mort ou vivant). Dans la simulation de feu de forêts, il y en a 4 (vide, arbre, feu ou cendre).

La grille (donc le tableau) sera modélisée par l’objet array de l’extension numpy :

import numpy as np
t = np.zeros((5, 5)) # Tableau nul de 5 cases par 5
t[2, 3] = 42 # Modification d'une case

Règles de transition #

Un automate cellulaire est un objet dynamique, qui change au cours du temps selon certaines règles. Ces changements concernent chacune des cellules. À la date t+1, l’état de toutes les cellules doit être recalculé et dépend uniquement des règles de transition et de l’état de ces cellules aux dates antérieures. En ce qui nous concerne, l’état d’une cellule particulière dépendra uniquement de l’état de ses cellules voisines (et d’elle même) à la date précédente. Nous pourrons considérer en revanche plusieurs types de voisinage, comme le voisinage de Moore (8 voisins) ou le voisinage de Von Neumann (4 voisins).

L’étant de la cellule (i,j) à la date t dépend uniquement des règles de transition, de son propre état à la date t et de l’état des cellules voisines (en 4-connexité ou 8-connexité) à la date t.

Pour la simulation de feu de forêt, par exemple, les règles de changement d’état sont :

Vide ⇨ Vide
Feu ⇨ Cendre
Cendre ⇨ Cendre
Arbres ⇨ Feu si un voisin est en feu et Arbre ⇨ Arbre sinon

Avec ces règles, l’automate serait modifié de la manière suivante (les couleurs sont explicites…) :

Représenter et animer un automate cellulaire #

Représentation de l’automate #

Pour représenter l’automate sur l’écran, nous devons représenter chaque case du tableau. On choisit généralement de représenter chaque état par un carré de couleur différente. Pour les feux de forêt, par exemple, on pourrait utiliser le code couleur suivant :

Vide : Noir
Arbre : Vert
Feu : Rouge
Cendre : Gris

Il sera commode d’utiliser une procédure spécifique pour afficher l’automate à l’écran. Cette fonction aura comme unique paramètre le tableau représentant l’automate (plus éventuellement la taille en pixels des carrés à dessiner).

afficher(tab) 
⎜ Répéter pour chaque case (i,j) du tableau tab 
⎜ ⎜ Si tab[i]|[j] = VIDE : Afficher un rectangle noir 
⎜ ⎜ Si tab[i]|[j] = ARBRE : Afficher un rectangle vert 
⎜ ⎜ Si tab[i]|[j] = FEU : Afficher un rectangle rouge
⎜ ⎜ Si tab[i]|[j] = CENDRE : Afficher un rectangle gris 
⎜ ⎣
⎣

L’algorithme précédent n’est qu’une ébauche. En particulier, l’unique boucle en cache en fait deux (une pour les abscisses et une pour les ordonnées), et les coordonnées (i,j) doivent subir une transformation. Vous résoudrez ces différents points au moment de programmer (vous devrez adapter ce qui précède au langage Python et à la bibliothèque graphique que vous utiliserez).

Évolution dans le temps #

Nous devrons aussi disposer d’une fonction ou procédure qui modifie l’automate en le faisant passer de l’étape t à l’étape t+1. Le seul paramètre nécessaire sera le tableau représentant l’automate à la date t. C’est ici que seront implantées les règles de transition de l’automate. Vous pouvez vous inspirer de l’algorithme suivant :

suivant(tab) 
⎜ Copier le contenu de tab dans un nouveau tableau tab2
⎜ Répéter pour chaque case (i,j) du tableau tab2 
⎜ ⎜ Mettre dans tab[i][j] l'état suivant de la case i,j, 
⎜ ⎜ qui dépend de tab2[i][j], des cases voisines, et 
⎜ ⎜ des règles de transition. 
⎜ ⎣
⎣

Il est primordial d’avoir bien compris pourquoi un second tableau (ici tab2) est nécessaire. Demandez de l’aide à l’encadrant si nécessaire.

Comme précédemment, les boucles Répéter pour cachent en fait deux boucles (une pour i, et une pour j).

Enfin, le corps de la boucle principale dépend des règles de transition de l’automate. Il est conseillé de faire appel à d’autres fonctions dans cette partie, pour compter le nombre de voisins par exemple. Vous devrez aussi trouver un moyen de gérer le cas des cellules en bordure de tableau, car elles n’ont pas le même voisinage que les autres.

À la fin, votre fonction ou procédure suivant doit être courte. Si elle grossit trop, c’est très certainement que vous avez oublié d’écrire des fonctions annexes.

Animation #

L’animation de l’automate sera simplement obtenue en appelant alternativement suivant et afficher.

Structure générale #

La structure générale du programme sera la suivante :

Programme principal
⎜ Ouvrir une fenêtre graphique
⎜ Initialiser le tableau tab : procédure init()
⎜ Répéter indéfiniment
⎜ ⎜ suivant(tab)
⎜ ⎣ afficher(tab)
⎣ Terminer le programme

La procédure init() devra initialiser correctement l’automate cellulaire (placer des arbres dans le cas des feux de forêt par exemple).

Le programme principal, en Python, devra être exécuté ainsi :

if __name__ == '__main__':
    main()

afin de permettre l’importation silencieuse de votre fichier.

Détails #

Il y a quelques détails techniques qui n’ont peut être pas été vus par ailleurs :

Pour éviter de mentionner les états des cellules en donnant leur valeurs numériques, il est possible d’utiliser un dictionnaire Python :

st = {"VIDE": 0, "ARBRE": 1, "FEU": 2, "CENDRE": 3}

Puis, on fera référence aux états ainsi :

if tab[i, j] == st["ARBRE"]:

ce qui est plus lisible que :

if tab[i, j] == 1:

Arrivés à ce point, vous pouvez reprendre la lecture du sujet concernant Vous devrez adapter ce qui précède au langage Python et à la bibliothèque graphique que vous utiliserez.

l’automate particulier que vous allez réaliser et commencer à le programmer. Le point suivant, que vos pourrez reprendre plus tard est plus complexe et vous indique comment animer l’écran et permettre les interactions avec l’automate. Vous pourrez en prendre connaissance une fois que vous aurez réalisé l’automate de la manière que nous venons de décrire.

Programmation de la version non interactive #

Votre programme doit impérativement comporter, en plus du programme principal :

une fonction d’initialisation du tableau : init
une fonction de passage au tableau suivant : suivant
une fonction d’affichage : afficher

Dans un premier temps, vous pouvez écrire un programme non interactif. Vous ne pourrez pas agir sur l’interface pendant l’exécution du programme, mais vous pourrez tester toutes vos fonctions.

Il est conseillé de programmer dans cet ordre :

coder la fonction d’initialisation du tableau
coder la fonction d’affichage du tableau
coder le programme principal qui initialise et affiche (en appelant les fonctions écrites aux points 1 et 2)
tester et corriger les bugs
coder la fonction de passage au tableau suivant
modifier la procédure principale pour calculer quelques générations, en ménageant une pause entre chaque affichage de manière à pouvoir contrôler manuellement le bon fonctionnement entre chaque étape
tester et corriger les bugs
finaliser le programme
tester et corriger les bugs

Programmation de l’automate interactif #

Cette partie est facultative dans un premier temps. Programmez d’abord l’automate avant de commencer ce travail

L’idée est maintenant de réaliser un programme interactif. L’affichage sera animé, et l’utilisateur pourra agir sur la fenêtre pour, par exemple :

Changer l’état d’une cellule dans le jeu de la vie
Modifier les règles d’un automate pendant son exécution (appui sur une touche)
Ajouter des foyers d’incendie dans la simulation des feux de forêt
…

Le principe est basé sur la gestion des événements. Le module graphique que vous utilisez permet probablement :

de gérer les événements souris, clavier etc…
d’appeler une fonction en tâche de fond : ce sera l’animation de l’automate

Pour réaliser cette partie, vous devrez donc consulter la documentation et les exemples relatifs au module que vous utilisez pour réaliser la partie graphique. En particulier, recherchez les informations relatifs aux événements et à la boucle de gestion des événements.

Python #

Pour représenter les tableaux, vous pouvez utiliser l’extension NumPy. Les fonctions suivantes peuvent vous être utiles :

import numpy as np
t = np.zeros((100, 100), dtype=np.int32) # tableau 100x100 d'entiers mis à 0
t2 = t.copy() # Réalise une copie du tableau t (alors qu'une simple affectation ajouterait simplement une référence)
t2.shape # Tuple de deux valeurs indique la taille de t2

Vous serez amené à utiliser des nombres aléatoires :

import random
a = random.randint(4, 19) # nombre entier entre 4 et 19 inclus

Documentations qui peuvent vous êtres utiles :