Automates cellulaires 1D

Partie 1: Automates bicolores

Il s'agit de simuler l'évolution d'une colonie de cellules à une dimension,au cours du temps

Une cellule a deux états: soit elle est vivante ce qui est représenté par le nombre 1 et la couleur noire à l'écran

Soit elle n'existe pas ce qui représenté par le nombre 0 et la couleur blanche

A un instant t la colonie est représenté par un tableau de taille égale au nombre de cellules ici 300

A l'instant initial on va supposer qu'il y a une seule cellule vivante située au centre du tableau t

Pour passer d'un état au suivant voici comment on procède

1. On regarde pour chaque cellule t[i] le voisin de gauche t[i-1] et le voisin de droite t[i+1] et on forme un nombre binaire ainsi t[i-1]t[i]t[i+1]

   Ce nombre est compris entre 000 et 111 = 7. Pour chacun de ces nombres on définie une règle d'évolution par la donnée de soit 0 soit 1. IL existe donc 256 règles d'évolution possibles

   Autrement dit une règle est définie par un octet

2. Par exemple la règle 110 est nommée ainsi car 110 en binaire correspond à l'octet 01101110 visualisé par

   

   Cependant cet octet est mémorisé par un tableau octet = [0,1,1,1,0,1,1,0]

3. Pour engendrer l'état suivant de la colonie, dans un nouveau tableau t', on parcourt le tableau t associé à la colonie et chaque triplet (t[i-1],t[i],t[i+1]) donne un indice j tel que l'état suivant de la cellule en i sera octet[j]

   Autrement dit t'[i] = octet[j]

   Une fois t' rempli on le visualise juste en dessous de t

   

4. Ensuite t prend la valeur de t' et on répète le processus plusieurs fois

   Par exemple ci-dessous il y a 15 générations

   

Travail à faire

1. Le squelette du code est à télécharger ici
2. Compléter et tester les fonctions dec_to_bin et indice
3. Compléter et tester les fonctions communes aux automates bicolores et tricolores, initialisation, etat_suivant, generation_suivante et evolution

4. Dans le main tester la règle 110

   Lire les pages 54 à 59 de ce document et tester les automates visualisées dans ce document.

Partie 2: Automates tricolores

Maintenant une cellule peut avoir trois états numérotés 0,1 ou 2

Au nombre 2 est associée la couleur noire et au nombre 1, la couleur grise

Par contre l'état futur d'une cellule dépend de la somme des états des deux voisins et de la cellule elle même, donc au minimum c'est 0 au maximum c'est 6

Donc pour définir une règle d'évolution on va créer un tableau de longueur 7, d'indice 0 (pour la somme = 0) jusqu'à l'indice 6 ( pour la somme = 6)

A chaque cellule de ce tableau on peut associer l'une des trois valeurs 0, 1 ou 2

Autrement dit une règle d'évolution est un nombre sur 7 bits écrit en base 3

Il y a $3^7 = 2187$ règles possibles

Une règle sera donc caractérisée par un nombre entier entre 0 et 2186, qu'il faudra écrire en base 3 dans un tableau de taille 7

Travail à faire

1. Compléter et tester les fonctions dec_to_tri et indice_tri
2. Visualiser les automates tricolores ci-dessous avec votre programme