Processing #1: Automates cellulaires et algorithmes de Griffeath


La « Vie Artificielle » est une discipline étudiant la création de systèmes artificiels s’inspirant du vivant, notamment sous la forme de programmes informatiques.

Ce champ de recherche alliant biologie et informatique nait dans les années 40, à travers les travaux précurseurs de John von Neumann, qui met au point les premiers types d’automates cellulaires popularisés plus tard par John Conway. Ce dernier met au point dans les années 70 le jeu de la vie, système d’automates cellulaires simples évoluant rapidement en systèmes complexes. Il s’agit en fait d’une matrice de cellules vivantes ou mortes (le plus souvent représentées par un pixel allumé ou éteint) influencées par leurs voisines directes.

Le Jeu de la vie, automate cellulaire par excellence.

Dans les cas les plus simples comme on peut le voir ci dessus, l’évolution d’une cellule est entièrement déterminée par l’état de ses huit voisines suivant deux règles fondamentales:

  • Une cellule morte (pixel éteint) possédant exactement trois voisines vivantes devient vivante (le pixel s’allume).
  • Une cellule vivante possédant deux ou trois voisines vivantes le reste, sinon elle meurt (le pixel s’éteint).

Pourtant, il est également possible de modifier ces règles et complexifier les paramètres d’évolution. Ce fut notamment l’approche utilisée par D.Griffeath, chercheur en mathématique qui s’est consacré à l’étude d’automates cellulaires dérivés du jeu de la vie.
Je me suis moi-même inspiré de cette approche pour étudier et développer via l’environnement de programmation graphique processing différents types d’automates cellulaires.
En me focalisant sur des automates intégrant non plus deux états de cellules (vivante ou morte, allumée ou éteinte) mais de nombreux états associés à différentes couleurs, j’ai pu engendrer des éléments graphiques aux règles et paramètres initiaux simples mais générant rapidement des comportements complexes et imprévisibles. Il s’agit de la notion d’émergence, fondamentale en Vie Artificielle.

Dans la suite, les exemples proposés sont limités en taille pour conserver une certaine fluidité. Libre à vous d’agrandir ces derniers via l’instruction size(hauteur,largeur);.

 


Dans ce premier exemple, les cellules peuvent accéder à quatre états différents, correspondant à des couleurs chaudes, inspirées du cycle ci-dessous:

Variation des états cellulaires.

Une cellule change d’état lorsqu’au moins deux cellules adjacentes possèdent un état identique.

Dans une première phase, les changements d’états sont calculés pour chaque cellule, puis dans une deuxième phase, ces modifications d’états deviennent effectives: les cellules changent de couleurs. Ceci explique l’apparition rapide de zones tâches pour lesquelles les couleurs varient sans cesse au contraire de leurs morphologies, qui restent stables.

Automate cellulaire à quatre états.

Exemple 1

Ce n’est pas le cas des deux exemple suivants dans lesquels chaque cellule voit son changement d’état immédiatement effectif, rendant l’ensemble plus chaotique.

 


Dans ce deuxième exemple, on observe l’apparition quasi immédiate d’un patchwork de couleurs hétérogènes dont les variations cessent au bout de quelques secondes seulement.
Il s’agit d’un automate à onze états, dans lequel chaque cellule verra son état diminuer dès lors qu’elle ne possédera pas au moins deux cellules adjacentes dans un état identique.
Comme nous avons pu le voir, le calcul est légèrement différent du premier exemple puisque les changements d’états sont immédiatement effectifs.

 

Automate cellulaire à onze états.

Exemple 2

 


Le troisième exemple est particulièrement intéressant, puisqu’il permet d’entrevoir une certaine forme de « chaos organisé ». Il s’agit ici d’un automate à onze états dans lequel le changement de couleur sera plus ou moins important en fonction du nombre de cellules adjacentes dans un état similaire.

Malgré son apparente imprévisibilité, il permet la naissance rapide d’ondes similaires à des vagues, qui ne cesseront alors de se mouvoir indéfiniment. On se trouve dans un cas très probant d’émergence de comportements complexes à partir d’un système initial et de règles fondamentalement simples.

Génération aléatoire des états initiaux.

Apparition de vaguelettes et de comportements émergents.

Exemple 3


Il est également possible d’initier un seul et même état pour toutes les cellules au lancement de l’automate. On obtient alors des schémas particuliers avec un passage par des états transitoires instables puis l’apparition de nouveaux comportements émergents qui diffèrent de la propagation d’ondes observées précédemment.

Automate cellulaire possédant un fond uni à l’état initial.

Apparition d’états transitoires instables.

Naissance de comportements émergents.

Exemple 4

Laissez un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *