Pull to refresh
1359.48
Timeweb Cloud
То самое облако

Удивительные клеточные автоматы: дефицитные правила

Level of difficultyEasy
Reading time6 min
Views4.2K


👾, Хабр!

Возвращаемся к нашей экскурсии по модификациям клеточных автоматов. Объект сегодняшнего внимания – дефицитные правила (deficient rules). Это ещё более свежая вариация, чем рассмотренный в прошлом посте BSFKL, и была описана 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…], с использованием нотации Хенселя.

:h Параметры
G – количество состояний клеток. Минимум – 2 (жива/мертва), бо́льшие значения отвечают за длительность «старения» клетки, когда она уже не считается живым соседом для прочих клеток, но ещё не освободила клетку для рождения новой.
B – перечисление количества соседей, необходимых для рождения новой клетки. С использованием нотации Хенселя каждому количеству могут быть определены конкретные шаблоны расположения соседей. Пример: 2 = 2 живых соседа в любом положении, 2a = 2 рядом стоящих живых соседа, 2-a = 2 живых соседа в любом положении, кроме a.
S – полностью аналогично B, но отвечает за количество/расположения соседей, необходимых для выживания клетки.
D – перечисление аналогично предыдущим. Определяет, какое множество переходов будет считаться временно дефицитным. Клетка, которая родилась по переходу, входящему в D, будет запрещать на следующей итерации рождение по «своему» переходу в соседних клетках. Переходом является конкретный паттерн расположения, такой как 2i или 2a, даже если в параметрах указан просто «количественный» вариант 2.
P – аналогично предыдущим. Определяет, какое множество переходов будет считаться перманентно дефицитным. Клетка, уже распространяющая временный дефицит, будет растягивать ограничение на всё время своей жизни, если переход её рождения входит в множество P.

Характеристики примера – [ускорение анимации от 100мс. на фрейм, если есть]; длительность анимации; размер поля; размер и процент центрального заполнения на старте.

Дефицитные ограничения распространяются только от живых клеток (в состоянии 1). «Стареющие» клетки при постоянном дефиците в нашей модификации уже не влияют на соседей, хотя этот пункт потенциально также можно расширить через определение в правиле.

Итак, с вводной закончили. Первым делом проверим, как работает наша модификация. По классике, на примере стандартного GoL.

B3/S23/D/P | ×1.25, 25с., 237×237, 150×10%
×1.25, 25с., 237×237, 150×10% | B3/S23/D/P

Отлично, ничего не сломано, можно вносить изменения. Введём глобальное перманентное ограничение.

B3/S23/D3/P3 | 5 запусков, ×1.25, 12с., 237×237, 150×10%
5 запусков, ×1.25, 12с., 237×237, 150×10% | B3/S23/D3/P3

Ожидаемо, остались лишь натюрморты, включая невозможные на обычном B3/S23. Для возвращения некоторого количества жизни в нашу «Жизнь» можно отключить ограничения ai. В параметре P это вернёт глайдеры, а в параметре D к ним ещё добавятся трёхклеточные пропеллеры.

B3/S23/D3/P3-ai | ×1.25, 11с., 237×237, 150×10%
×1.25, 11с., 237×237, 150×10% | B3/S23/D3/P3-ai

B3/S23/D3-ai/P3[-ai] | ×1.25, 12с., 237×237, 150×10%
×1.25, 12с., 237×237, 150×10% | B3/S23/D3-ai/P3[-ai]

Конечно же, подавляющее большинство описанных пользователями дефицитных правил являются вариациями GoL. Один из примеров, с взрывными репликаторами:

B34a/S234cet/D34[a] | ×1.25, 37с., 237×237, 150×10%
×1.25, 37с., 237×237, 150×10% | B34a/S234cet/D34[a]

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

B1e2e/S1-e2ckai3-e4-e/D1[e]2[e] | 29с., 237×237, 150×20%
29с., 237×237, 150×20% | B1e2e/S1-e2ckai3-e4-e/D1[e]2[e]
Сглаженный вариант
B1e2e/S1-e2ckai3-e4-e/D1[e]2[e] | Обрезан каждый второй кадр, 15с., 237×237, 150×20%
Обрезан каждый второй кадр, 15с., 237×237, 150×20% | B1e2e/S1-e2ckai3-e4-e/D1[e]2[e]

Казалось бы, дефицит должен был не допустить такие однотипные конструкции, но если присмотреться к «головам» строителей, мы увидим, что в первую итерацию они рождаются по переходу 2c 2c и 2e 2e, а во вторую – по 3i 3i и 3a 3a, за счёт чего и происходит движение. В то же время в центре остаётся множество клеток застрявших в своём цикле перерождений. aren't we all?

Если убрать у этого примера условие выживания 4-e получим довольно интересный совмещённый вид:

B1e2e/S1-e2ckai3-e/D1[e]2[e] | 39с., 237×237, 150×20%
39с., 237×237, 150×20% | B1e2e/S1-e2ckai3-e/D1[e]2[e]

Когда перерождение выходит за пределы одиночных отростков, оно может породить интересные осцилляторы «звёздного» вида:

B24c678/S3ai4ert5er/D24[c]678 | 75с., 237×237, 150×5%
75с., 237×237, 150×5% | B24c678/S3ai4ert5er/D24[c]678

B2/S34678/D2 | ×1.25, 80с., 237×237, 150×5%
×1.25, 80с., 237×237, 150×5% | B2/S34678/D2

Говоря о мерцающих примерах, нельзя не упомянуть правило с одними из самых необычных кораблей-вихрей.
Мерцание
B1c2aen/S1/D1[c]2[aen]/P1[c] |×1.5, 71с., 237×237, 150×5%
x1.5, 71с., 237×237, 150×5% | B1c2aen/S1/D1[c]2[aen]/P1[c]

Хотел бы оставить за спойлером обрезанную версию, но из-за периода кораблей резать пришлось много.
B1c2aen/S1/D1[c]2[aen]/P1[c] |×1.5, 18с., 237×237, 150×5%
x1.5, 18с., 237×237, 150×5% | B1c2aen/S1/D1[c]2[aen]/P1[c]

Дефицит можно использовать точечно, для коррекции поведения правила. К примеру на правиле B2/S3-a45678/D мы увидим стандартный разрастающийся во все стороны шаблон. Добавив D2e в наше правило, мы существенно изменим его начальное поведение:

B2/S3-a45678/D2е |×1.5, 20с., 237×237, 2×100%
x1.5, 20с., 237×237, 2×100% | B2/S3-a45678/D2е

И это, конечно же, не эквивалентно ограничению рождения 2-e.
B2/S3-a45678/D
B2/S3-a45678/D |×1.5, 19с., 237×237, 2×100%
x1.5, 19с., 237×237, 2×100% | B2/S3-a45678/D
B2-e/S3-a45678/D
B2-e/S3-a45678/D |×1.5, 23с., 237×237, 2×100%
x1.5, 23с., 237×237, 2×100% | B2-e/S3-a45678/D

И немного посмотрим на правила с поколениями. Комбинация этих расширений не добавляет каких-то особенностей, сверх напрямую отнаследованных от них.

G3/B2/S345678/D2 | ×2, 62с., 237×237, 150×5%
×2, 62с., 237×237, 150×5% | G3/B2/S345678/D2

Если убрать у последнего примера выживание при 5 соседях, можно получить корабль-псевдорепликатор. Весьма уникальное поведение:

G3/B2/S34678/D2 | ×1.5, 43с., 237×237, 150×5%
×1.5, 43с., 237×237, 150×5% | G3/B2/S34678/D2

Ещё один пример точечного дефицита для небольшой коррекции.

G3/B2/S/D2-ikea | ×2, 56с., 237×237, 2×50%
×2, 56с., 237×237, 2×50% | G3/B2/S/D2-ikea

И напоследок – цикличные треугольники Серпинского с превью, на большем поле:

G3/B24c678/S3ai4ert5er/D2ce | ×1.5, 44с., 1005×1005, 2×50%
×1.5, 44с., 1005×1005, 2×50% | G3/B24c678/S3ai4ert5er/D2ce

2029×2029.png
G3/B24c678/S3ai4ert5er/D2ce | 2029×2029, 2×50%

Бонус
G3/B25-acei/S1/D2a5 | 51с., 237×237, 150×7%
51с., 237×237, 150×7% | G3/B25-acei/S1/D2a5

B3/S012345678/D3 | ×1.5, 29с., 237×237, 100×2%
×1.5, 29с., 237×237, 100×2% | B3/S012345678/D3

B1e2i/S01/D1e | 1/4, ×1.5, 11с., 237×237, 100×20%
1/4, ×1.5, 11с., 237×237, 100×20% | B1e2i/S01/D1e
Мерцающий оригинал
B1e2i/S01/D1e | ×1.5, 42с., 237×237, 100×20%
×1.5, 42с., 237×237, 100×20% | B1e2i/S01/D1e



Читайте также
О клеточных автоматах:
  1. Базовая «life-like» конфигурация
  2. Старение клеток: параметр поколений
  3. Нотация Хенселя: учёт расположения соседей
  4. LtL: расширенный радиус поиска соседей
  5. Циклические клеточные автоматы
  6. Альтернативные окрестности и HROT
  7. Блочные КА, окрестность Марголуса
  8. Взвешенные окрестности, окрестность Гаусса, Far Corners/Edges
  9. Направленные и пользовательские окрестности
  10. Клетки-киллеры, BSFK[L]
  11. Дефицитные правила (вы здесь)
  12. Обратные и расширенные поколения

Прочее:

← Предыдущая часть | Следующая часть →

Tags:
Hubs:
Total votes 43: ↑43 and ↓0+43
Comments13

Articles

Information

Website
timeweb.cloud
Registered
Founded
Employees
201–500 employees
Location
Россия
Representative
Timeweb Cloud