Jouons avec les automates cellulaires en Javascript

Vous savez tous ce que sont les automates cellulaires, n'est-ce pas ? Bon, pour les cancres et les gens qui ont vécu dans une cave pendant des années, je vous fait un court rappel. Un automate cellulaire est une grille à n dimensions, découpée en cases ou « cellules », chaque cellule pouvant adopter une parmi plusieurs valeurs à un instant t. La vie d'un automate cellulaire est découpée en intervalle de temps distcrt. À chaque itération, la valeur d'une cellule depend de la valeur des cellules environnantes lors de l'itération précédente. C'est clair ?

Le plus célèbre des automates cellulaires est très probablement le Jeu de la vie et ses fascinantes évolutions, mais c'est loin d'être le seul. Aujourd'hui, pour la beauté des yeux et du code, nous nous intéresserons aux automates cellulaires élémentaires.

Ce type d'automate est le plus simple qu'il puisse exister : une seule dimension (une ligne au lieu d'une grille), deux valeurs possibles pour chaque cellule (0 ou 1) et chaque cellule ne dépend que d'elle même et ses deux voisins les plus proches pour ses changements d'états. Pourtant, même avec une telle simplicité, certains automates conservent des propriétés amusantes.

Comprendre les automates cellulaires élémentaires

Chaque cellule dépend de trois cellules (elle-même et ses voisines) pour changer d'état, et il existe deux états possibles pour chaque cellule ; on comprend donc qu'il existe 2³ = 8 états possibles pour une cellule et ses voisines. Une règle associe à chacun de ces états une nouvelle valeur possible (0 ou 1). Cela nous donne donc 2⁸ = 256 règles différentes, quoiqu'en réalité certains automates soient équivalents par simple symétrie.

Chaque automate peut être représenté par un tableau :

État courant	111	110	101	100	011	010	001	000
Nouvel état	1	1	0	0	1	1	0	0

Ici, vous noterez que chaque cellule conserve l'état qu'elle avait à l'itération précédente, indépendamment de ses voisines. Stephen Wolfram a proposé une nomenclature pour les différentes règles : il suffit de convertir l'enchaînement de bits représentant le nouvel état (ici 1, 1, 0, 0, 1, 1, 0, 0) en décimal (ici, 204). La règle 204 est donc celle qui conserve l'identité de l'automate d'une itération à l'autre. Ce n'est certes pas la plus intéressante.

Afin de pouvoir observer les différents effets produits par les multiples règles possibles, chaque ligne est représentée sous la précédente, ce qui fait apparaître de fabuleux motifs 2d (ou pas). Exemple de rendu avec la règle 110 :

rule_110_random

Sur chaque rendu, la première ligne a été génée aléatoirement, et toutes les lignes suivantes ont été générée à partir de la précédente.

Les différents types d'automates

Certaines règles produisent des automates plus ou moins intéressants. On peut assez rapidement se retrouver avec des états stables ou périodiques. Exemple avec la règle 218.

rule_218_random

En revanche, si on fait tourner la même règle sur une ligne ou une seule cellule est activée, le résultat est beaucoup plus sympa.

rule_218_single

D'autres automates produisent des résultats conservant un aspect chaotique et aléatoire sur la durée. Exemples avec les règles 150 et 182 ; hypnotisant, n'est-ce-pas ?

rule_150_random

rule_283_random

Enfin, certains automates présentent des propriétés vraiment particulières. Allez, je vous en présente deux.

Modéliser le traffic avec la règle 184

État courant	111	110	101	100	011	010	001	000
Nouvel état	1	0	1	1	1	0	0	0

Cette règle peut s'interpréter ainsi : si quelque part sur l'automate il existe un 1 suivi d'un 0, le 1 se déplace sur la droite. Si le 1 est suivi d'un autre 1, il reste à sa place. Si on considère que chaque 1 modélise une voiture et chaque 0 une portion libre d'une route, alors on obtient un simulateur extrêmement basique de flux de traffic : si la route est dégagée, la voiture roule ; sinon, elle s'arrête. Sur la capture suivante, on voit bien les vagues de ralentissements provoquées par un traffic chargé.

rule_184_random

La version 2d existe également.

Une machine de turing avec la règle 110

Parmi tous les automates élémentaires, la règle 110 est probablement la plus fascinante. Voici le rendu avec une seule cellule sur la première ligne.

rule_110_single

Et avec une ligne génératrice aléatoire.

rule_110_single

Cette règle présente l'étonnante particularité de générer des schémas en équilibre entre ordre et chaos. Mais surtout, il a été prouvé que la règle 110 est Turing-Complet. C'est à dire que dans des conditions théoriques, il est possible d'utiliser cet automate pour programmer un ordinateur de Turing. Implémenter un interpréteur Python en règle 110 sera laissé en exercice au lecteur.

Nous aussi, on veut jouer

Je suis sûr que vous aussi, vous voulez vous amuser à générer des motifs plus fascinants les uns que les autres. Je suis sympa, je vous colle un bout de javascript pour que vous puissiez vous amuser. Il vous faudra néanmoins un navigateur supportant l'api canvas. N'hésitez pas à tester les quelques règles les plus intéressantes.

Du code ! Du code !

Allez, je suis sympa, je vous montre un peu de code. C'est un blog de développeur, oui ou non ?! On commence par un simple index.html.

<!DOCTYPE html>
<html>
    <head>
        <meta http-equiv="content-type" content="text/html; charset=utf-8" />
        <title>Test Cellular automaton</title>
        <style>
            form#control_form {
                margin-bottom: 1em;
            }
        </style>
    </head>
    <body>
        <form id="control_form">
            <label for="rule_number">Rule :</label>
            <input type="number" min="0" max="255" id="rule_number" value="110" /> <br />

            <label for="mode_random">Random</label>
            <input type="radio" name="mode" id="mode_random" name="random" />

            <label for="mode_single">Single cell</label>
            <input type="radio" name="mode" id="mode_single" name="single" checked="checked" /> <br />

            <input type="submit" id="start_button" name="start" value="Start" />
        </form>
        <canvas id="main_canvas"> </canvas>
        <script type="text/javascript" src="./automaton.js"></script>
        <script type="text/javascript" src="./main.js"></script>
    </body>
</html>

Enchaînons avec automaton.js.

var cellautomaton = (function() {
    "use strict";

    var CellularAutomaton = function(width) {
        this.width = width;
        this.cells = new Array(width);
        this.colors = {
            0: "white",
            1: "blue"
        }
    }

    CellularAutomaton.prototype.setRule = function(rule) {
        this.rule = rule;
    }

    /**
     * Initialize the grid with random values
     */
    CellularAutomaton.prototype.initRandom = function() {
        for (var i = 0 ; i < this.width ; i++) {
            this.cells[i] = Math.floor(Math.random() * 2);
        }
    }

    /**
     * Initialize the grid with a single cell in the middle of the row
     */
    CellularAutomaton.prototype.initSingleCell = function(cell_index) {
        for (var i = 0 ; i < this.width ; i++) {
            this.cells[i] = i == cell_index ? 1 : 0;
        }
    }

    /**
     * Apply the rule to move to the automaton's next step
     */
    CellularAutomaton.prototype.nextStep = function() {
        // The slice() method without argument clones the array
        var nextStep = this.cells.slice();
        for (var i = 0 ; i < this.width ; i++) {
            nextStep[i] = this.getNextStepValue(i);
        }

        this.cells = nextStep;
    }

    /**
     * Get the next step value for given cell index
     */
    CellularAutomaton.prototype.getNextStepValue = function(index) {
        var left_index = index - 1;
        if (left_index < 0) {
            left_index = this.width - 1;
        }

        var right_index = index + 1;
        if (right_index >= this.width) {
            right_index = 0;
        }

        var key = [
            this.cells[left_index],
            this.cells[index],
            this.cells[right_index]
        ].join('');
        return this.rule[key];
    }

    /**
     * Use the canvas API to render the grid
     */
    CellularAutomaton.prototype.drawOn = function(canvas, y) {
        var ctx = canvas.getContext('2d');
        for (var i = 0 ; i < this.width ; i++) {
            ctx.fillStyle = this.colors[this.cells[i]];
            ctx.fillRect(i * 5, y * 5, 5, 5);
        }
    }

    return {
        CellularAutomaton: CellularAutomaton
    }
})();

Et nous terminerons avec main.js.

var WIDTH = 800,
    HEIGHT = 600;

var app = (function(cellautomaton) {
    "use strict";

    var App = function(canvas, nb_cells, nb_rows) {
        this.canvas = canvas;
        this.canvas.width = nb_cells * 5;
        this.canvas.height = nb_rows * 5;
        this.nb_cells = nb_cells;
        this.nb_rows = nb_rows;
        this.automaton = new cellautomaton.CellularAutomaton(nb_cells);
        this.automaton_interval = 0;
    }

    /**
     * Set the cellular automaton evolving rule from it's wolfram code.
     */
    App.prototype.setWolframCode = function(rule_number) {
        var binary = rule_number.toString(2);
        var pad = "00000000";
        var mask = pad.substring(0, pad.length - binary.length) + binary;
        var rule = {
            '000': mask[7],
            '001': mask[6],
            '010': mask[5],
            '011': mask[4],
            '100': mask[3],
            '101': mask[2],
            '110': mask[1],
            '111': mask[0]
        }
        this.automaton.setRule(rule);
    }

    /**
     * Clear the canvas
     */
    App.prototype.clear = function() {
        var ctx = this.canvas.getContext('2d');
        ctx.clearRect(0, 0, this.canvas.width, this.canvas.height);
    }

    /**
     * Start the automaton
     *
     * We will also clear any previously running automaton
     */
    App.prototype.run = function(rule, random_mode) {
        this.clear();
        this.setWolframCode(rule);

        if (random_mode) {
            this.automaton.initRandom();
        } else {
            this.automaton.initSingleCell(parseInt(this.nb_cells / 2));
        }

        var step = 0;
        clearInterval(this.automaton_interval);
        this.automaton_interval = setInterval(function(automaton) {
            automaton.drawOn(canvas, step % this.nb_rows);
            automaton.nextStep();
            step++;
        }, 50, this.automaton);
    }

    return {
        App: App
    }

})(cellautomaton);


var canvas = document.getElementById('main_canvas');
var nb_cells = parseInt(WIDTH / 5);
var nb_rows = parseInt(HEIGHT / 5);
var main_app = new app.App(canvas, nb_cells, nb_rows);

var submitHandler = function(evt) {
    evt.preventDefault();
    var input = document.getElementById('rule_number');

    var mode_random_input = document.getElementById('mode_random');
    var mode_random = mode_random_input.checked;

    var rule = parseInt(input.value);

    main_app.run(rule, mode_random);
}
document.addEventListener('submit', submitHandler);

J'espère que ce petit article de culture générale aura eu l'heur de vous plaîre. Je vous laisse sur ce dernier rendu de la règle 85.

rule_85_random