Реализация классического клеточного автомата — конуээвской «Жизни» — это такая же задачка для начинающего программиста, как для радиотехника — спаять простейший радиоприемник. Для тех кто не знает, что такое «Жизнь», прочитайте эту статью: Википедия: Жизнь (игра).
Напомню правила: действие происходит на клеточном поле. Каждая клетка имеет 8 соседей — клетки, примыкающие к ней сторонами или углами. В начале игры некоторые клетки заполнены, образуя начальный организм, остальные — пусты. Эволюция происходит так: в следующем поколении очищаются все заполненные клетки, имеющие менее 2 или более 3 соседей и заполняются пустые, имеющие ровно 3 соседа.
После того, как поиграешь с интересными конфигурациями, становится немного скучно. В самом деле, за 40 лет все, что можно описано, разжевано на сотнях страниц различных статей и книг. Найти что-то новое и интересное сложно. Тогда возникает желание поменять правила — а вдруг новые организмы будут вести себя совершенно по-иному?
Здесь вы можете сразу посмотреть демо.
Для начала можно изменить количество клеток, при котором умирают старые и появляются новые. Всего 28 вариантов (появляется ли клетка при N = 1..8 соседях?) для рождения клеток и 29 — для смерти, итого имеем 217, неплохое количество. Однако, большинство таких конфигураций не представляет интереса (быстро вымирают или неограниченно распространяются). Сам Джон Конуэй писал, что экспериментировал с правилами, так подбирая значения, чтобы эволюция была интересной: плохо предсказуемой, относительно долгой, оставляющей после себя различные изолированные конфигурации, а также чтобы не было простых неограниченно растущих конфигураций. И в итоге пришел к единственной, которая сейчас имеет наибольшую популярность.
Теперь попробуем обобщить правила. Имеем клетку, которая может быть заполненной или пустой, а также группу клеток — соседей. Итого 2 группы — из одной клетки и из 8 клеток.
Нам нужен список пар приращений координат, определяющий положение клеток группы относительно обрабатываемой. Для первой группы (центральная клетка) это будет единственная пара ( +0, +0 ). Для второй (соседние клетки) — восемь пар ( -1, -1 ), ( -1, +0 ), …, ( +1, +0 ), ( +1, +1 ).
Для задания правил воспользуемся двумерным массивом булева типа. Размерность определяется количеством возможных состояний групп: для первой — два (клетка в центре пуста или заполнена), для второй — девять (от 0 соседей до максимального кол-ва — 8).
Индекс элемента массива определяет количество заполненных клеток в каждой из групп, а значение элемента — состояние клетки после обработки: пуста (false) или заполнена (true). Таким образом, чтобы узнать, что делать с заполненной клеткой с 4-мя соседями, нам нужно обратиться к элементу с индексом ( 1, 4 ). Если значение — false — очищаем клетку, если true — оставляем без изменений. А содержимое массива будет таким: элементы с индексами ( 0, 3 ), ( 1, 2 ) и ( 1, 3 ) равны true, остальные — false.
Обобщим правила для N групп: массив координат будет содержать N списков пар целых значений, а свод правил будет представлен N-мерным массивом, n-ая размерность которого будет равна 1 + кол-во списков пар приращений для n-ой группы.
При такой структуре правил количество вариантов ограничено только фантазией, хотя возможность расширения правил еще есть. Теперь о нюансах реализации.
Реализация массива c задаваемым программно количеством измерений во всех знакомых мне языках отсутствует, поэтому придется писать свою. Сделаем это через одномерный массив следующим образом: пусть надо создать n-мерный массив е[ Q1, Q2, …, Qn ] с диапазоном индексов [ 0 … Qn — 1 ] для n-ой размерности. Создадим одномерный массив е’ с размерностью Q1 * Q2 * … * Qn и сопоставим каждому элементу е[ i1, i2, …, in ] элемент e’[ i1 * k1 + i2 * k2 + …+ in * kn ], где km = 1 * Q1 * Q2 * … * Qm — 1. То есть, k1 = 1, k2 = Q1, k3 = Q1 * Q2 и т. д. Это взаимно-однозначное соответствие, иначе говоря разные элементы массива е будут соответствовать разным элементам массива e’.
Для быстродействия и простоты я буду реализовывать ограниченное зацикленное поле. Алгоритм зацикливания целой координаты Х в диапазоне [ 0 … K — 1 ] таков: если при изменении координаты она вышла из этого диапазона, то будем увеличивать или уменьшать ее на К единиц (в зависимости от того, слева или справа от нашего диапазона она находится) пока координата не вернется в заданные пределы. Тогда при “выходе” координаты за правую границу диапазона, она “войдет” через левую границу и наоборот.
Алгоритм реализуется формулой X = X — floor( X / K ) * K, но если K — это степень двойки, то лучше использовать более быструю и простую формулу X = X & K.
Поле, таким образом, будет представлять собой двумерный массив N x N клеток, который можно представить одномерным с помощью уже знакомого соответствия e( X, Y ) => e’( X + Y * N ).
Теперь немного об оптимизации:
Не стоит перерисовывать все поле на каждом шаге эволюции. Конечно, в начале придется отрисовать все клетки начальной конфигурации, но потом для каждого поколения достаточно перерисовать только изменившиеся клетки.
Вместо того, чтобы обрабатывать все заполненные клетки и соседние незаполненные с проверкой количества соседей для каждой клетки, лучше обрабатывать только изменение заполненности клетки, храня в каждой клетке количество ее соседей: при заполнении клетки, она “разбрасывает” единицы по клеткам, соседом которых она является, увеличивая значение количества соседей для этих клеток. И наоборот, при очищении клетки, она эти единицы “забирает”.
Так как мы имеем несколько групп, то получается, что для каждой клетки мы должны хранить список из кол-ва соседей для каждой группы. Но быстрее будет использовать вместо этого списка соответствующее ему целое число по принципу соответствия, аналогичному преобразованию адреса при переходе от многомерного массива к одномерному, который мы рассмотрели ранее: [ K1, K2, …, Kn ] => [ K1 + Q1 * K2 + Q1 * Q2 * K3 +… + Q1 * … * Qn-1 * Kn ].
Таким образом, цикл поколения будет выглядеть так:
Программу я писал на языке Google Dart, посмотреть ее можно здесь. Запустить скомпилированную в Javascript программу можно здесь.
Теперь об интересных сводах правил, которые мне удалось найти:
Этот вариант правил характеризуется эволюцией похожей на зыбучие пески. Случайно заполненное поле стабилизируется через несколько сотен поколений. При этом образуется множество стабильных конфигураций вроде блоков и диагональных полосок, и простейших пульсирующих конфигураций с периодом в 2 поколения — диагональный ряд из 2-х клеток и вертикальный из 3-х. Также часто встречается пульсирующий крест с периодом в 3 поколения. Еще встречаются “шокеры” — стабильные конфигурации с несколькими пульсирующими клетками, а также “бабочки” — пульсирующие конфигурации с большим периодом, похожие на машущих крыльями насекомых. Перемещающихся конфигураций я не встретил.
Правила аналогичны предыдущим, только вместо рождения при 1 соседе по диагонали и 2 по вертикали/горизонтали используется правило рождения при 2 соседях по диагонали и 1 по вертикали/горизонтали.
Тоже зыбучие пески, но стабилизируются они быстрее — после 100-200 поколений, а конфигурации возникают иные. Стабильных конфигураций почти нет (в основном это блоки 2х2), а вот пульсирующих — целый зоопарк. Можно отметить популярную конфигурацию “скобка”, квадраты с мигающими краями, крест из предыдущих правил, “конфету”, пульсирующий мусор и довольно сложную и большую “летучую мышь” с большим периодом пульсации. Иногда конфигурация выпускает летящие по вертикали/горизонтали “истребители”.
Случайная конфигурация при этих правилах быстро приобретает ромбоподобную форму. Она крайне не склонна разделяться на несколько пульсирующих областей и любит подбирать за собой оставленные стабильные и пульсирующие блоки. Крайне неохотно разрастается и уменьшается, но при малых размерах часто исчезает, оставляя после себя маленькие стабильные или пульсирующие конфигурации.
Данные правила приводят к тому, что конфигурации тяготеют к прямоугольно-диагональным формам, похожим на дорожки печатной платы. После приблизительно тысячи поколений на поле обычно остаются пульсирующие прямоугольные конфигурации.
Конфигурация быстро приобретает вид “кипящей воды с паром” в треугольных “бокалах”. Она обычно “успокаивается” через несколько тысяч поколений, после чего остается система этих “бокалов” с пульсирующей “водой” в них.
Массив клеток, существующий изначально, начинает быстро разрастаться влево и вправо, что обеспечивается быстрым формированием “паровозов”, то есть перемещающихся конфигураций, оставляющих за собой пульсирующий след. Так как поле закольцовано, то “армады кораблей” сталкиваются, в результате чего ее части могут как уничтожиться, так и трансформироваться в корабли, летящие в обратном направлении, а также оставить после себя пульсирующие конфигурации. Из примечательных конфигураций — минимальная перемещающая единица — скаут (напоминает корабль Shofixti из Star Control), также есть немного больших размеров “парусники”, генерирующий “скаутов” “бомбардировщик”, размножающийся в геометрической прогрессии “диск”, а также стабильные конфигурации “слэш”, “аплодисменты” и “прыгающая дуга”, которые могут в некоторых случаях разворачивать корабли в обратную сторону.
Эта конфигурация склонна отступать и наступать рывками, медленно расширяясь по итогам и оставляя диагональные, изогнутые под прямым углом “проволочные” куски. Также часто остается “жизненные” камень и улей, вращающееся “двоеточие”. Из пульсирующих конфигураций можно выделить “четыре точки”, “комкатель” из двух камней и “улыбку” с длинным периодом пульсации. Часто в результате развития маленькой отдельной конфигурации образуется стабильный “ромб”.
Здесь вместо “проволочных” кусков формируются стабильные ворохи из “камней” и “завитушек”разной сложности. Есть одна распространенная диагонально перемещающаяся конфигурация “пятно”.
При таких правилах даже самые мелкие конфигурации часто превращаются в замысловатые “паровозы”. Можно выделить вертикальную “змею” с возможной генерацией массива двуклеточных “плашек”, растущий полосатый треугольник, растущий диагональный ряд, генерирующий пульсирующий мусор. Также некоторые конфигурации могут передавать по образовавшемуся диагональному ряду одноклеточные “сигналы”, которые другими конфигурациями могут быть погашены. Существует простая перемещающаяся вертикально конфигурация — “тележка”, которая может оставлять за собой исчезающий “дым”, а также пульсирующий “паучок”, который часто является стабилизатором диагонального ряда.
В программе вы найдете еще своды правил, каждый из которых имеет интересную особенность.
Напомню правила: действие происходит на клеточном поле. Каждая клетка имеет 8 соседей — клетки, примыкающие к ней сторонами или углами. В начале игры некоторые клетки заполнены, образуя начальный организм, остальные — пусты. Эволюция происходит так: в следующем поколении очищаются все заполненные клетки, имеющие менее 2 или более 3 соседей и заполняются пустые, имеющие ровно 3 соседа.
После того, как поиграешь с интересными конфигурациями, становится немного скучно. В самом деле, за 40 лет все, что можно описано, разжевано на сотнях страниц различных статей и книг. Найти что-то новое и интересное сложно. Тогда возникает желание поменять правила — а вдруг новые организмы будут вести себя совершенно по-иному?
Здесь вы можете сразу посмотреть демо.
Для начала можно изменить количество клеток, при котором умирают старые и появляются новые. Всего 28 вариантов (появляется ли клетка при N = 1..8 соседях?) для рождения клеток и 29 — для смерти, итого имеем 217, неплохое количество. Однако, большинство таких конфигураций не представляет интереса (быстро вымирают или неограниченно распространяются). Сам Джон Конуэй писал, что экспериментировал с правилами, так подбирая значения, чтобы эволюция была интересной: плохо предсказуемой, относительно долгой, оставляющей после себя различные изолированные конфигурации, а также чтобы не было простых неограниченно растущих конфигураций. И в итоге пришел к единственной, которая сейчас имеет наибольшую популярность.
Теперь попробуем обобщить правила. Имеем клетку, которая может быть заполненной или пустой, а также группу клеток — соседей. Итого 2 группы — из одной клетки и из 8 клеток.
Нам нужен список пар приращений координат, определяющий положение клеток группы относительно обрабатываемой. Для первой группы (центральная клетка) это будет единственная пара ( +0, +0 ). Для второй (соседние клетки) — восемь пар ( -1, -1 ), ( -1, +0 ), …, ( +1, +0 ), ( +1, +1 ).
Для задания правил воспользуемся двумерным массивом булева типа. Размерность определяется количеством возможных состояний групп: для первой — два (клетка в центре пуста или заполнена), для второй — девять (от 0 соседей до максимального кол-ва — 8).
Индекс элемента массива определяет количество заполненных клеток в каждой из групп, а значение элемента — состояние клетки после обработки: пуста (false) или заполнена (true). Таким образом, чтобы узнать, что делать с заполненной клеткой с 4-мя соседями, нам нужно обратиться к элементу с индексом ( 1, 4 ). Если значение — false — очищаем клетку, если true — оставляем без изменений. А содержимое массива будет таким: элементы с индексами ( 0, 3 ), ( 1, 2 ) и ( 1, 3 ) равны true, остальные — false.
Обобщим правила для N групп: массив координат будет содержать N списков пар целых значений, а свод правил будет представлен N-мерным массивом, n-ая размерность которого будет равна 1 + кол-во списков пар приращений для n-ой группы.
При такой структуре правил количество вариантов ограничено только фантазией, хотя возможность расширения правил еще есть. Теперь о нюансах реализации.
Реализация массива c задаваемым программно количеством измерений во всех знакомых мне языках отсутствует, поэтому придется писать свою. Сделаем это через одномерный массив следующим образом: пусть надо создать n-мерный массив е[ Q1, Q2, …, Qn ] с диапазоном индексов [ 0 … Qn — 1 ] для n-ой размерности. Создадим одномерный массив е’ с размерностью Q1 * Q2 * … * Qn и сопоставим каждому элементу е[ i1, i2, …, in ] элемент e’[ i1 * k1 + i2 * k2 + …+ in * kn ], где km = 1 * Q1 * Q2 * … * Qm — 1. То есть, k1 = 1, k2 = Q1, k3 = Q1 * Q2 и т. д. Это взаимно-однозначное соответствие, иначе говоря разные элементы массива е будут соответствовать разным элементам массива e’.
Для быстродействия и простоты я буду реализовывать ограниченное зацикленное поле. Алгоритм зацикливания целой координаты Х в диапазоне [ 0 … K — 1 ] таков: если при изменении координаты она вышла из этого диапазона, то будем увеличивать или уменьшать ее на К единиц (в зависимости от того, слева или справа от нашего диапазона она находится) пока координата не вернется в заданные пределы. Тогда при “выходе” координаты за правую границу диапазона, она “войдет” через левую границу и наоборот.
Алгоритм реализуется формулой X = X — floor( X / K ) * K, но если K — это степень двойки, то лучше использовать более быструю и простую формулу X = X & K.
Поле, таким образом, будет представлять собой двумерный массив N x N клеток, который можно представить одномерным с помощью уже знакомого соответствия e( X, Y ) => e’( X + Y * N ).
Теперь немного об оптимизации:
Не стоит перерисовывать все поле на каждом шаге эволюции. Конечно, в начале придется отрисовать все клетки начальной конфигурации, но потом для каждого поколения достаточно перерисовать только изменившиеся клетки.
Вместо того, чтобы обрабатывать все заполненные клетки и соседние незаполненные с проверкой количества соседей для каждой клетки, лучше обрабатывать только изменение заполненности клетки, храня в каждой клетке количество ее соседей: при заполнении клетки, она “разбрасывает” единицы по клеткам, соседом которых она является, увеличивая значение количества соседей для этих клеток. И наоборот, при очищении клетки, она эти единицы “забирает”.
Так как мы имеем несколько групп, то получается, что для каждой клетки мы должны хранить список из кол-ва соседей для каждой группы. Но быстрее будет использовать вместо этого списка соответствующее ему целое число по принципу соответствия, аналогичному преобразованию адреса при переходе от многомерного массива к одномерному, который мы рассмотрели ранее: [ K1, K2, …, Kn ] => [ K1 + Q1 * K2 + Q1 * Q2 * K3 +… + Q1 * … * Qn-1 * Kn ].
Таким образом, цикл поколения будет выглядеть так:
- Перед первым циклом, обрабатываются все клетки начальной конфигурации. В список обрабатываемых клеток cells заносятся они и те клетки, соседями которых они являются.
- Все клетки из cells проверяются на изменение (то есть, если их состояние и состояние из свода правил, соответствующее количеству их соседей в данный момент, не равны). Если по правилам состояние должно измениться, эта клетка заносится в список изменившихся клеток togglingCells.
- Список cells очищается.
- Все клетки из togglingCells меняют свое состояние, “разбрасывая” или “забирая” свое соседство из клеток, соседями которых они являются. Все клетки с изменившимcя кол-вом соседей заносятся в cells.
- Клетки togglingCells отрисовываются.
- togglingCells очищается.
Программу я писал на языке Google Dart, посмотреть ее можно здесь. Запустить скомпилированную в Javascript программу можно здесь.
Теперь об интересных сводах правил, которые мне удалось найти:
Горизонтально-вертикально-диагональная разбивка
ПесочнаяГВ (SandyLifeHV)
- Выживание
- 1 или 2 по диагонали + 1 или 2 по вертикали/горизонтали
- Рождение
- 2 по диагонали + 0 по вертикали/горизонтали
- 0 по диагонали + 2 по вертикали/горизонтали
- 1 по диагонали + 2 по вертикали/горизонтали
Этот вариант правил характеризуется эволюцией похожей на зыбучие пески. Случайно заполненное поле стабилизируется через несколько сотен поколений. При этом образуется множество стабильных конфигураций вроде блоков и диагональных полосок, и простейших пульсирующих конфигураций с периодом в 2 поколения — диагональный ряд из 2-х клеток и вертикальный из 3-х. Также часто встречается пульсирующий крест с периодом в 3 поколения. Еще встречаются “шокеры” — стабильные конфигурации с несколькими пульсирующими клетками, а также “бабочки” — пульсирующие конфигурации с большим периодом, похожие на машущих крыльями насекомых. Перемещающихся конфигураций я не встретил.
ПесочнаяД (SandyLifeD)
Правила аналогичны предыдущим, только вместо рождения при 1 соседе по диагонали и 2 по вертикали/горизонтали используется правило рождения при 2 соседях по диагонали и 1 по вертикали/горизонтали.
Тоже зыбучие пески, но стабилизируются они быстрее — после 100-200 поколений, а конфигурации возникают иные. Стабильных конфигураций почти нет (в основном это блоки 2х2), а вот пульсирующих — целый зоопарк. Можно отметить популярную конфигурацию “скобка”, квадраты с мигающими краями, крест из предыдущих правил, “конфету”, пульсирующий мусор и довольно сложную и большую “летучую мышь” с большим периодом пульсации. Иногда конфигурация выпускает летящие по вертикали/горизонтали “истребители”.
Амеба (AmoebaLife)
- Выживание
- 2 по диагонали + 0-2 по вертикали/горизонтали
- 0-2 по диагонали + 2 по вертикали/горизонтали
- Рождение
- 2 по диагонали + 0-2 по вертикали/горизонтали
Случайная конфигурация при этих правилах быстро приобретает ромбоподобную форму. Она крайне не склонна разделяться на несколько пульсирующих областей и любит подбирать за собой оставленные стабильные и пульсирующие блоки. Крайне неохотно разрастается и уменьшается, но при малых размерах часто исчезает, оставляя после себя маленькие стабильные или пульсирующие конфигурации.
Электроника (ElectronicLife)
- Выживание
- 2-3 по диагонали + 2 по вертикали/горизонтали
- 0-1 по диагонали + 2-3 по вертикали/горизонтали
- Рождение
- 1-2 по диагонали + 1-2 по вертикали/горизонтали
Данные правила приводят к тому, что конфигурации тяготеют к прямоугольно-диагональным формам, похожим на дорожки печатной платы. После приблизительно тысячи поколений на поле обычно остаются пульсирующие прямоугольные конфигурации.
Слоеная разбивка
Жидкость (LiquidLife)
- Появление / выживание клетки
- 0-1 верхних + 1-3 центральных + 2-3 нижних
- 1-2 верхних + 2-3 центральных + 0-1 нижних
- 2-3 верхних + 1-3 центральных + 1-2 нижних
Конфигурация быстро приобретает вид “кипящей воды с паром” в треугольных “бокалах”. Она обычно “успокаивается” через несколько тысяч поколений, после чего остается система этих “бокалов” с пульсирующей “водой” в них.
Армада (ArmadaLife)
- Появление / выживание клетки
- 0-1 верхних + 1-2 центральных + 2-3 нижних
- 1-3 верхних + 1-2 центральных + 1-3 нижних
- 2-3 верхних + 1-2 центральных + 0-1 нижних
Массив клеток, существующий изначально, начинает быстро разрастаться влево и вправо, что обеспечивается быстрым формированием “паровозов”, то есть перемещающихся конфигураций, оставляющих за собой пульсирующий след. Так как поле закольцовано, то “армады кораблей” сталкиваются, в результате чего ее части могут как уничтожиться, так и трансформироваться в корабли, летящие в обратном направлении, а также оставить после себя пульсирующие конфигурации. Из примечательных конфигураций — минимальная перемещающая единица — скаут (напоминает корабль Shofixti из Star Control), также есть немного больших размеров “парусники”, генерирующий “скаутов” “бомбардировщик”, размножающийся в геометрической прогрессии “диск”, а также стабильные конфигурации “слэш”, “аплодисменты” и “прыгающая дуга”, которые могут в некоторых случаях разворачивать корабли в обратную сторону.
Боковая разбивка
Проволока (WireLife)
- Выживание
- 1-3 по горизонтали + 1-2 по вертикали
- Рождение
- 2 по горизонтали + 2-3 по вертикали
Эта конфигурация склонна отступать и наступать рывками, медленно расширяясь по итогам и оставляя диагональные, изогнутые под прямым углом “проволочные” куски. Также часто остается “жизненные” камень и улей, вращающееся “двоеточие”. Из пульсирующих конфигураций можно выделить “четыре точки”, “комкатель” из двух камней и “улыбку” с длинным периодом пульсации. Часто в результате развития маленькой отдельной конфигурации образуется стабильный “ромб”.
Завитушки (TwirlLife)
- Выживание
- 1-3 по горизонтали + 1-3 по вертикали
- Рождение
- 2 по горизонтали + 2 по вертикали
Здесь вместо “проволочных” кусков формируются стабильные ворохи из “камней” и “завитушек”разной сложности. Есть одна распространенная диагонально перемещающаяся конфигурация “пятно”.
Скобочная разбивка
Змеи (Snakes)
- Выживание
- 2-3 клетки в одной из скоб, 0 в другой
- Рождение
- 1-2 клетки в каждой из скоб
При таких правилах даже самые мелкие конфигурации часто превращаются в замысловатые “паровозы”. Можно выделить вертикальную “змею” с возможной генерацией массива двуклеточных “плашек”, растущий полосатый треугольник, растущий диагональный ряд, генерирующий пульсирующий мусор. Также некоторые конфигурации могут передавать по образовавшемуся диагональному ряду одноклеточные “сигналы”, которые другими конфигурациями могут быть погашены. Существует простая перемещающаяся вертикально конфигурация — “тележка”, которая может оставлять за собой исчезающий “дым”, а также пульсирующий “паучок”, который часто является стабилизатором диагонального ряда.
В программе вы найдете еще своды правил, каждый из которых имеет интересную особенность.
