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

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

Одномерный клеточный автомат представляет собой линейный набор ячеек, т.е по сути дела простой одномерный массив. В этом наборе ячеек каждая из них в конкретный момент времени может иметь одно состояние из некоторого заранее фиксированного их множества. Для одномерного клеточного автомата, задается некоторое правило, которое берет текущую ячейку, а также двух ее соседей — слева и справа, и на основании состояний этих трех ячеек вычисляется состояние текущей ячейки, после чего происходит переход к следующей. В таком клеточном автомате используется замкнутое одномерное пространство, т.е для того, чтобы у каждой клетки было два соседа, начальная клетка «смыкается» с последней. Иными словами, у начальное клетки все равно два соседа — клетка которая справа, а также самая последняя клетка.

Также, хочется заметить, что здесь как и в случае двумерных клеточных автоматов, здесь также есть кванты времени, в течении которых обновляется все состоянии автомата.

Однако, есть ряд особенностей, про которые мы расскажем ниже.

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

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

Вот именно про них мы и будем вести речь дальше.

Элементарные клеточные автоматы — это такие одномерные автоматы, у которых есть только два состояния — 0 и 1. Для задания правил в таком автомате есть особый принцип, который называется кодом Вольфрама (по фамилии ученого Стивена Вольфрама, который придумал классификацию таких автоматов на основе таких правил). Код Вольфрама представляет собой 8-битное двоичное число, которое показывает, какое состояние примет текущая клетка в следующий момент на основании своего собственного состояния, а также состояния двух своих соседей. Выглядит это следующим образом: представим, что мы берем три клетки (сосед слева — текущая клетка — сосед справа) и записываем их состояния в виде трехбитного двоичного числа. К примеру, запись 011 — означает, что текущая клетка имеет состояние 1, сосед слева — состояние 0, а сосед справа — состояние 1. Запишем все возможные состояния клеток начиная с самого «заполненного» — 111 и заканчивая самым «пустым» — 000 в один список, тогда список будет содержать всего 8 позиций, которые соответствуют десятичным числам от 7 до 0. Запомним этот факт, он еще потребуется далее.

Сопоставим каждому такому числу, а по сути — состоянию текущей клетки, новое состояние и запишем это в виде следующей таблички: (числа взяты для примера)

И если сопоставлять таким образом состояния трех клеток новому состоянию текущей, то мы и получаем правило клеточного автомата. Поскольку, вторая строка таблицы кодирует правило в виде 8-битного числа, то число которое образуется после перевода двоичного представления 8-битного числа в десятичное и является отличительным признаком правила, и правила различают именно по номерам. Правил всего 256 и не все из них интересны, а некоторые, как, к примеру, правило в представленной табличке (которое называется правилом 30) имеют ряд нетривиальных и необычных свойств в своей эволюции во времени.

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

class WolframRule(ubyte rule, int size)
{
	private {
		ubyte[size] _prev, _next;
	}
	
	this() {
		
	}
	
	void run()
	{		
		_prev = _next;
		
		for (int i = 0; i < size; i++)
		{
			int left = (i - 1) <= 0 ? size - 1 : (i - 1); 
			int right = (i + 1) >= size ? 0 : (i + 1); 
			
			auto stateOf()
			{
				return  (_prev[left] << 2) +  (_prev[i] << 1) + _prev[right];
			}
			
			auto state = stateOf;
			_next[i] =  (rule & (0x01 << state)) >> state;  
		}
	}
	
	auto get()
	{
		return _next;
	}
	
	alias _next this;
}

Данный класс имеет два шаблонных параметра — номер правила, а также размер одномерного клеточного автомата (в клетках). При создании экземпляра класса достаточно указать два этих параметра и использовать пустой конструктор класса. Класс имеет два метода — get и run, которые используются для того, чтобы извлечь все текущее состояние автомата (представлено одномерным массивом фиксированной длины) и чтобы вычислить новое состояние для всех клеток в автомате. Обратите внимание, здесь нет метода set, однако, для того, чтобы задать нужное состояние для клетки можно использовать привычный синтаксис для задания элемента одномерного массива, поскольку внутри класса объявлен alias this на массив с текущим состоянием (так называемый subtyping).

Самое интересное происходит в методе run: в классе есть два массива — _prev (предыдущее состояние автомата) и _next (текущее состояние автомата) и в методе сначала происходит копирование предыдущего состояния в текущее, после чего для каждой клетки автомата происходит вычисление ее состояния в цикле. И здесь есть два интересных момента:

• функция stateOf, которая формирует трехбитное число (в десятичном представлении) из текущей клетки и ее соседей с помощью перевода двоичного числа в десятичное (стандартный способ перевода из одной системы счисления в другую, но умножения на степени 2 выполнены на сдвигах);
• способ вычисления текущего состояния: используются также побитовые операции, которые здесь выделяют из правила, заданного 8-битным числом, следующее состояние, на номер которого указывает результат вычисления функции stateOf (проще говоря, таким нестандартным образом реализовано сопоставление состояний трех клеток со следующим состоянием).

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

Создадим простой пример, который будем собирать с помощью dub:

#!/usr/bin/env dub
/+ dub.sdl:
	dependency "ppmformats" version="~>0.0.6"
+/


import std.stdio;

import ppmformats;

class WolframRule(ubyte rule, int size)
{
	private {
		ubyte[size] _prev, _next;
	}
	
	this() {
		
	}
	
	void run()
	{		
		_prev = _next;
		
		for (int i = 0; i < size; i++)
		{
			int left = (i - 1) <= 0 ? size - 1 : (i - 1); 
			int right = (i + 1) >= size ? 0 : (i + 1); 
			
			auto stateOf()
			{
				return  (_prev[left] << 2) +  (_prev[i] << 1) + _prev[right];
			}
			
			auto state = stateOf;
			_next[i] =  (rule & (0x01 << state)) >> state;  
		}
	}
	
	auto get()
	{
		return _next;
	}
	
	alias _next this;
}



void main()
{
	enum int SIZE = 500;
	alias Rule184 = WolframRule!(184, SIZE);
	alias Rule110 = WolframRule!(110, SIZE);
	alias Rule30 =  WolframRule!(30, SIZE);
	
	
	auto state = new Rule30;
	state[SIZE - 1] = 1;
	
	auto img = new P6Image(500, SIZE, new RGBColor(255, 255, 255));
	
	foreach (i; 0..img.height)
	{
		auto w = state.get;
		
		foreach (j; 0..img.width)
		{
			if (w[j] == 1)
			{
				img[j, i] = new RGBColor(0, 0, 0);
			}
		}
		
		state.run;
	}
	
	img.save(`rule.ppm`);
}

Результат выглядит примерно так:

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

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

• Правило 30
• Элементарные клеточные автоматы
• A New Kind of Science, книга о клеточных автоматах и не только, Стивена Вольфрама