????, Хабр!

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

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

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

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

• клетки имеют 2 состояния – жива/мертва;

• клетки – квадраты без смещений;

• правила изменения состояния зависят только от количества живых соседей из окрестности Мура первого порядка (8 окружающих);

• правила учитывают 4 исхода для каждой клетки – рождение, выживание, смерть, пустота.

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

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

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

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

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

• Устойчивые (a.k.a. «натюрморты»):

  • Блоки

  • Ульи и пасеки

  • Пруды

  • Караваи

  • Лодки

  • Корабли

• Устойчивый пожиратель «рыболовный крючок»

• Периодические мигалки

• Классические планеры или глайдеры

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

• Натюрморты:

  • Пекарня (симметрия двойных караваев)

  • Длинные баржи , лодки и корабли

  • Лодочный и корабельный банты

  • Каноэ

  • Авианосец

  • Интеграл

  • Манго

  • Змея

• Осцилляторы:

  • Звезда

  • Крест

  • Французский поцелуй

  • Часы

  • Октагон

  • Фумарола

  • Пентоид

  • Галактика Кока

  • Пентадекатлон

• Ружья

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

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

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

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

• И многие другие

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

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. То есть, клетки никогда не выживают, только появляются новые при двух соседях.

На этом правиле хорошо видны простейшие космические корабли.

6. Персидский ковёр

Продолжим идею невыживающих клеток. B234/S

Генерация со стартом с заполненного 2×2 блока

Генерация со случайным распределением

Есть ещё несколько интересных неименованных разновидностей «ковров»:

B234678/S8

B2345678/S0238

B234567/S124567

B235678/S1234567

7. Кораллы

И закончим со спойлерами. B3/S45678

Очень медленно, но всё же растущее правило с большим количеством осцилляторов.

8. Коагуляция

B378/S235678

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

9. Большинство

B45678/S5678

Приближаемся к завершению, а смотрели только на разрастающиеся конфигурации. Стоит это исправить.

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

10. Отжиг

B4678/S35678

Ещё одно правило с уменьшающимся видом, которое приходит к финальному состоянию только на самых малых натюрмортах и осцилляторах.

Бонус: ещё немного maze-like вариаций (без мерцаний, спойлер не из-за этого)

Удивительно, как им удаётся в итоге всё равно прийти к более или менее стабильному виду.

А тут уже мерцание

Следующая часть: поколенческие клеточные автоматы