10 удивительно зрелищных простейших клеточных автоматов

15 августа 202315 авг 2023

4 мин

Оглавление

Игра «Жизнь»
1. Лабиринт
Лабиринты с модификациями

Базовая вводная

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

Самое простое представление двумерной модели включает следующие характеристики:

клетки имеют 2 состояния – жива/мертва;
клетки – квадраты без смещений;
правила изменения состояния зависят только от количества живых соседей из окрестности Мура первого порядка (8 окружающих);
правила учитывают 4 исхода для каждой клетки – рождение, выживание, смерть, пустота.

Такая категория КА называется «Life-like», по названию самого известного автомата с такими характеристиками – «Conway's Game of Life». Игра «Жизнь» Конвея работает на правиле B3/S23, т.е. для рождения клетки (Birth) требуется ровно 3 живых соседа, для выживания (Survival) – 2 или 3. Во всех других случаях клетка умирает (или же остаётся пустой).

На данных характеристиках у нас существует 218 вариантов правил. Очень немногая часть из них получила в сообществе собственные названия, сверх обычного именования нотацией. Сегодня посмотрим на нескольких интересных представителей.

Игра «Жизнь»

Вне счёта, для разминки начнём с классики. B3/S23

Из-за популярности автомата у него существует множество именованных паттернов/фигур. На этом примере мы видим несколько простейших:

В случайной генерации/развитии сложно поймать более изощрённые паттерны, но их ещё множество:

Ружья

Космические корабли

Паровозы – космические корабли оставляющие за собой след из других объектов

Грабли – паровозы оставляющие за собой след из космических кораблей

Поглощатели и отражатели – структуры не повреждающиеся от сталкивающихся с ними космических кораблей, уничтожая или отражая последние
И многие другие

Игра «Жизнь» стала культовой и внесла большой вклад в популяризацию клеточных автоматов. По сей день обсуждают различные возможные конфигурации объектов, а на собеседованиях могут предложить простую задачу с итерацией этого КА.

1. Лабиринт

B3/S12345

Конфигурация с почти полным заполнением, без отмирания клеток.

На генерациях со случайным началом паттерны обнаруживается очень редко.

Как и с многими КА, подбор стартового состояния может дать очень впечатляющие орнаменты.

Лабиринты с модификациями

B3/S1234 (без S5)

Mazectric модификация приводит к более вытянутым коридорам, более плавному и полному распространению, а также на ней куда чаще встречаются естественные мигалки.

B37/S12345 (с B7)

Лабиринт с «мышами»-мигалками. Дополнительное рождение при 7 соседях порождает бегающие по лабиринту клетки-мыши, хоть они и ограничены только прямыми коридорами, сталкиваясь друг с другом.

И вместе – B37/S1234. Mazectric with mice.

Интересно как мыши в этом варианте иногда "запирают" некоторые свежесгенерированные проходы лабиринта, становясь частью последнего.

2. H-деревья

B1/S012345678

Один из самых "предсказуемых" КА, не имеющий каких-либо особых паттернов сверх своего обычного вида. Потому с ним интереснее вручную задавать старт, получая определённый финальный орнамент.

3. Диамёба

B35678/S5678

Поглощающее правило с рядом известных паттернов.

4. Ассимиляция

B345/S4567

Ещё одно поглощающее правило со стабильным видом. Стремится к ромбу, но не всегда заканчивает фигуру.

На последней генерации видно, что у данного правила также присутствуют осцилляторы – пропеллеры, волны, стрелы, жуки (названия я придумал сам ¯\_(ツ)_/¯).

5. Живи свободным или умри

B2/S0

Не самое зрелищное, но концептуально интересное правило, отсылающее к девизу времён войны за независимость США (ныне официальный девиз штата Нью-Гэмпшир) – клетки выживают только если не имеют соседей, а рождаются исключительно от двух клеток.

В правиле существует только один вид осцилляторов – дуоплеты (две клетки расположенные по диагонали друг от друга), а также несколько прочих фигур, вроде ружья и космических кораблей.

N. Семена

Отдельное правило, но упомянем вне счёта, как продолжение идеи прошлого. Здесь ещё более строгое условие выживания – B2/S. То есть, клетки никогда не выживают, только появляются новые при двух соседях.