Fonctionnement
Le but de cet article n’est pas d’expliquer les automates cellulaires ou leur fonctionnement, mais de montrer un exemple d’implémentation en python. Voici une vidéo qui explique le fonctionnement de l’automate cellulaire single rotation : Les automates cellulaires réversibles - Passe-science #23.
Implémentation
Grille de cellules
Nous allons créer un objet qui représente une grille de cellules. Pour cela, il faut d’abord penser à quelques détails.
Premièrement, la structure de données utilisée pour représenter la grille. Le plus simple en python est d’utiliser une liste de listes de booléens, où True
représente une cellule pleine, et False
une cellule vide.
Nous allons donc créer l’objet Grid
. Cet objet aura pour fonction de représenter des grilles en 2D.
Objet Grid
Pour l’initialisation de l’objet Grid
, il faut prendre en paramètre la hauteur et la largeur (height
et width
) souhaitée.
On veut ensuite être sûr que la grille peut être divisée en un voisinage de Margolous, ce qui veut dire que l’on veut une hauteur et une largeur paires.
Enfin, on peut créer cette liste de liste de booléens.
class Grid():
def __init__(self, width: int, height: int):
self.width: int = 2 * int(width / 2)
self.height: int = 2 * int(height / 2)
self.__grid: bool = [[False for _ in range(self.width)]
for _ in range(self.height)]
Ici, j’ai nommé self.__grid
l’attribut qui contient la grille. Le fait de faire commencer le nom de l’attribut par __
(deux tirets du bas) fait qu’il devient un attribut privé. Cela signifie qu’il ne sera pas accessible en dehors de l’objet : il est possible d’utiliser self.__grid
, mais si vous créez un objet Grid
, vous ne pourrez pas lui trouver d’attribut _grid
.
J’utilise cela car je veux protéger la modification de cet attribut : je veut que, lorsque l’on essaie de le modifier, il soit possible uniquement de lui donner une valeur qui est une grille correcte (c’est-à-dire une grille de booléens). J’ai donc écrit un accesseur et un mutateur (getter et setter en anglais) :
class Grid():
...@property
def grid(self) -> list[list[bool]]:
"""Retourne la grille booléenne"""
return self.__grid
@grid.setter
def grid(self, new_grid: list[list[bool]]) -> None:
"""Vérifier que `new_grid` est correctement typé comme list[list[bool]], et de la bonne taille en fonction de `self.width` et `self.height`."""
assert len(new_grid) == self.height
assert all(len(line) == self.width for line in new_grid)
self.__grid = new_grid
Indexer des cellules dans la grille
Pour manipuler la grille, il est nécessaire d’avoir la possibilité de récupérer le contenu de la grille. Pour cela, on veut pouvoir indexer la grille.
Surchage de l’indexation avec __getitem__
En python, il est possible de définir soi-même ce qui se passe lorsque l’on indexe un objet que l’on a créé.
Dans le cas d’une grille, le code est très simple, puisqu’il suffit d’indexer la liste sous-jacente :
class Grid:
...def __getitem__(self, idx: int):
return self.__grid[idx]
Indexation qui gère les dépassements sur les bords
D’un point de vue théorique, les automates cellulaires fonctionnent souvent sur une grille infinie. Il est possible de simuler cela, par exemple en faisant grandir la grille seulement quand cela est nécessaire. Cependant, une solution plus évidente consiste à utiliser une grille finie.
Un des moyens les plus simples de gérer les bords d’une grille finie est de supposer que les bords sont reliés entre eux. Par exemple, dans le jeu Pac Man, lorsque le personnage se déplace jusqu’au bord droit de la grille, il se téléporte au bord gauche, et inversement : les deux bords sont comme “reliés”. Nous allons donc utiliser un principe similaire pour notre automate cellulaire : les bords opposés seront reliés.
Ce choix possède 2 principaux avantages : il évite d’avoir un “bord” dans notre simulation (généralement, cela serait un contour de cellules qui sont toujours mortes quoi qu’il arrive), et surtout il est très simple à programmer : il suffit d’utiliser l’opérateur modulo : %
. En effet, l’opérateur modulo permet simplement de faire cela avec des entiers. Si vous prenez un nombre n
, faîtes n % 10
, et n
reviendra à 0 dès que vous dépasserez 10, de la même manière que la position doit revenir à gauche dès que l’on dépasse la droite.
Nous allons donc implémenter la fonction get_item
, qui récupère le contenu d’une cellule à une position donnée, mais en prenant en compte note principe de “dépassement” : si la position donnée dépasse un bord, elle sera renvoyée à 0.
class Grid:
...def get_item(self, y: int, x: int) -> bool:
bool = self.__grid[y % self.height][x % self.width]
grid_at_idx: return bool(grid_at_idx)
Affichage
Il faut maintenant penser à l’affichage.
Un petit problème est que les caractères sur un terminal sont généralement 2 fois plus haut que larges. Il vaut donc mieux afficher une cellule avec 2 caractères si on veut éviter d’avoir une image déformée (écrasée horizontalement) de notre grille.
Par exemple, on pourrait utiliser 2 espaces pour une cellule vide, et []
pour une cellule pleine.
Il faut donc bien penser à diviser par 2 la largeur de l’affichage par rapport à la largeur réelle de la fenêtre de terminal.
Pour afficher notre grille, nous allons surcharger la méthode __str__
. Cela permet de donner à python une nouvelle façon de transformer notre objet en chaîne de caractères. Il suffira ensuite de faire str(ma_grille)
pour avoir une chaîne de caractères qui représente la grille dans son état actuel. Le code est simplement un parcours de la grille qui crée au fur et à mesure la chaîne de caractères :
class Grid:
...def __str__(self) -> str:
= ""
res for line in self.__grid:
for elt in line:
+= "[]" if elt else " "
res += "\n"
res return res
Voisinage de margolous
Transformer en sous-grille
Il nous faut maintenant coder une méthode qui permettra de manipuler le voisinage de Margolous. Le moyen que j’ai utilisé est de diviser la grille principale en une “grille de grilles” : chaque groupe de 4 cellules du voisinage est mis dans une grille à part, et l’ensemble de tous ces groupes de grilles forme lui-même une grille. C’est assez logique, puisque lorsque l’on visualise ce voisinage, on a tendance à voir une “grande grille”, elle-même subdivisée en plus petits carreaux.
Il faut donc coder une fonction qui permet de transformer notre grille normale en ce que j’ai appelé une subgrid (sous-grille). Voici mon code :
class Grid:
...def get_subgrid(self):
# attention : width et height sont les dimensions de subgrid
# soit la moitié des dimension de self.grid
= self.width // 2, self.height // 2
width, height # on initialise une grille vide
= [[0 for _ in range(width)] for _ in range(height)]
subgrid # on parcoure les indices de cette grille vide
for y in range(height):
for x in range(width):
# On multiplie par 2 pour revenir à des indices sur grid
# x et y en minuscules : indices dans subgrid
# X et Y en majuscules : indices dans grid (du coin supérieur gauche)
= 2 * y
Y = 2 * x
X # on créée une grille 2x2 pour le voisinage de margolous
= Grid(2, 2)
cell # on remplis cette grille avec les valeurs de la grille
= [[self.get_item(Y, X), self.get_item(Y, X+1)],
cell.grid self.get_item(Y+1, X), self.get_item(Y+1, X+1)]]
[# on met cette cellule de voisinage dans subgrid au bon endroit
= cell
subgrid[y][x] return subgrid
Mais l’intérêt du voisinage de Margolous est qu’il se décale une fois sur deux. Il faut donc ajouter un argument à la fonction. Je l’ai appelé shift
(décalage en anglais), et les valeurs possibles sont 0 (aucun décalage) ou 1 (décalage d’une cellule vers la droite et vers le bas). Voici la fonction réécrite avec l’argument shift
:
class Grid:
...def get_subgrid(self, shift: int):
= self.width // 2, self.height // 2
width, height = [[0 for _ in range(width)] for _ in range(height)]
subgrid for y in range(height):
for x in range(width):
= shift + 2 * y
Y = shift + 2 * x
X = Grid(2, 2)
cell = [[self.get_item(Y, X), self.get_item(Y, X+1)],
cell.grid self.get_item(Y+1, X), self.get_item(Y+1, X+1)]]
[= cell
subgrid[y][x] return subgrid
Récupérer depuis une sous-grille
Il faut maintenant faire l’opération inverse : à partir de subgrid
, il faut être capable de reconstituer le contenu de la grille normale.
class Grid:
...def set_from_subgrid(self, subgrid: list[list[Grid]]):
for y in range(self.height):
for x in range(self.width):
self.__grid[y][x] = subgrid[y//2][x//2][y%2][x%2]
Il faut à nouveau faire attention au fait que le voisinage de Margolous se décale une fois sur deux. Lorsque le décalage (shift
) est de 1, la sous-grille (subgrid
) est décalée par rapport à la grille. Dans ce cas, il faut donc faire le décalage inverse. Cela consiste à déplacer la première colonne de la grille en dernière place, et la première ligne à la fin. Le module numpy
possède une fonction roll
qui permet justement de faire cette opération. Il faut l’importer (ainsi que la fonction array
qui permet de transformer notre grille en objet manipulable par numpy). La méthode roll
modifie l’objet afin de faire ce décalage inverse :
from numpy import array as np_array
from numpy import roll as np_roll
class Grid:
...def roll(self):
self.__grid = np_array(self.__grid)
self.__grid = np_roll(self.__grid, 1, axis=0)
self.__grid = np_roll(self.__grid, 1, axis=1)
Enfin, il faut modifier légèrement la fonction set_from_subgrid
afin qu’elle fasse ce décalage lorsque c’est nécessaire, en fonction de la valeur de shift
(qui doit donc être passé en argument).
class Grid:
...def set_from_subgrid(self, subgrid: list[list], shift: int):
for y in range(self.height):
for x in range(self.width):
self.__grid[y][x] = subgrid[y//2][x//2][y%2][x%2]
if shift == 1:
self.roll()
Appliquer les règles
Faire tourner une grille de voisins
Il faut maintenant une fonction qui fait tourner une grille de 4 cellules.
Comme il n’y a que 4 valeurs dans chaque cellule de voisinage, il est possible de coder “à la main” cette rotation : on crée une nouvelle grille de 4 valeurs qui est une copie élément par élément de notre cellule de voisinage, mais avec une rotation. Voici le code correspondant :
def rotate_cell(cell: Grid) -> Grid:
= Grid(2, 2)
new_cell = [[cell[0][1], cell[1][1]],
new_cell.grid 0][0], cell[1][0]]]
[cell[return new_cell
Faire tourner seulement selon les règles
L’automate single rotation n’effectue une rotation que si les cellules sont seules dans leur voisinage. Il faut donc implémenter cette fonction : étant donné un voisinage, s’il contient une seule cellule, le faire tourner, sinon ne rien faire.
def single_rotation(cell: Grid) -> Grid:
# if there is only one alive cell in the 2x2 neighbourhood
if sum((cell[0][0], cell[0][1], cell[1][0], cell[1][1])) == 1:
return rotate_cell(cell)
return cell
Appliquer les règles sur toute la sous-grille
Il faut simplement créer une nouvelle sous-grille à partir de la grille actuelle, en appliquant single_rotation
sur chaque cellule de voisinage.
def single_rotation_on_subgrid(sub: list[list[Grid]]) -> list[list[Grid]]:
return [[single_rotation(cell) for cell in line]
for line in sub]
tout faire fonctionner ensemble : step
On peut maintenant coder la fonction qui fait avancer la simulation d’une étape : la fonction step
. Elle prend en argument le décalage (shift
) (j’ai décidé de ne pas le calculer automatiquement pour ne pas donner une responsabilité de plus à mon objet Grid
qui contient déjà beaucoup de choses).
class Grid:
...def step(self, shift: int =0):
= self.get_subgrid(shift=shift)
sub = single_rotation_on_subgrid(sub)
sub self.set_from_subgrid(sub, shift=shift)
Lancer l’exécution
Initialiser une grille
Remplir la grille aléatoirement
On peut vouloir initialiser une grille remplie aléatoirement. Pour cela, on a besoin de la fonction random
du module random
, et d’une nouvelle méthode dans Grid
:
from random import random
class Grid:
...def randomize_grid(self, proportion: float =.3):
self.grid = [[random() < proportion for _ in range(self.width)]
for _ in range(self.height)]
Il est aussi intéressant de ne pas remplir toute la grille, mais seulement une portion. Par exemple, uniquement un cercle d’un rayon donné :
class Grid:
...def randomize_grid_circle(self, radius: int, proportion: float =.3):
"""Randomize the grid, but fill only cells that are in a circle of the given radius."""
self.grid = [[(i**2 + j**2 < radius**2) * (random() < proportion)
for i in range(self.width)]
for j in range(self.height)]
Faire fonctionner la simulation
Il ne reste que quelques étapes pour faire fonctionner notre automate cellulaire. D’abord, il faut choisir la taille de notre grille. Pour cela, on peut utiliser la fonction get_terminal_size()
du module os
, qui permet de récupérer la taille de la fenêtre de terminal dans laquelle le programme tourne. Cela va permettre d’adapter la taille de la grille automatiquement à la taille de la fenêtre de terminal.
Il faut donc importer cette fonction :
from os import get_terminal_size
Et ajouter ce code à la fin de notre programme
if __name__ == "__main__":
# on récupère la taille de la fenêtre de terminal
= get_terminal_size()
width, height # il faut diviser la largeur par 2 car chaque cellule prends 2 caractères de largeur
= Grid(width//2, height)
G # on remplis aléatoirement une partie de la grille
=10, proportion=.3)
G.randomize_grid_circle(radius# boucle d'exécution
while True:
# on calcule l'étape suivante puis on affiche
0)
G.step(print(G, end="")
1)
G.step(print(G, end="")
Meilleur affichage
Si vous exécutez le programme que j’ai décrit pour l’instant, vous remarquerez que l’affichage “saute” : il vacille, comme s’il y avait un câble mal branché sur un vieil écran de télévision.
La raison est assez simple : afficher du texte dans un terminal est plutôt lent, et le fait de remplir l’écran avec du texte prend autant de temps que de calculer l’étape suivante.
Il y a plusieurs solutions à ce problème.
Appuier sur une touche pour aller à l’étape suivante
Une solution très simple consiste à faire en sorte l’utilisateur doive appuyer sur une touche à chaque fois qu’il veut voir l’étape suivante. Cela permet de limiter la vitesse à laquelle les étapes avancent, et donc de limiter les problèmes d’affichage. Pour cela, il suffit d’utiliser la fonction input
de python.
if __name__ == "__main__":
= get_terminal_size()
width, height = Grid(width//2, height)
G =10, proportion=.3)
G.randomize_grid_circle(radiuswhile True:
0)
G.step(input(G)
1)
G.step(input(G)
Cela élimine la plupart des tressautements, mais ne l’élimine pas complètement.
Utiliser sys.stdout.write
La fonction stdout.write
du module sys
est un peu plus rapide que la fonction print
. La fonction stdout.write
ne convertit pas automatiquement les objets en chaîne de caractères comme la fonction print
. Il faut donc convertir vous-même la grille avec la fonction str
.
if __name__ == "__main__":
from sys import stdout
= get_terminal_size()
width, height = Grid(width//2, height)
G =10, proportion=.3)
G.randomize_grid_circle(radiuswhile True:
0)
G.step(str(G))
stdout.write(1)
G.step(str(G)) stdout.write(
Ajouter une pause entre chaque étape
Le problème que nous avons maintenant est que l’affichage est trop rapide pour que l’on voie toutes les étapes. Il est préférable d’ajouter une pause pour être sûr que le rafraîchissement soit effectué à chaque fois.
if __name__ == "__main__":
from sys import stdout
from time import sleep
= get_terminal_size()
width, height = Grid(width//2, height)
G =10, proportion=.3)
G.randomize_grid_circle(radiuswhile True:
0)
G.step(str(G))
stdout.write(0.03)
sleep(1)
G.step(str(G))
stdout.write(0.03) sleep(
Il y aura toujours quelques problèmes d’affichage, surtout si vous affichez une grille assez grande, mais l’affichage sera beaucoup plus fluide.
Meilleur caractère pour afficher les cellules pleines
Pour un meilleur rendu visuel, j’utilise le caractère █
(full block). Vous pouvez simplement modifier la fonction __str__
pour mettre le caractère que vous préférez.
Le code complet
from numpy import array as np_array
from numpy import roll as np_roll
from random import random
from os import get_terminal_size
class Grid():
def __init__(self, width: int, height: int, proportion: float =.3):
self.width: int = 2 * int(width / 2)
self.height: int = 2 * int(height / 2)
# the actual grid of cells
self.__grid: bool = [[False for _ in range(self.width)]
for _ in range(self.height)]
# set random cells in the grid
self.randomize_grid(proportion)
@property
def grid(self) -> list[list[bool]]:
return self.__grid
@grid.setter
def grid(self, new_grid: list[list[bool]]) -> None:
# make sure that the given value is correctly typed
assert len(new_grid) == self.height
assert all(len(line) == self.width for line in new_grid)
self.__grid = new_grid
def randomize_grid(self, proportion: float =.3):
self.grid = [[random() < proportion for _ in range(self.width)]
for _ in range(self.height)]
def randomize_grid_circle(self, radius: int, proportion: float =.3):
"""Randomize the grid, but fill only cells that are in a circle of the given radius."""
self.grid = [[(i**2 + j**2 < radius**2) * (random() < proportion)
for i in range(self.width)]
for j in range(self.height)]
def __getitem__(self, idx: int):
return self.__grid[idx]
def get_item(self, y: int, x: int) -> bool:
"""Index the grid, but avoid index error with a modulo.
Basically the same as self.__grid[y][x], but makes the grid "wrap around".
"""
bool = self.__grid[y % self.height][x % self.width]
grid_at_idx: # make sure to get only True of False
return bool(grid_at_idx)
def get_subgrid(self, shift: int):
"""The subgrid is the grid of squares of the margolous neighbourhood.
It makes it a list[list[list[list[bool]]]] of dimensions
(width/2) × (height/2) × 2 × 2"""
= self.width // 2, self.height // 2
width, height = [[0 for _ in range(width)] for _ in range(height)]
subgrid for y in range(height):
for x in range(width):
= shift + 2 * y
Y = shift + 2 * x
X = Grid(2, 2)
cell = [[self.get_item(Y, X), self.get_item(Y, X+1)],
cell.grid self.get_item(Y+1, X), self.get_item(Y+1, X+1)]]
[= cell
subgrid[y][x] return subgrid
def set_from_subgrid(self, subgrid: list[list], shift: int):
for y in range(self.height):
for x in range(self.width):
self.__grid[y][x] = subgrid[y//2][x//2][y%2][x%2]
if shift == 1:
self.roll()
def roll(self):
self.__grid = np_array(self.__grid)
self.__grid = np_roll(self.__grid, 1, axis=0)
self.__grid = np_roll(self.__grid, 1, axis=1)
def step(self, shift: int =0):
= self.get_subgrid(shift=shift)
sub = single_rotation_on_subgrid(sub)
sub self.set_from_subgrid(sub, shift=shift)
def __str__(self) -> str:
= ""
res for line in self.__grid:
for elt in line:
+= "██" if elt else " "
res += "\n"
res return res
def rotate_cell(cell: Grid) -> Grid:
= Grid(2, 2)
new_cell = [[cell[0][1], cell[1][1]],
new_cell.grid 0][0], cell[1][0]]]
[cell[return new_cell
def single_rotation(cell: Grid) -> Grid:
# if there is only one alive cell in the 2x2 neighbourhood
if sum((cell[0][0], cell[0][1], cell[1][0], cell[1][1])) == 1:
return rotate_cell(cell)
return cell
def single_rotation_on_subgrid(sub: list[list[Grid]]) -> list[list[Grid]]:
return [[single_rotation(cell) for cell in line]
for line in sub]
if __name__ == "__main__":
from sys import stdout
from time import sleep
= get_terminal_size()
width, height = Grid(width//2, height)
G =10, proportion=.3)
G.randomize_grid_circle(radiuswhile True:
0)
G.step(str(G))
stdout.write(0.03)
sleep(1)
G.step(str(G))
stdout.write(0.03) sleep(