????, Хабр!
Осторожно, присутствуют мерцающие гифки. Они спрятаны под спойлеры, открывайте на своё усмотрение. На большом экране рекомендуется смотреть в хорошо освещённом помещении.
Базовая вводная
Клеточный автомат – модель, в которой состояние ячеек-клеток изменяется в зависимости от окружающих её клеток. Существует множество характеристик моделей, в каждой из которых ещё большее количество правил-конфигураций.
Самое простое представление двумерной модели включает следующие характеристики:
клетки имеют 2 состояния – жива/мертва;
клетки – квадраты без смещений;
правила изменения состояния зависят только от количества живых соседей из окрестности Мура первого порядка (8 окружающих);
правила учитывают 4 исхода для каждой клетки – рождение, выживание, смерть, пустота.
Такая категория КА называется «Life-like», по названию самого известного автомата с такими характеристиками – «Conway's Game of Life». Игра «Жизнь» Конвея работает на правиле B3/S23, т.е. для рождения клетки (Birth) требуется ровно 3 живых соседа, для выживания (Survival) – 2 или 3. Во всех других случаях клетка умирает (или же остаётся пустой).
На данных характеристиках у нас существует 218 вариантов правил. Очень немногая часть из них получила в сообществе собственные названия, сверх обычного именования нотацией. Сегодня посмотрим на нескольких интересных представителей.
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 вариаций (без мерцаний, спойлер не из-за этого)
Удивительно, как им удаётся в итоге всё равно прийти к более или менее стабильному виду.
А тут уже мерцание
Следующая часть: поколенческие клеточные автоматы
Читайте также
Комментарии (22)
khrapko
00.00.0000 00:00+5На первом курсе инстика была у нас Машина МИР-2 по моему. Вот на ней игрались с клеточными автоматами. Но быстро убили печатную машинку. Больше нас туда не пускали.
Terimoun
00.00.0000 00:00+1Мне одному поплохело в процессе чтения из-за этих картинок?
Medeyko
00.00.0000 00:00+27Вероятно, не только Вам, но большинство людей должны воспринимать их без неприятных ощущений.
Возможно, Вам стоит проявлять осторожность, когда сталкиваетесь с мельтешащими объектами.
То, что автор скрыл мигающие картинки спойлерами, вызывает уважение к его обстоятельности.
halfhope
00.00.0000 00:00Вспомнилась статья про простую систему из нескольких простых правил, которая на более высоком уровне может эмулировать саму себя. Близкая тема, но найти статью не могу.
Nikita22007
00.00.0000 00:00+2https://www.youtube.com/v/xP5-iIeKXE8
Клеточный автомат "Жизнь" тьюринг-полный. В нём можно реализовать любой другой клеточный автомат
DarkMitya
00.00.0000 00:00Похоже это и есть "мультик" из игры "Ну погоди", про волка который ловил яйца.
kraidiky
00.00.0000 00:00+5Среди паттернов жизни отсутствует мой любимый - световая волна:
Двигается со скоростью света (единственная в своём роде), но схлопывается при этом с краёв. Может исчезать без остатков или оставляя некоторые конструкции в зависимости от выбора варианта оформления края.
Linder666
Так вот как эти узоры создаются! Оказывается персидские/узбекские/армянские мастера просто играют в клеточные автоматы)))
engine9
Это докомпьютерный пиксель арт с симметриями :)
P.S.: Кто желает поиграться с КА на своей ЭВМ, рекомендую бесплатную программу Golly. Многочасовое залипалово обеспечено.
Terimoun
Интересно, а как они пользовались клеточными автоматами до изобретения компьютера? ????
Gadd
Мы с братом как-то в детстве узнали при "Жизнь" Конвея, если правильно помню - из Техники Молодёжи. Брат расчертил поле, нарубил гильзой кучу кругляшков из обложки общей тетради. Новые клетки - одна сторона фишки, не новые - другая, на "умирающие" клали сверху ещё одну, опять же, если я правильно помню.
Вот так и играли.
Tarson
У Мартина Гарднера в одном из томов по занимательной математике Жизнь была подробно разобрана. Было дело тоже играл в детстве. Но когда вручную, ошибиться очень легко. Поэтому дальше простейших фигур не удалось пройти. А планерное ружье так вообще за гранью...
CTheo
В детстве исчертил тетрадку в клетку, результат не сошелся с результатом из журнала, оказалось на 3-м шаге ошибся в 1 клетке.
Didimus
В юном технике (или в левше ) предлагали вручную пойти комбинацию из 1000+ ходов
MAXH0
Что такое "клеточный автомат". Это когда клетка генерируется на основании значений соседних по простому правилу. Если цвета подбираются на основании "после цвета X вязать цвет Y, если рядом цвет Z" то это вполне клеточный автомат. Просто без эволюции.
Chillingwilli
Осталось только узнать тайну изготовления финки НКВД
ZekaVasch
Нужно взять простой советский...