👾!
Возвращаемся к нашей экскурсии по модификациям клеточных автоматов. Объект сегодняшнего внимания – дефицитные правила (deficient rules). Это ещё более свежая вариация, чем рассмотренный в прошлом посте , и была описана 5 лет назад энтузиастом 83bismuth38.
Модификация предполагает, что при рождении клетки на окружающих соседей налагается ограничение на рождение по этому переходу, согласно нотации Хенселя. Освежить в памяти, что из себя представляют переходы можно здесь.
Учёт соседей определяется правилами, которые устанавливаются нами. Вариаций правил существует бесчисленное множество, и они были систематизированы в определённые конфигурации.
Самая популярная конфигурация – «B/S», или «life-like», по названию крайне широко известного клеточного автомата «Game of Life», где B/S обозначает, что в нашем правиле мы описываем всего два параметра – количество соседей необходимых для рождения новой клетки в пустой ячейке, и количество соседей для выживания существующей клетки.
В каждой статье серии мы углубляемся в данную конфигурацию, добавляя новые параметры, либо дополняя существующие. Иногда заглядываем и в прочие конфигурации.
Начало серии здесь, если желаете ознакомиться последовательно.
Существуют две разновидности ограничений – вре́менные и постоянные. Вре́менные действуют одну итерацию, постоянные – пока жива сама клетка, распространяющая ограничение.
В устоявшейся нотации и применении модификации эти параметры используются глобально: все переходы дефицитные или, того более, – все перманентно дефицитные. Обозначаются как d и dp, соответственно, в конце правила. Мы же несколько расширим конфигурацию и будем использовать отдельные параметры D и P, по общему с B/S синтаксису, с явным обозначением, какие именно переходы будут временно дефицитными, какие перманентно, а какие и вовсе работать по старым правилам.
Ещё раз обратим внимание на то, что ограничение налагается именно при рождении, а значит наше перечисление в параметре D будет подмножеством переходов B. Даже если мы укажем больше, эти ограничения попросту никогда не сработают. И аналогично, перечисление переходов для перманентного дефицита P является подмножеством переходов из пересечения D и S, то есть мы указываем, какие переходы из D стоит продлевать при выживании клетки.
Также мы добавим к нашей модификации функциональность поколений. Даже в тех немногих описанных в интернете правилах они не используются, по той лишь причине, что в известных симуляторах КА состояния клеток, ранее используемые для поколенческих правил, используются для обозначения перехода в дефицитных правилах, что не позволяет использовать их вместе.
Потенциальный вид правила в нашей модификации дефицитных правил – [G…/]B…/S…/D…[/P…], с использованием нотации Хенселя.
B – перечисление количества соседей, необходимых для рождения новой клетки. С использованием нотации Хенселя каждому количеству могут быть определены конкретные шаблоны расположения соседей. Пример:
2
= 2 живых соседа в любом положении
, 2a
= 2 рядом стоящих живых соседа
, 2-a
= 2 живых соседа в любом положении, кроме a
.S – полностью аналогично B, но отвечает за количество/расположения соседей, необходимых для выживания клетки.
D – перечисление аналогично предыдущим. Определяет, какое множество переходов будет считаться временно дефицитным. Клетка, которая родилась по переходу, входящему в D, будет запрещать на следующей итерации рождение по «своему» переходу в соседних клетках. Переходом является конкретный паттерн расположения, такой как
2i
или 2a
, даже если в параметрах указан просто «количественный» вариант 2
.P – аналогично предыдущим. Определяет, какое множество переходов будет считаться перманентно дефицитным. Клетка, уже распространяющая временный дефицит, будет растягивать ограничение на всё время своей жизни, если переход её рождения входит в множество P.
Характеристики примера – [ускорение анимации от 100мс. на фрейм, если есть]; длительность анимации; размер поля; размер и процент центрального заполнения на старте.
Дефицитные ограничения распространяются только от живых клеток (в состоянии 1). «Стареющие» клетки при постоянном дефиците в нашей модификации уже не влияют на соседей, хотя этот пункт потенциально также можно расширить через определение в правиле.
Итак, с вводной закончили. Первым делом проверим, как работает наша модификация. По классике, на примере стандартного GoL.
×1.25, 25с., 237×237, 150×10% | B3/S23/D/P
Отлично, ничего не сломано, можно вносить изменения. Введём глобальное перманентное ограничение.
5 запусков, ×1.25, 12с., 237×237, 150×10% | B3/S23/D3/P3
Ожидаемо, остались лишь натюрморты, включая невозможные на обычном B3/S23. Для возвращения некоторого количества жизни в нашу «Жизнь» можно отключить ограничения ai. В параметре P это вернёт глайдеры, а в параметре D к ним ещё добавятся трёхклеточные пропеллеры.
×1.25, 11с., 237×237, 150×10% | B3/S23/D3/P3-ai
×1.25, 12с., 237×237, 150×10% | B3/S23/D3-ai/P3[-ai]
Конечно же, подавляющее большинство описанных пользователями дефицитных правил являются вариациями GoL. Один из примеров, с взрывными репликаторами:
×1.25, 37с., 237×237, 150×10% | B34a/S234cet/D34[a]
Правила с временным дефицитом чаще обычного оказываются несколько мерцающими, когда клетки не порождают новую жизнь по своему образу и подобию, из-за ограничений в соответствии с конфигурацией, но и им самим не хватает соседей для выживания. Это запускает бесконечный цикл смертей и перерождений, который, конечно, часто встречается и на стандартной конфигурации, но здесь модификация дополнительно способствует подобному поведению. Однотипный же, на первый взгляд, рост, возможен в случае чередования паттернов.
29с., 237×237, 150×20% | B1e2e/S1-e2ckai3-e4-e/D1[e]2[e]
Обрезан каждый второй кадр, 15с., 237×237, 150×20% | B1e2e/S1-e2ckai3-e4-e/D1[e]2[e]
Казалось бы, дефицит должен был не допустить такие однотипные конструкции, но если присмотреться к «головам» строителей, мы увидим, что в первую итерацию они рождаются по переходу 2c и 2e , а во вторую – по 3i и 3a , за счёт чего и происходит движение. В то же время в центре остаётся множество клеток застрявших в своём цикле перерождений. aren't we all?
Если убрать у этого примера условие выживания 4-e получим довольно интересный совмещённый вид:
39с., 237×237, 150×20% | B1e2e/S1-e2ckai3-e/D1[e]2[e]
Когда перерождение выходит за пределы одиночных отростков, оно может породить интересные осцилляторы «звёздного» вида:
75с., 237×237, 150×5% | B24c678/S3ai4ert5er/D24[c]678
×1.25, 80с., 237×237, 150×5% | B2/S34678/D2
Говоря о мерцающих примерах, нельзя не упомянуть правило с одними из самых необычных кораблей-вихрей.
x1.5, 71с., 237×237, 150×5% | B1c2aen/S1/D1[c]2[aen]/P1[c]
Хотел бы оставить за спойлером обрезанную версию, но из-за периода кораблей резать пришлось много.
x1.5, 18с., 237×237, 150×5% | B1c2aen/S1/D1[c]2[aen]/P1[c]
Дефицит можно использовать точечно, для коррекции поведения правила. К примеру на правиле B2/S3-a45678/D мы увидим стандартный разрастающийся во все стороны шаблон. Добавив D2e в наше правило, мы существенно изменим его начальное поведение:
x1.5, 20с., 237×237, 2×100% | B2/S3-a45678/D2е
И это, конечно же, не эквивалентно ограничению рождения 2-e.
x1.5, 19с., 237×237, 2×100% | B2/S3-a45678/D
x1.5, 23с., 237×237, 2×100% | B2-e/S3-a45678/D
И немного посмотрим на правила с поколениями. Комбинация этих расширений не добавляет каких-то особенностей, сверх напрямую отнаследованных от них.
×2, 62с., 237×237, 150×5% | G3/B2/S345678/D2
Если убрать у последнего примера выживание при 5 соседях, можно получить корабль-псевдорепликатор. Весьма уникальное поведение:
×1.5, 43с., 237×237, 150×5% | G3/B2/S34678/D2
Ещё один пример точечного дефицита для небольшой коррекции.
×2, 56с., 237×237, 2×50% | G3/B2/S/D2-ikea
И напоследок – цикличные треугольники Серпинского с превью, на большем поле:
×1.5, 44с., 1005×1005, 2×50% | G3/B24c678/S3ai4ert5er/D2ce
51с., 237×237, 150×7% | G3/B25-acei/S1/D2a5
×1.5, 29с., 237×237, 100×2% | B3/S012345678/D3
1/4, ×1.5, 11с., 237×237, 100×20% | B1e2i/S01/D1e
×1.5, 42с., 237×237, 100×20% | B1e2i/S01/D1e
- Базовая «life-like» конфигурация
- Старение клеток: параметр поколений
- Нотация Хенселя: учёт расположения соседей
- LtL: расширенный радиус поиска соседей
- Циклические клеточные автоматы
- Альтернативные окрестности и HROT
- Блочные КА, окрестность Марголуса
- Взвешенные окрестности, окрестность Гаусса, Far Corners/Edges
- Направленные и пользовательские окрестности
- Клетки-киллеры, BSFK[L]
- Deficient rules (вы здесь)
- Моделирование лесных пожаров: теория, клеточный автомат на Python
- Сегрегация общества: модель Шеллинга и распределение этнических групп в городах Израиля
Прочее:
- 🟢 История моделирования лесных пожаров
- 🟠 REcollapse: фаззинг с использованием unicode-нормализации
- 🔵 Хватит использовать [a-zа-яё]: правильная работа с символами и категориями Unicode в регулярных выражениях
- 🟢 Краткая история календаря и фантазии о шестидневной неделе
- 🟢 Пройти LeetCode за год: экскурсия по сайту и roadmap
Автор:
TLHE