Концепция клеточного автомата возникла в середине 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. Ниже показано несколько примеров.
Читайте также:
- Введение: 4 новейших операции JavaScript
- Креативное программирование: методы и инструменты для JavaScript, Python и других языков
- Сравнение производительности JS-фреймворков на RealWorld Demo
Читайте нас в Telegram, VK и Яндекс.Дзен
Перевод статьи Chris Webb: One-Dimensional Cellular Automaton in JavaScript
