13,8 тыс подписчиков

Одномерный клеточный автомат в JavaScript

5 минут

78 прочтений

7 января 2021

Концепция клеточного автомата возникла в середине 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, начиная с конструктора.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

_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. Ниже показано несколько примеров.