Как стать автором
Обновить

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

Уровень сложности Простой
Время на прочтение 5 мин
Количество просмотров 30K

👾, Хабр!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    • Блоки

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

    • Пруды

    • Караваи

    • Лодки

    • Корабли

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

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

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

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

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

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

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

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

    • Каноэ

    • Авианосец

    • Интеграл

    • Манго

    • Змея

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

    • Звезда

    • Крест

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

    • Часы

    • Октагон

    • Фумарола

    • Пентоид

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

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

  • Ружья

Ружьё Госпера – выпускает глайдеры
Ружьё Госпера – выпускает глайдеры
  • Космические корабли

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

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

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

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

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

1. Лабиринт

B3/S12345

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

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

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

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

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

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

B3/S1234 (без S5)

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

B37/S12345 (с B7)

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

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

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

2. H-деревья

B1/S012345678

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

Старт с точки; до границы в каждую сторону 98 клеток.
Старт с точки; до границы в каждую сторону 98 клеток.
Старт с точки; до границы в каждую сторону 102 клетки.
Старт с точки; до границы в каждую сторону 102 клетки.
Старт из углов; поле 200×200
Старт из углов; поле 200×200
Полностью случайный старт с 0.1% на живую клетку
Полностью случайный старт с 0.1% на живую клетку

3. Диамёба

B35678/S5678

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

Поле 200×200; случайное распределение 50% в центральных 140×140.
Поле 200×200; случайное распределение 50% в центральных 140×140.
Осцилляторы
Осцилляторы
Космические корабли
Космические корабли
Фигуры с бесконечным ростом
Фигуры с бесконечным ростом

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

B345/S4567

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

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

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

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

B2/S0

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

Случайное распределение 40×40
Случайное распределение 40×40

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

N. Семена

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

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

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

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

Генерация со стартом с заполненного 2×2 блока
Вид полностью соответствует наименованию
Вид полностью соответствует наименованию

Генерация со случайным распределением
Уже что-то не то, верно?
Уже что-то не то, верно?

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

B234678/S8

B2345678/S0238

B234567/S124567

B235678/S1234567

7. Кораллы

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

Случайное распределение 40%
Случайное распределение 40%

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

Различные виды осцилляторов на данном правиле
Различные виды осцилляторов на данном правиле

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

B378/S235678

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

Случайное распределение 40%
Случайное распределение 40%

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

B45678/S5678

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

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

Интересно, что между некоторыми группами сохраняется сообщение "бегущими" линиями.
Интересно, что между некоторыми группами сохраняется сообщение "бегущими" линиями.

10. Отжиг

B4678/S35678

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

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

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

B2/S124
B2/S124
B2/S123
B2/S123
B3/S012358
B3/S012358
B25/S23457
B25/S23457
B278/S0124567
B278/S0124567
B26/S012357
B26/S012357
B2378/S1234
Столько мышей у нас не было. Или же это конвейер.
B2378/S1234 Столько мышей у нас не было. Или же это конвейер.
B23/S234
Силовые поля?
B23/S234 Силовые поля?
А тут уже мерцание
B24567/S
B24567/S


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

Читайте также

О клеточных автоматах:

  1. Базовая «life-like» конфигурация (вы здесь)

  2. Старение клеток: параметр поколений

  3. Нотация Хенселя: учёт расположения соседей

  4. LtL: расширенный радиус поиска соседей

  5. Циклические КА

  6. Альтернативные окрестности и HROT

  7. Блочные КА, окрестность Марголуса

  8. Взвешенные окрестности, окрестность Гаусса, Far Corners/Edges

  9. Направленные и пользовательские окрестности

  10. Клетки-киллеры, BSFK[L]

  11. Дефицитные правила

  12. Обратные и расширенные поколения

Прочее:

Теги:
Хабы:
+158
Комментарии 24
Комментарии Комментарии 24

Публикации

Истории

Работа

Веб дизайнер
36 вакансий

Ближайшие события

Московский туристический хакатон
Дата 23 марта – 7 апреля
Место
Москва Онлайн
Геймтон «DatsEdenSpace» от DatsTeam
Дата 5 – 6 апреля
Время 17:00 – 20:00
Место
Онлайн