Искусственная жизнь клеточных автоматов

Наблюдая за любыми проявлениями жизни, легко заметить нечто такое, что отличает их от неживых объектов. В чем же разница? Почему поведение живого так разительно внешне отличается от всякого иного механического движения в неживой природе? Раскрыть или, по крайней мере, пролить свет на общие принципы, управляющие поведением живых объектов, удалось английскому математику Дж. Конвэю. Он придумал очень простую игру, которую так и назвал - "Жизнь". Напомним, что суть дела заключается в следующем. На бесконечном клеточном поле обитает популяция фишек. Каждая клеточка поля может быть либо заселена фишкой, либо пуста. Моменты времени в игре сменяют друг друга дискретно - 1, 2, 3... В пустой клетке рождается новая фишка, если в предыдущий момент времени в окрестных восьми клетках обитало ровно три живых ее собрата. Фишка, вокруг которой обитало меньше двух или больше трех фишек, в следующий момент времени умирает, а занятая ею клетка освобождается.

Если изначально разбросать на клеточном поле некоторое количество фишек, а затем дать возможность исходной популяции развиваться по описанным простым правилам, то можно будет наблюдать те особые процессы характерного "копошения", свойственные только живым системам. Именно поэтому игра и получила свое название - "Жизнь". Сразу с момента своего возникновения "Жизнь" завоевала бешеную популярность во всем мире. Множество программистов разрабатывало свои оригинальные версии игры. Стали выпускаться даже специализированные журналы.

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

В игре "Жизнь" каждая из клеток может находиться лишь в одном из двух возможных дискретных состояний. А что если попытаться придумать игру, в которой каждая из клеток могла бы принимать не два значения (ноль и единица), а вмещала бы любое действительное число между ними (то есть, например, могла быть заселенной на 0.81 или на 0.38). Пусть имеется некая клеточная поверхность. Состояние каждой из клеток этой поверхности характеризуется действительным числом "x", находящимся в интервале от 0 до 1. Число "x" можно интерпретировать как степень заселенности клетки. Тогда клетка, содержащая значение 0, пуста; клетка, содержащая значение 0.2, заполнена на 20% и т. д. Затем предположим, что в следующий момент времени, которое изменяется в игре дискретными тактами, степень заселенности клетки определяется состоянием ее ближайшей окрестности, т.е. средней заселенностью соседних восьми клеток. Среднюю заселенность окрестности будем определять как деленную на 8 сумму заселенностей соседних восьми ячеек. Предположим, что наиболее оптимальные условия для клетки создаются, когда средняя заселенность ее окрестности находится примерно на уровне 0.5. Тогда ячейке не слишком тесно и не слишком одиноко. Математически это может быть выражено следующей формулой:

Xk+1=4xYkx(1-Yk),

 

где Xk+1 - заселенность некоторой клетки в k+1 момент времени, Yk - средняя заселенность окрестности данной клетки в k-тый момент времени. График зависимости заселенности клетки в следующий момент времени от средней заселенности ее окрестности в текущий момент времени будет иметь вид параболы с вершиной в точке с координатами (0.5, 1). То есть, наиболее комфортные условия для клетки создаются, когда ее окрестность в момент времени k заселена в среднем наполовину. Для того, чтобы не ломать себе голову над тем, как трансформировать правила игры и алгоритмы расчетов на границах игрового поля (т.к. смоделировать бесконечное клеточное поле на компьютере с пусть даже очень большой, но все же ограниченной памятью не представляется возможным), целесообразно свернуть его в тор (тором математики называют фигуру в форме бублика). Тогда клеточная поверхность не будет иметь краев, но будет ограничена по площади. Для этого двумерные массивы, в которых будут сохраняться предыдущая и последующая конфигурации, необходимо описать (во все стороны) на единичку больше, чем выбранный размер игрового поля, оставив тем самым поля для "склейки". Если Вы выбрали размер игрового поля (1..200, 1..200), то массивы следует описать так:

Dim x (0 to 201, 0 to 201) As Single
Dim y (0 to 201, 0 to 201) As Single

Затем для "сворачивания" клеточного поля, которое следует производить перед расчетом конфигурации каждого очередного поколения, значения крайних клеток необходимо скопировать в поля для "склейки".

x(0, 0) = x(n, n): x(0, n + 1) = x(n, 1)
x(n + 1, 0) = x(1, n): x(n + 1, n + 1) = x(1, 1)
For k = 1 To n
 x(0, k) = x(n, k): x(k, 0) = x(k, n)
 x(n + 1, k) = x(1, k): x(k, n + 1) = x(k, 1)
Next k

Для расчета следующей конфигурации ячеек на игровом поле можно использовать вложенный цикл:

For i = 1 To n
 For j = 1 To n
 s = x(i + 1, j) + x(i, j + 1) + x(i, j - 1) + x(i + 1, j + 1)+
 x(i + 1, j - 1) + x(i - 1, j) + x(i - 1, j + 1) + x(i - 1, j - 1)
 s = s / 8
 y(i, j) = 4 * s * (1 - s)
 c = 255 * (1 - y(i, j))
 Screen.Pset (i, j), RGB(c, c, c)
 Next j
Next i

Для успешного округления переменной "с" необходимо, чтобы она была описана как переменная типа BYTE. Перед расчетом конфигурации следующего поколения нужно обновить значения всех элементов массива "x", заменив их вновь рассчитанными значениями (массив "y").

Пусть изначально заселенность каждой клетки представляет собой результат случайного равновероятного выбора произвольного числа из интервала от 0 до 1 (X(i,j)= rnd), а в дальнейшем в действие вступают описанные правила. Через некоторое время можно будет наблюдать, как на основе микроскопических межклеточных взаимодействий в процессе эволюции исходной хаотической конфигурации формируются макроскопические структуры заселенности клеточного поля. Несмотря на то, что закон взаимодействия клеток на микроскопическом уровне крайне прост и строго детерминирован, макроскопическая эволюция системы выглядит крайне сложно. В процессе эволюции на клеточном поле формируются изменчивые замысловатые кольцевые структуры, в которых чередуются зоны с высокой и низкой заселенностью.

Микробы
компьютерные
и микробы
живые

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

А.КОЛЕСНИКОВ,
andr61@mail.ru

Версия для печатиВерсия для печати

Номер: 

26 за 1999 год

Рубрика: 

Азбука программирования
Заметили ошибку? Выделите ее мышкой и нажмите Ctrl+Enter!
 

Комментарии

Аватар пользователя ggmu6
"Искусственная жизнь клеточных автоматов"

On the web-site

http://www.grsu-grodno.narod.ru/

you will find information on monograph that can be useful for you or your colleagues, namely:

Aladjev V.Z., Boiko V.K., Rovba E.A. Classical Cellular Automata: Theory and Applications.– Grodno: Grodno State University, 2008, 485 p. (in Russian and English)

At last, on the following web-sites you can find the extended bibliography on Cellular Automata (Homogeneous Structures):

http://www.geocities.com/ca_hs_ref

http://www.geocities.com/vz_aladjev

http://www.cellular-automata.narod.ru

Аватар пользователя Вепряков С.И.
Библиографию по клеточным автоматам можно найти здесь

http://depositfiles.com/en/files/y6eajlnz6

http://hsbibliography.bravehost.com/

http://www.ca-hs.narod.ru

http://ca-hs.weebly.com/