TLHE Feb 24 2023 at 10:01

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

Easy

5 min

34K

Programming*Algorithms*Reading roomDesignPopular science

Review

?, Хабр!

Осторожно, присутствуют мерцающие гифки. Они спрятаны под спойлеры, открывайте на своё усмотрение. На большом экране рекомендуется смотреть в хорошо освещённом помещении.

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

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

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

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

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

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

0. Игра «Жизнь»

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

Генерация со случайно заполненными клетками (30%) в центральных 80×80 на сетке 200×200

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

Устойчивые (a.k.a. «натюрморты»):
- Блоки
- Ульи и пасеки
- Пруды
- Караваи
- Лодки
- Корабли
Устойчивый пожиратель «рыболовный крючок»
Периодические мигалки
Классические планеры или глайдеры

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

Натюрморты:
- Пекарня (симметрия двойных караваев)
- Длинные баржи , лодки и корабли
- Лодочный и корабельный банты
- Каноэ
- Авианосец
- Интеграл
- Манго
- Змея
Осцилляторы:
- Звезда
- Крест
- Французский поцелуй
- Часы
- Октагон
- Фумарола
- Пентоид
- Галактика Кока
- Пентадекатлон
Ружья

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

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

Паровоз оставляющий за собой ружья Госпера

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

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

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

1. Лабиринт

B3/S12345

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

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

Генерация со случайно заполненными клетками (30%) в центральных 10×10 на сетке 200×200.

Уникальная генерация с башней и мигалкой. Огромная редкость при естественном росте.

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

Башни-близнецы с мигалками на каждой из сторон. Старт с центрального 19×19 заполненного блока.

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

B3/S1234 (без S5)

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

B37/S12345 (с B7)

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

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

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

2. H-деревья

B1/S012345678

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

Старт с точки; до границы в каждую сторону 98 клеток.

Старт с точки; до границы в каждую сторону 102 клетки.

Полностью случайный старт с 0.1% на живую клетку

3. Диамёба

B35678/S5678

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

Поле 200×200; случайное распределение 50% в центральных 140×140.

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

B345/S4567

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

Случайное 30% распределение на центральных 80×80

Случайное 20% распределение на центральных 180×180

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

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

B2/S0

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

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

N. Семена

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