![](https://habrastorage.org/webt/lm/gd/ho/lmgdhotqlkr4vxdhcuzwwieuhbe.gif)
????, Хабр!
Возвращаемся к нашей экскурсии по модификациям клеточных автоматов. Объект сегодняшнего внимания – дефицитные правила (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…], с использованием нотации Хенселя.
B – перечисление количества соседей, необходимых для рождения новой клетки. С использованием нотации Хенселя каждому количеству могут быть определены конкретные шаблоны расположения соседей. Пример:
2
= 2 живых соседа в любом положении
, 2a
= 2 рядом стоящих живых соседа
, 2-a
= 2 живых соседа в любом положении, кроме a
S – полностью аналогично B, но отвечает за количество/расположения соседей, необходимых для выживания клетки.
D – перечисление аналогично предыдущим. Определяет, какое множество переходов будет считаться временно дефицитным. Клетка, которая родилась по переходу, входящему в D, будет запрещать на следующей итерации рождение по «своему» переходу в соседних клетках.
P – аналогично предыдущим. Определяет, какое множество переходов будет считаться перманентно дефицитным. Клетка, уже распространяющая временный дефицит, будет растягивать ограничение на всё время своей жизни, если переход её рождения входит в множество P.
Характеристики примера – [ускорение анимации от 100мс. на фрейм, если есть]; длительность анимации; размер поля; размер и процент центрального заполнения на старте.
Дефицитные ограничения распространяются только от живых клеток (в состоянии 1). «Стареющие» клетки при постоянном дефиците в нашей модификации уже не влияют на соседей, хотя этот пункт потенциально также можно расширить через определение в правиле.
Итак, с вводной закончили. Первым делом проверим, как работает наша модификация. По классике, на примере стандартного GoL.
![B3/S23/D/P | ×1.25, 25с., 237×237, 150×10%](https://habrastorage.org/webt/tu/mt/wa/tumtwaps_ytijfzfqjr4sscz6uq.gif)
×1.25, 25с., 237×237, 150×10% | B3/S23/D/P
Отлично, ничего не сломано, можно вносить изменения. Введём глобальное перманентное ограничение.
![B3/S23/D3/P3 | 5 запусков, ×1.25, 12с., 237×237, 150×10%](https://habrastorage.org/webt/7y/p5/u5/7yp5u5g8urn1zzzn3hakqhjzwcc.gif)
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%](https://habrastorage.org/webt/vk/xj/fe/vkxjfeuqttdrcfnickjds1o1ikc.gif)
×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%](https://habrastorage.org/webt/yj/zh/sq/yjzhsqf5cjv-awvgr_nf28nr2zk.gif)
×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%](https://habrastorage.org/webt/hm/oq/ft/hmoqft5x-cxpc2stlmnvbgbulw8.gif)
×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%](https://habrastorage.org/webt/lp/cv/9g/lpcv9g1egtfyhsthphqb8plj1em.gif)
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%](https://habrastorage.org/webt/tz/n-/0v/tzn-0vnchlordk5tv5k_2svcn3q.gif)
Обрезан каждый второй кадр, 15с., 237×237, 150×20% | B1e2e/S1-e2ckai3-e4-e/D1[e]2[e]
Казалось бы, дефицит должен был не допустить такие однотипные конструкции, но если присмотреться к «головам» строителей, мы увидим, что в первую итерацию они рождаются по переходу 2c
![2c](https://habrastorage.org/webt/fj/a9/8i/fja98ipanc7l7ctzxda0qbry47o.png)
![2e](https://habrastorage.org/webt/1b/8h/x5/1b8hx5zwajey-oieyvcsiijvuaw.png)
![3i](https://habrastorage.org/webt/9t/lg/1y/9tlg1y1nzelf9ufaqznnbmftjuu.png)
![3a](https://habrastorage.org/webt/_h/48/qb/_h48qb8xwxprugeu1ewpohxwdri.png)
Если убрать у этого примера условие выживания 4-e получим довольно интересный совмещённый вид:
![B1e2e/S1-e2ckai3-e/D1[e]2[e] | 39с., 237×237, 150×20%](https://habrastorage.org/webt/eq/-r/kz/eq-rkzynhivco5i-dvisbvmbg7q.gif)
39с., 237×237, 150×20% | B1e2e/S1-e2ckai3-e/D1[e]2[e]
Когда перерождение выходит за пределы одиночных отростков, оно может породить интересные осцилляторы «звёздного» вида:
![B24c678/S3ai4ert5er/D24[c]678 | 75с., 237×237, 150×5%](https://habrastorage.org/webt/ik/1r/7t/ik1r7tnh-mne0tm4deuapvgh_vq.gif)
75с., 237×237, 150×5% | B24c678/S3ai4ert5er/D24[c]678
![B2/S34678/D2 | ×1.25, 80с., 237×237, 150×5%](https://habrastorage.org/webt/xi/np/vw/xinpvwv4t55rnfh7m0cwleqyaqg.gif)
×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%](https://habrastorage.org/webt/7u/5g/qh/7u5gqhjdvv-ocq9igvztku3uymg.gif)
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%](https://habrastorage.org/webt/rp/cw/cv/rpcwcvvmxegguuacfocuj8yprjg.gif)
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%](https://habrastorage.org/webt/u1/nl/ic/u1nlicp4hbwngzjinsgzbr6amc0.gif)
x1.5, 20с., 237×237, 2×100% | B2/S3-a45678/D2е
И это, конечно же, не эквивалентно ограничению рождения 2-e.
![B2/S3-a45678/D |×1.5, 19с., 237×237, 2×100%](https://habrastorage.org/webt/tk/am/gy/tkamgy5ifrolarun134zqlet46g.gif)
x1.5, 19с., 237×237, 2×100% | B2/S3-a45678/D
![B2-e/S3-a45678/D |×1.5, 23с., 237×237, 2×100%](https://habrastorage.org/webt/t2/f7/sk/t2f7skegq9pkr7erbcjekaldcio.gif)
x1.5, 23с., 237×237, 2×100% | B2-e/S3-a45678/D
И немного посмотрим на правила с поколениями. Комбинация этих расширений не добавляет каких-то особенностей, сверх напрямую отнаследованных от них.
![G3/B2/S345678/D2 | ×2, 62с., 237×237, 150×5%](https://habrastorage.org/webt/0r/5p/le/0r5ple3o0bt0yhr5zifzccejjnu.gif)
×2, 62с., 237×237, 150×5% | G3/B2/S345678/D2
Если убрать у последнего примера выживание при 5 соседях, можно получить корабль-псевдорепликатор. Весьма уникальное поведение:
![G3/B2/S34678/D2 | ×1.5, 43с., 237×237, 150×5%](https://habrastorage.org/webt/zx/rb/jt/zxrbjthglybetqgaqkwatb5wp4k.gif)
×1.5, 43с., 237×237, 150×5% | G3/B2/S34678/D2
Ещё один пример точечного дефицита для небольшой коррекции.
![G3/B2/S/D2-ikea | ×2, 56с., 237×237, 2×50%](https://habrastorage.org/webt/3w/12/pr/3w12pru7x4lj6ebk_pnhvxdgtok.gif)
×2, 56с., 237×237, 2×50% | G3/B2/S/D2-ikea
И напоследок – цикличные треугольники Серпинского с превью, на большем поле:
![G3/B24c678/S3ai4ert5er/D2ce | ×1.5, 44с., 1005×1005, 2×50%](https://habrastorage.org/webt/v5/54/6w/v5546whbvnibo4kl6arkycj6eru.gif)
×1.5, 44с., 1005×1005, 2×50% | G3/B24c678/S3ai4ert5er/D2ce
![G3/B24c678/S3ai4ert5er/D2ce | 2029×2029, 2×50%](https://habrastorage.org/webt/hh/ow/ew/hhowews2bvxjoiycj3-rnlbhcoi.png)
![G3/B25-acei/S1/D2a5 | 51с., 237×237, 150×7%](https://habrastorage.org/webt/pb/pz/10/pbpz10bxdrwzyzhbldbumkzt7zo.gif)
51с., 237×237, 150×7% | G3/B25-acei/S1/D2a5
![B3/S012345678/D3 | ×1.5, 29с., 237×237, 100×2%](https://habrastorage.org/webt/ql/8d/hj/ql8dhjyxa2kutzde2_nug_uudic.gif)
×1.5, 29с., 237×237, 100×2% | B3/S012345678/D3
![B1e2i/S01/D1e | 1/4, ×1.5, 11с., 237×237, 100×20%](https://habrastorage.org/webt/rq/y6/uv/rqy6uvdjfs3ms_yeq02k6eyawtw.gif)
1/4, ×1.5, 11с., 237×237, 100×20% | B1e2i/S01/D1e
![B1e2i/S01/D1e | ×1.5, 42с., 237×237, 100×20%](https://habrastorage.org/webt/wp/kr/yy/wpkryyycmtaw0tnhinwp-nedby8.gif)
×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
← Предыдущая часть | Следующая часть (TBA) →
![](https://habrastorage.org/webt/mx/ua/nb/mxuanbovcusqgmqdgugvpnql8vq.jpeg)
Комментарии (11)
moffvrn
20.09.2023 10:59+7Увлекательный цикл. Начинался с темы "пятничные клеточные автоматы" но потом всё реже и реже - видимо это для души...
TLHE Автор
20.09.2023 10:59+1Спасибо.
Да, поначалу еженедельный формат бодро пошёл. Хотел так до конца серии и довести, но не вышло. Последняя запланированная треть уже в вольном режиме.
Vitter
20.09.2023 10:59+1Автор, вы с таким интересом стали перечислять различные виды новых паттернов клеточных автоматов, что напрочь забыли описать .... сами новые правила.
Например В3 - правило для "мёртвых" клеток, у которых ровно 3 живых соседа стают живыми.
S23 - правило для живых клеток у которых 2 или 3 живых соседа выживают, и становятся мёртвыми в остальных случаях.
А что означает D3 или P3 - непонятно вообще никак!TLHE Автор
20.09.2023 10:59+1Добавил спойлер ":h Параметры". Надеюсь, с ним новым читателям будет чуть проще.
Vitter
20.09.2023 10:59спасибо, проще стало!
Но всё ещё непонятноОпределяет, какое множество переходов будет считаться временно дефицитным. Клетка, которая родилась по переходу, входящему в D, будет запрещать на следующей итерации рождение по «своему» переходу в соседних клетках.
То есть если клетка родилась по правилу B3, и если в это же время есть правило D3, то родившеся клетка на следующем ходу на всех соседей блокирует правило B3?
. Определяет, какое множество переходов будет считаться перманентно дефицитным. Клетка, уже распространяющая временный дефицит, будет растягивать ограничение на всё время своей жизни, если переход её рождения входит в множество P.
То есть если клетка родилась по правилу B3, и если в это же время есть правило Р3, то родившеся клетка пока жива на всех соседей блокирует правило B3?
leshabirukov
20.09.2023 10:59+1треугольник Серпинского
Он же Элементарный клеточный автомат — Википедия (wikipedia.org) , правило 90. Имеем двумерный КА, сохраняющий историю одномерного. Нельзя ли в данной механике сделать то же самое для других правил (к примеру 110)? Если нельзя, то можно ли промоделировать правило 90 с другой стартовой строкой?
TLHE Автор
20.09.2023 10:59+1Не уверен, можно ли тут делать равенство. Финальный вид похож, хоть и не идентичен, но получен совершенно другой логикой.
Элементарные КА можно переложить через обычную конфигурацию с направленной пользовательской окрестностью, но всё равно придётся явно обозначать каждый переход рождения (в тоталистичной нотации получится повторить лишь 16). В анизотропных конфигурациях можно только найти схожие симметричные виды, но как это сделать без перебора не подскажу.
dlinyj
Всегда с удовольствием читаю этот цикл статей. Очень круто и интересно. Подскажите, это какая-то научно-исследовательская работа или это просто для души?
TLHE Автор
Рад, что нравится.
Для души. Просто нахожу эту область крайне интересной, а на Хабре, да и в интернете в целом, она почти не освещена (не считая «жизни» Конвея, конечно, о ней-то материала хватает). Вот и решил немного исправить ситуацию и заинтересовать новых людей. А раз эта серия ещё и тёплый отклик получает, то и просто, как автору, приятно.
dlinyj
Спасибо, продолжайте ещё!