Концепция клеточного автомата возникла в середине 20 века, и с того времени область ее практического и теоретического применения значительно расширилась. 

Клеточный автомат состоит из любого числа ячеек, упорядоченных в 1, 2, 3 или более измерениях. С каждой из них связано какое-либо состояние, простейшее из которых  —  “on” (включено) или “off” (выключено). Каждая ячейка, а следовательно и весь автомат, со временем переходит из одного состояния в другое в соответствии с одним или несколькими правилами.

Число измерений, возможных состояний ячеек и правил может быть произвольно большим и сложным, но в рамках этого проекта мы реализуем простейший или элементарный одномерный клеточный автомат. 

Элементарный клеточный автомат 

Такой автомат состоит из ряда ячеек, каждая из которых может находиться в состоянии “on” или “off”, отображенных в нижеприведенной таблице как 0 и 1.  

При расчете последующего состояния ячеек, учитывается тот факт, что каждая отдельная ячейка имеет окрестность, охватывающую саму ячейку и по одному её соседу с каждой стороны. Одной частью окрестности крайней ячейки является ячейка с другого конца, поэтому клеточный автомат можно считать логично циклическим. В следующей таблице показаны окрестности двух ячеек, выделенные жирным шрифтом. 

Существует 8 возможных окрестностей, в связи с чем правила для установки следующего состояния ячейки можно выразить в байте. Десятичные значения 0-255 представлены всеми возможными байтами  —  это форма известна как код Вольфрама, названная в честь Стивена Вольфрама, который занимался исследованиями в этой научной области и написал книгу “Новый вид науки”. 

Ниже представлен код Вольфрама для правила 30, в котором биты второго ряда образуют 30 в двоичном формате. 

Как правило, состояния одномерного клеточного автомата представлены во времени последовательно сменяющими друг друга рядами, в которых состояния обозначаются группами ячеек разного цвета. В этом проекте мы напишем реализацию на основе HTML/JavaScript. Ниже приводится скриншот образца, выполняемого с применением правила 109. Создаваемые шаблоны  —  один интереснее другого.

Проект состоит из следующих файлов, включая файлы CSS и графику, которые вы можете скопировать/загрузить из репозитория на Github:

  • ca1d.js — реализует сам клеточный автомат;
  • ca1dsvg.js — выводит клеточный автомат из ca1d.js в виде HTML-страницы; 
  • ca1d.htm — содержит клеточный автомат, его вывод и элементы управления;
  • ca1dpage.js — вспомогательный код для ca1d.htm. 

Сначала обратим внимание на ca1d.js, который реализует клеточный автомат как класс ES6/ES2015, начиная с конструктора. 

class CellularAutomaton1D
{
    constructor()
    {
        this._CurrentState = [];
        this._NextState = [];
        this._NumberOfCells = 32;
        this._Rule = 0;
        this._StateChangedEventHandlers = [];
        this._NumberOfCellsChangedEventHandlers = [];
    }

Здесь ничего особенного не происходит! Мы всего лишь создаем несколько вспомогательных переменных для свойств. 

//---------------------------------------------------
    // СВОЙСТВА
    //---------------------------------------------------

    get StateChangedEventHandlers() { return this._StateChangedEventHandlers; }

    get NumberOfCellsChangedEventHandlers() { return this._NumberOfCellsChangedEventHandlers; }

    get CurrentState() { return this._CurrentState; }

    get NextState() { return this._NextState; }

    get Rule() { return this._Rule; }
    set Rule(Rule) { this._Rule = Rule; }

    get NumberOfCells() { return this._NumberOfCells; }
    set NumberOfCells(NumberOfCells)
    {
        this._NumberOfCells = NumberOfCells;
        this.FireNumberOfCellsChangedEvent();
    }

Первые два свойства являются массивами, изначально пустыми. К ним можно добавить функции, вызов которых происходит при изменении текущего состояния или числа клеток. Благодаря этому любой код, ответственный за прорисовку клеточного автомата, может содержать ссылку на объект и добавлять к нему обработчики событий. Затем эти обработчики делают все необходимое для наглядного отображения вывода автомата. Таким образом, клеточный автомат и его визуальный вывод полностью отделяются. В этом проекте мы будем использовать класс CellularAutomaton1DSVG, но вы можете написать собственную реализацию без изменений класса CellularAutomaton1D

Далее у нас появляются еще несколько свойств. Обратите внимание, что последнее из них, а именно NumberOfCells, запускает соответствующее событие, в следствие чего любой подключенный UI знает, что нужно себя обновить. 

//-------------------------------------------------------------------
    // МЕТОДЫ
    //-------------------------------------------------------------------

    FireStateChangedEvent()
    {
        this._StateChangedEventHandlers.every(function (Handler) { Handler(); });
    }

    FireNumberOfCellsChangedEvent()
    {
        this._NumberOfCellsChangedEventHandlers.every(function (Handler) { Handler(); });
    }

    Randomize()
    {
        for (let i = 0; i < this._NumberOfCells; i++)
        {
            this._CurrentState[i] = parseInt(Math.random() * 2);
        }

        this.FireStateChangedEvent();
    }

    InitializeToCentre()
    {
        for (let i = 0; i < this._NumberOfCells; i++)
        {
            this._CurrentState[i] = 0;
        }

        this._CurrentState[Math.floor(this._NumberOfCells / 2)] = 1;

        this.FireStateChangedEvent();
    }

    CalculateNextState()
    {
        let PrevIndex;
        let NextIndex;
        let Neighbourhood;
        let RuleAsBinary = this._Rule.toString(2);

        // дополняем двоичное значение до 8
        while (RuleAsBinary.length < 8)
            RuleAsBinary = "0" + RuleAsBinary;

        for (let i = 0; i < this._NumberOfCells; i++)
        {
            if (i == 0)
                PrevIndex = this._NumberOfCells - 1;
            else
                PrevIndex = i - 1;

            if (i == (this._NumberOfCells - 1))
                NextIndex = 0;
            else
                NextIndex = i + 1;

            Neighbourhood = this._CurrentState[PrevIndex].toString() + this._CurrentState[i].toString() + this._CurrentState[NextIndex].toString();

            switch (Neighbourhood)
            {
                case "111":
                    this._NextState[i] = RuleAsBinary[0];
                    break;
                case "110":
                    this._NextState[i] = RuleAsBinary[1];
                    break;
                case "101":
                    this._NextState[i] = RuleAsBinary[2];
                    break;
                case "100":
                    this._NextState[i] = RuleAsBinary[3];
                    break;
                case "011":
                    this._NextState[i] = RuleAsBinary[4];
                    break;
                case "010":
                    this._NextState[i] = RuleAsBinary[5];
                    break;
                case "001":
                    this._NextState[i] = RuleAsBinary[6];
                    break;
                case "000":
                    this._NextState[i] = RuleAsBinary[7];
                    break;
            }
        }

        for (let i = 0; i < this._NumberOfCells; i++)
        {
            this._CurrentState[i] = this._NextState[i];
        }

        this._NextState.length = 0;

        this.FireStateChangedEvent();
    }

    Iterate(Iterations)
    {
        for(let Iteration = 1; Iteration <= Iterations; Iteration++)
        {
            this.CalculateNextState();
        }
    }
}

Первые два метода вызывают все функции в массивах _StateChangedEventHandlers и _NumberOfCellsChangedEventHandlers. Как правило, они представлены только по одному, но при желании вы можете добавить и больше. 

Далее следует метод Randomize. Он устанавливает каждую ячейку в состояние 0 или 1 в случайном порядке с равной степенью вероятности.  

Метод InitializeToCentre устанавливает все ячейки в состояние 0, за исключением одной центральной, которой задается значение 1. 

Метод CalculateNextState наиболее сложный и располагается в самом сердце класса. Прежде всего нам потребуется правило в виде двоичного числа, преобразованного в строку и дополненного до 8 бит. Например, правило 30 трансформируется в “00011110”.

Далее мы перебираем ячейки, сначала получая индексы предыдущей и последующей, а также позволяя первой и последней ячейкам возвращаться к противоположному концу. После этого мы можем установить значения окрестности с 3 ячейками в виде строки. 

Внутри блока switch мы задаем правильное значение для соответствующей ячейки в массиве. Следующее состояние необходимо установить в отдельном массиве, иначе в расчете очередного значения нужной ячейки будут допущены ошибки. После цикла потребуется лишь скопировать новое состояние в текущее и запустить соответствующее событие. 

Последний метод Iterate просто повторяет заданное число итераций в аргументе функции, каждый раз вызывая CalculateNextState.

Теперь можно переходить к коду, отображающему клеточный автомат, а также класс. 

class CellularAutomaton1DSVG
{
    constructor(SVGID, CA)
    {
        this._SVGID = SVGID;
        this._CA = CA;
        this._Iteration = 0;

        this._CellSize = 16;
        this._CellZeroColor = "#FFFFFF";
        this._CellOneColor = "#000000";

        let that = this;

        this._CA.StateChangedEventHandlers.push(function()
        {
            that._SetHeight(that._CellSize * that._Iteration);
            that._DrawState();
        });

        this._CA.NumberOfCellsChangedEventHandlers.push(function()
        {
            that._SetWidth(that._CellSize * that._CA.NumberOfCells);
        });

        this._SetHeight(this._CellSize * this._Iteration);
        this._SetWidth(this._CellSize * this._CA.NumberOfCells);
    }

Создав несколько вспомогательных переменных для различных свойств, мы устанавливаем пару обработчиков событий класса CellularAutomaton1D. Для изменения состояния нам потребуется вызвать функции, увеличивающие высоту SVG, с целью размещения дополнительного ряда и его последующей отрисовки. Для изменения числа ячеек мы должны скорректировать ширину, тем самым выделив под них дополнительное пространство. 

На финальном этапе необходимо вызвать функции для установки исходной ширины и высоты элемента SVG. 

//---------------------------------------------------
    // СВОЙСТВА
    //---------------------------------------------------

    get CellSize() { return this._CellSize; }
    set CellSize(CellSize) { this._CellSize = CellSize; }

    get CellZeroColor() { return this._CellZeroColor; }
    set CellZeroColor(CellZeroColor) { this._CellZeroColor = CellZeroColor; }

    get CellOneColor() { return this._CellOneColor; }
    set CellOneColor(CellOneColor) { this._CellOneColor = CellOneColor; }

Здесь ничего интересного не происходит — лишь несколько геттеров и сеттеров. 

//---------------------------------------------------
    // МЕТОДЫ
    //---------------------------------------------------

    _DrawState()
    {
        for (let i = 0, m = this._CA.NumberOfCells; i < m; i++)
        {
            let rect = document.createElementNS("http://www.w3.org/2000/svg", 'rect');

            rect.setAttributeNS(null, 'x', i * this._CellSize);
            rect.setAttributeNS(null, 'y', this._Iteration * this._CellSize);
            rect.setAttributeNS(null, 'height', this._CellSize);
            rect.setAttributeNS(null, 'width', this._CellSize);

            if (this._CA.CurrentState[i] == 0)
            {
                rect.setAttributeNS(null, 'style', "fill:" + this._CellZeroColor + "; stroke:" + this._CellOneColor + "; stroke-width:" + 0.25 + ";");
            }
            else
            {
                rect.setAttributeNS(null, 'style', "fill:" + this._CellOneColor + "; stroke:" + this._CellZeroColor + "; stroke-width:" + 0.25 + ";");
            }

            document.getElementById(this._SVGID).appendChild(rect);
        }

        this._Iteration++;

        this._SetHeight(this._CellSize * this._Iteration);
    }

    _SetHeight(height)
    {
        document.getElementById(this._SVGID).setAttribute("height", height);
    }

    _SetWidth(width)
    {
        document.getElementById(this._SVGID).setAttribute("width", width);
    }

    Clear()
    {
        document.getElementById(this._SVGID).innerHTML = "";

        this._Iteration = 0;

        this._SetHeight(0);
    }
}

_DrawState

Эта функция создает новый элемент для каждой ячейки, устанавливает ее размер, положение, цвет и добавляет ее к элементу SVG. Ее окончательная цель — добавить новый ряд ячеек в нижнюю часть экрана. 

_SetHeight and _SetWidth

Эти весьма небольшие функции устанавливают соответствующие атрибуты элемента SVG.

Clear

Она удаляет все составляющие SVG элемента, сбрасывает итерацию и доводит величину SVG до 0, успешно его скрывая. 

ca1d.htm

Здесь не указан HTML-код для страницы, но он включен в zip репозиторий на Github. Он просто содержит средства управления и элемент SVG, представленный на последующих скриншотах. 

ca1dpage.js

Здесь также отсутствует код, но он создает экземпляры классов CellularAutomaton1D иCellularAutomaton1DSVG, а еще устанавливает свойства или вызывает методы в различных обработчиках событий элементов управления. 

Откройте ca1d.htm в браузере, задайте правило, кликните сначала по кнопке Initialize to Centre, а затем по Run. Ниже показано несколько примеров. 

Правило 22
Правило 122
Правило 158

Читайте также:

Читайте нас в Telegram, VK и Яндекс.Дзен


Перевод статьи Chris Webb: One-Dimensional Cellular Automaton in JavaScript