Un automate cellulaire est un système composé de cellules avec des valeurs numériques dans une grille, ainsi que des règles qui déterminent le comportement de ces cellules. En appliquant à plusieurs reprises la règle à chaque cellule de la grille en parallèle avec la visualisation de la grille, on peut souvent obtenir l'effet d'un certain organisme en évolution avec un comportement complexe et complexe, même si les règles sont relativement simples.
Les automates cellulaires ont différentes formes, types et dimensions. L'automate cellulaire le plus célèbre est probablement le jeu de la vie de Conway (GOL). Il consiste en une grille bidimensionnelle dans laquelle chaque cellule contient une valeur binaire (vivante ou morte). Les règles d'accompagnement, basées sur l'état des cellules voisines, déterminent si la cellule doit être morte ou vivante. Les règles disent qu'une cellule vivante meurt de solitude s'il y a moins de 2 cellules vivantes autour d'elle. Si plus de trois cellules voisines sont vivantes, elle meurt de surpopulation. En d'autres termes, une cellule «survit» s'il y a exactement 2 ou 3 cellules voisines vivantes autour d'elle. Pour qu'une cellule
morte prenne vie, elle doit avoir exactement 3 cellules voisines vivantes, sinon elle reste morte. Un exemple de machine GoL qui parcourt plusieurs états est illustré ci-dessous.
Une autre version célèbre de l'automate cellulaire est unidimensionnelle; il est appelé automate cellulaire élémentaire (ECA). C'est ce que nous mettons en œuvre dans ce post.
Chaque état de cet automate est stocké sous la forme d'un tableau unidimensionnel de valeurs booléennes, et bien que deux dimensions soient nécessaires pour visualiser l'état GOL, un automate de valeurs suffit pour cet automate. Grâce à cela, nous pouvons utiliser deux dimensions (plutôt que l'animation) pour visualiser toute l'histoire des états de cet automate. Comme dans le cas de GOL, l'état de la cellule dans cette machine est 0 ou 1, mais contrairement à la cellule GOL, qui est mise à jour en fonction de ses 8 voisins, la cellule ECA est mise à jour en fonction de l'état du voisin gauche, du voisin droit et de lui-même!
Des exemples de règles sont présentés ci-dessous: les trois cellules supérieures sont l'entrée de la règle, et celle du bas est la sortie, où le noir est 1 et le blanc est 0. En outre, nous pouvons voir les modèles générés par chacun d'eux, lorsque l'état initial est tout 0 sauf 1 dans la cellule du milieu.
Vous vous demandez peut-être: pourquoi les règles présentées ci-dessus sont-elles indiquées par des chiffres? Parce que chaque nombre dans la plage de 0 à 255 correspond directement à la règle ECA, et donc ces nombres sont utilisés comme noms des règles. Cette correspondance est illustrée ci-dessous:
Du nombre à la règleTout nombre compris entre 0 et 255 peut être représenté sous forme binaire avec seulement 8 chiffres (première flèche ci-dessus). De plus, nous pouvons donner à chacun de ces nombres un index basé sur sa localisation (deuxième flèche). Naturellement, ces indices sont compris entre 0 et 7, c'est-à -dire qu'ils peuvent être représentés sous forme binaire en utilisant seulement 3 chiffres (troisième flèche). En interprétant ces 3 chiffres en entrée et le chiffre correspondant du numéro d'origine en sortie, nous obtenons la fonction ternaire dont nous avons besoin (quatrième flèche).
Génération de règles
get_rule l'interprétation ci-dessus en tant que fonction d'ordre supérieur
get_rule qui reçoit un nombre de 0 à 255 en entrée et retourne une règle ECA correspondant à ce nombre.
Nous devons créer quelque chose comme ça:
const rule30 = get_rule(30); const output110 = rule30(1, 1, 0);
Dans l'exemple ci-dessus, la
rule30(1,1,0) départ
rule30(1,1,0) combinera les trois valeurs binaires en un seul nombre (110 = 6) et renverra un bit à cette position (6) en représentation binaire 30. Le nombre 30 en représentation binaire est 00011110, par conséquent, la fonction renverra 0 (nous comptons à droite et commençons le compte à partir de 0).
Sachant que les trois variables d'entrée binaires seront combinées en un seul nombre, commençons par implémenter une telle fonction de
combine .
const combine = (b1, b2, b3) => (b1 << 2) + (b2 << 1) + (b3 << 0);
Après avoir déplacé à gauche les arguments vers les positions correspondantes, puis en additionnant les trois nombres décalés, nous obtenons la combinaison souhaitée.
La deuxième partie importante de la fonction
get_rule consiste à déterminer la valeur de bit à une position spécifique dans un nombre. Par conséquent, créons une fonction
get_bit(num, pos) , qui peut retourner une valeur de bit à une position donnée
pos à un nombre donné
num . Par exemple, le nombre 141 sous forme binaire est 10001101, donc
get_bit(2, 141) devrait retourner
1 , et
get_bit(5, 141) devrait retourner
0 .
La fonction
get_bit(num,pos) peut être implémentée en effectuant d'abord un décalage binaire du nombre par
pos vers la droite, puis en effectuant l'opération au niveau du bit "ET" avec le nombre 1.
const get_bit = (num, pos) => (num >> pos) & 1;
Il ne nous reste plus qu'Ă combiner ces deux fonctions:
const get_rule = num => (b1, b2, b3) => get_bit(num, combine(b1, b2, b3));
Super! Donc, nous avons une fonction qui, pour chaque nombre dans notre intervalle, nous donne une règle ECA unique avec laquelle nous pouvons faire n'importe quoi. L'étape suivante consiste à les rendre dans le navigateur.
Visualisation des règles
Pour rendre les automates dans le navigateur, nous utiliserons l'élément
canvas . L'
canvas peut être créé et ajouté au corps html comme suit:
window.onload = function() { const canvas = document.createElement('canvas'); canvas.width = 800; canvas.height = 800; document.body.appendChild(canvas); };
Pour pouvoir interagir avec le
canvas , nous avons besoin de
contexte . Le contexte nous permet de dessiner des formes et des lignes, de coloriser des objets et généralement de naviguer dans le
canvas . Il nous est fourni via la méthode
getContext de notre
canvas .
const context = canvas.getContext('2d');
Le paramètre
'2d' fait référence au type de contexte que nous utiliserons dans cet exemple.
Ensuite, nous allons créer une fonction qui, ayant le contexte, la règle ECA, ainsi que quelques informations sur l'échelle et le nombre de cellules, dessine la règle sur le
canvas . L'idée est de générer et dessiner une grille ligne par ligne; La partie principale du code ressemble à ceci:
function draw_rule(ctx, rule, scale, width, height) { let row = initial_row(width); for (let i = 0; i < height; i++) { draw_row(ctx, row, scale); row = next_row(row, rule); } }
Nous commençons avec une sorte d'ensemble initial de cellules, qui est la ligne actuelle. Cette ligne, comme dans les exemples ci-dessus, contient généralement tous les zéros, à l'exception d'une unité dans la cellule du milieu, mais elle peut également contenir une ligne complètement aléatoire de 1 et 0. Nous dessinons cette ligne de cellules, puis utilisons la règle pour calculer la ligne de valeurs suivante en fonction de ligne actuelle. Ensuite, nous répétons simplement le dessin et calculons les nouvelles étapes jusqu'à ce que nous trouvions que la grille est suffisamment haute.
Pour l'extrait de code ci-dessus, nous devons implémenter trois fonctions:
initial_row ,
draw_row et
next_row .
initial_row est une fonction simple. Il crée un tableau de zéros et modifie l'élément au centre du tableau par un.
function initial_row(length) { const initial_row = Array(length).fill(0); initial_row[Math.floor(length / 2)] = 1; return initial_row; }
Comme nous avons déjà une fonction de règle, la fonction
next_row peut être composée d'une seule ligne. La valeur de chaque cellule d'une nouvelle ligne est le résultat de l'application de la règle avec les valeurs des cellules les plus proches, et l'ancienne ligne est utilisée comme entrée.
const next_row = (row, rule) => row.map((_, i) => rule(row[i - 1], row[i], row[i + 1]));
Avez-vous remarqué que nous avons triché sur cette ligne? Chaque cellule d'une nouvelle ligne nécessite l'entrée de trois autres cellules, mais deux cellules situées aux bords de la ligne reçoivent des données de seulement deux. Par exemple,
next_row[0] essaie d'obtenir la valeur d'
next_row[0] de la
row[-1] . Cela fonctionne toujours, car lorsque vous essayez d'accéder à des valeurs par des index qui ne sont pas dans le tableau, javascript renvoie
undefined , et il arrive que
(undefined >> [ ]) (Ă partir de la fonction
combine ) renvoie toujours 0. Cela signifie qu'en réalité, nous traitons chaque valeur en dehors du tableau comme 0.
Je sais que c'est moche, mais bientôt nous allons créer quelque chose de beau à l'écran, pour qu'on puisse nous pardonner.
Vient ensuite la fonction
draw_row ; c'est elle qui fait le rendu!
function draw_row(ctx, row, scale) { ctx.save(); row.forEach(cell => { ctx.fillStyle = cell === 1 ? '#000' : '#fff'; ctx.fillRect(0, 0, scale, scale); ctx.translate(scale, 0); }); ctx.restore(); ctx.translate(0, scale); }
C'est ici que nous sommes très dépendants de l'objet contextuel, en utilisant au moins 5 méthodes différentes de celui-ci. Voici une brève liste et comment les utiliser.
fillStyle indique comment nous voulons remplir les formes. Il peut s'agir d'une couleur, par exemple, "#f55" , ainsi que d'un dégradé ou d'un motif. Nous utilisons cette méthode pour séparer visuellement les cellules 0 des cellules 1.fillRect(x, y, w, h) dessine un rectangle à partir d'un point (x, y) de largeur w et de hauteur h, rempli selon fillStyle . Nos rectangles sont de simples carrés, mais vous serez peut-être surpris que le point de départ de chacun d'eux soit à l'origine. Cela est arrivé parce que nous utilisons cette méthode en combinaison avec translate .translate(x, y) vous permet de déplacer l'ensemble du système de coordonnées. La position est enregistrée, la méthode est donc une excellente alternative au suivi de différentes positions d'éléments. Par exemple, au lieu de calculer la position de chaque cellule de grille individuelle, nous pouvons simplement dessiner une cellule, déplacer vers la droite, dessiner une nouvelle cellule, etc.save() et restore() sont utilisés conjointement avec translate et d'autres méthodes de conversion de coordonnées. Nous les utilisons pour enregistrer le système de coordonnées actuel à un certain point, afin que nous puissions y revenir plus tard (en utilisant la restauration ). Dans ce cas, nous enregistrons le système de coordonnées avant de rendre la ligne et la déplaçons vers la droite. Ensuite, lorsque nous avons fini de dessiner la ligne et que nous sommes allés complètement à droite, les coordonnées sont restaurées et nous revenons à l'état d'origine. Ensuite, nous descendons pour nous préparer à tracer la ligne suivante.
Nous avons maintenant toutes les pièces nécessaires à la fonction
draw_rule . Nous utilisons cette fonction dans
window.onload après avoir préparé le
canvas . Nous déterminerons également les paramètres dont nous avons besoin.
window.onload = function() { const width = 1000;
Nous extrayons les dimensions du
canvas tant que variables distinctes avec le nombre de cellules horizontalement. Ensuite, nous calculons
cell_scale et 'cells_down' afin que la grille remplisse tout le
canvas , tandis que les cellules restent carrées. Grâce à cela, nous pouvons facilement changer la "résolution" de la grille, en restant dans le
canvas .
C'est tout! L'exemple de code complet se trouve sur
github et sur
codepen :
Aller de l'avant
Grâce à ce système, nous pourrons examiner les 256 règles l'une après l'autre, soit de manière itérative, en changeant le code, soit en choisissant un numéro de règle au hasard à chaque chargement de page. Quoi qu'il en soit, il est très excitant d'étudier tous ces résultats imprévisibles dans notre environnement contrôlé.
Vous pouvez également rendre l'état initial des cellules de l'automate aléatoire au lieu des «zéros solides et une unité» statiques. Nous obtenons donc des résultats encore plus imprévisibles. Cette version de la fonction
initial_row peut ĂŞtre Ă©crite comme ceci:
function random_initial_row(width) { return Array.from(Array(width), _ => Math.floor(Math.random() * 2)); }
Ci-dessous, vous voyez Ă quel point ce changement de ligne de sortie a un grand impact sur la sortie.
Chaîne source aléatoireEt ce n'est qu'un aspect que vous pouvez changer! Pourquoi vous limiter à seulement deux conditions? (La transition de 2 à 3 états fait passer le nombre de règles de 256 à 7 625 597 484 987!) Pourquoi se limiter aux carrés? Pourquoi seulement 2 dimensions? Pourquoi une seule règle à la fois?
Des exemples de visualisations basées sur ECA sont présentés ci-dessous, mais avec une fonction alternative
draw_rule qui
draw_rule lignes non pas avec des carrés, mais avec un motif isométrique, puis remplit les zones définies par ces lignes avec des couleurs. Vous n'avez même pas besoin d'afficher les lignes de séparation et d'afficher uniquement les couleurs.
Si vous allez encore plus loin, vous pouvez ajouter des symétries, à la fois axiales (rangée du milieu) et miroir (rangée du bas).
Si ces visualisations vous ont semblé intéressantes, mais étudiez
ce bac à sable interactif , ou mieux encore, commencez par le code que nous avons créé et essayez de créer vos propres automates cellulaires!
Bonne chance