![](https://habrastorage.org/webt/qq/4v/b9/qq4vb9tdkcmlxawyixs_dwg74jk.gif)
?, Хабр!
Сегодня мы снова немного отойдём от классической модели, и будем строить конфигурацию с самого начала, благо, никаких сложностей в этом нет. Сегодняшняя конфигурация – блочные КА – предполагает, что наша сетка разбивается на некоторые участки, собственно, блоки, для которых заранее определены инструкции перехода. Никаких вариаций – один шаблон перехода для одного шаблона расположения. Звучит так, будто мы получим набор бессвязных осцилляторов, верно? Но у конфигурации есть второе условие: каждый шаг происходит смещение сетки разбиения, за счёт чего клетки при каждой следующей итерации относятся к новому блоку. Лучше, конечно, на примере.
Самой популярной моделью построения блочных КА является разбиение на блоки 2×2, со смещением на 1 клетку по диагонали за итерацию. Данная модель носит имя своего первого и основного исследователя, пионера изучения КА – Нормана Марголуса. Хоть сам вид и называют окрестностью Марголуса, он несколько отличается логически от тех окрестностей, что мы с вами обозревали ранее. А именно: данная окрестность отображает сразу оба возможных состояния, и она не привязана ни к какой конкретной клетке. Есть разные представления на изображении. Одно из них:
![](https://habrastorage.org/webt/lc/j4/uw/lcj4uwn0mkjihqdv2-dwrb8fbzg.png)
Синими линиями формируются блоки на чётных итерациях, красными пунктирами – на нечётных
Как и в случае с альтернативными окрестностями, данный раздел КА также весьма скудно исследован (данное утверждение будет становиться только актуальнее, чем дальше мы будем отходить от стандартной модели), и окрестность Марголуса является чуть ли не единственной признанной на всей конфигурации. Тем не менее, это не значит, что нам не найдётся на что посмотреть.
❯ Вводная
В общем виде, каждое правило вида содержит в себе некоторое количество инструкций перехода в одномерном представлении, вроде
0, 0, 0, 0: 1, 1, 1, 1
(=блок со всеми пустыми клетками становится полностью заполненным).Кроме набора инструкций также уточняется, нужны ли повороты инструкций и их отражения по горизонтали и вертикали. Это позволяет сократить описания, например, сделав эквивалентными
1, 0, 0, 0: 0, 1, 0, 0
и 0, 1, 0, 0: 1, 0, 0, 0
горизонтальным отражением.Также, для сокращения количества описываемых инструкций, отдельные значения клеток могут быть заменены переменными, то есть принимать любое значение.
Пример:
0, 0, 0, 0: 0, 0, 1, 1
и 1, 0, 0, 0: 1, 0, 1, 1
заменяются на a, 0, 0, 0: a, 0, 1, 1
Стоит упомянуть, что блочные КА являются обратимыми, то есть мы, зная текущее состояние поля и инструкции перехода, можем шаг за шагом восстанавливать предыдущие состояния.
❯ 1. Бильярд
Начнём с не самого простого примера, но на нём мы хорошо закрепим понимание данной конфигурации. Billiard Ball Machine.
Правило определено двумя переходами с поворотной симметрией, и, как и большинство правил конфигурации, требует определённого стартового состояния.
Симметрия: поворот
1, 0, 0, 0: 0, 0, 0, 1
1, 0, 0, 1: 0, 1, 1, 0
![](https://habrastorage.org/webt/sz/3_/pz/sz3_pz9cm-cfj8ptsffjulox4xg.gif)
18с., скорость 3, 112×112
У вас может возникнуть вопрос – «А почему «шары» правильно рикошетят? Мы ведь не задаём никакого направления, известно только текущее состояние». Секрет во второй инструкции, и в том, что наши «шары» состоят из двух клеток. Немного замедлим анимацию:
![](https://habrastorage.org/webt/u7/y2/s-/u7y2s-zyckureuuvkxkubuu4az8.gif)
10с., скорость 0.2, 112×112
Давайте нарушим стартовое состояние: внешний шар сдвинем на одну клетку выше, у первого внутреннего уберём одну клетку, а для второго шара придвинем клетки ближе друг к другу.
![](https://habrastorage.org/webt/qt/kv/2l/qtkv2lfsfozrbvhivov1s7ekl9s.gif)
12с., 112×112
Всё, ожидаемо, сломалось. Возможно, у вас возник новый вопрос – «Хорошо, а почему отдельные клетки вообще отскакивают в ту же сторону, откуда и прилетели?».
Тут суть в самой конфигурации – клетка, которая изменилась по переходу
1, 0, 0, 0: 0, 0, 0, 1
не может оказаться в другом блоке на второй или третьей позициях, она всегда будет на позициях 1 и 4, и будет следовать переходам по этой диагонали. И наоборот – клетка на позициях 2 и 3 по этому переходу (Симметрия: поворот
) всегда будет на них же.Обилие линий на изображении окрестности может скрыть от вас эту контринтуитивную особенность, которая является крайне важной при реализации алгоритма и составлении фигур. Взгляните на изображение ещё раз (продублировано ниже, под спойлером). Из-за того, что мы с каждой итерацией смещаемся по диагонали, блоков со стартовыми клетками на позициях x+1 или y+1 попросту не существует. Другими словами, существуют только те блоки, у которых сумма позиций по обеим осям у стартовых клеток чётная.
Что же, можно считать, что мы разобрались с конфигурацией. Теперь можем насладиться прочими примерами.
❯ 2. Песок
Одно из самых популярных правил конфигурации моделирует поведение клеток-песчинок, пусть и с некоторыми допущениями.
Симметрия: отражение по горизонтали
1, 1, 0, 0: 0, 0, 1, 1
1, a, 0, b: 0, a, 1, b
1, 0, a, 0: 0, 0, a, 1
3, a, 0, b: 3, a, 1, b
В данном правиле предполагается 4 состояния: 0 – пустая клетка; 1 – песчинка; 2 – неподвижные клетки, которыми мы можем создавать поверхности для песка; 3 – бесконечный источник песка.
![](https://habrastorage.org/webt/j1/t-/hy/j1t-hyg2hqahr7iisvdh95tmahk.gif)
40с., скорость 1.5, 112×112
Здесь видна основная масса допущений, однако даже с ними, модель весьма близка к своему прототипу.
С бо́льшим количеством песчинок можно обнаружить ещё одну занятную особенность, когда клетки при падении собираются в линии.
![](https://habrastorage.org/webt/fe/3s/vs/fe3svsfao4nhcn_v65ko6rrjtei.gif)
28с., скорость 1.5, 224×224; Случайное заполнение (20%)
❯ 3. Diffusion Limited Aggregation
Симметрия: отражения + поворот
1, 0, 0, 0: 0, 0, 0, 1
1, 1, 0, 0: 1, 1, 0, 0
0, 1, 1, 0: 1, 0, 0, 1
1, 1, 1, 0: 1, 1, 0, 1
1, 0, 2, 0: 2, 0, 2, 0
1, 0, 2, 2: 2, 0, 2, 2
Переходы для состояния 1 могут напомнить бильярдное правило, с парой модификаций:
![](https://habrastorage.org/webt/r7/rn/lm/r7rnlmduk03tjf3f-cfuki9ioxk.gif)
13с., 112×112; Случайное заполнение (5%)
Но основной интерес к правилу вызывают клетки во втором состоянии, благодаря которым возникает рост, схожий со многими природными процессами:
![](https://habrastorage.org/webt/lz/7j/um/lz7jum6jxdnth6ukyprutruqopg.gif)
32с., 112×112; Случайное заполнение (60%) + центральная клетка во втором состоянии
❯ 4. Toothpick sequence
Одно из простейших правил, с единственным переходом: в каждом блоке, с единственной заполненной клеткой, также заполняются и смежные.
Симметрия: поворот
1, 0, 0, 0: 1, 1, 1, 0
![](https://habrastorage.org/webt/fz/8r/0k/fz8r0kdht4o_obzjd-llcn3sc7i.gif)
15с., 224×224; Две стартовые клетки по диагонали
672×672
![](https://habrastorage.org/webt/fq/ym/g9/fqymg9vgcphcarxseypbjppggxc.gif)
❯ 5. Tron
Классическое правило конфигурации. Инструкции перехода ещё проще «зубочисток» – все пустые блоки заполняются, и наоборот. Никакие симметрии, конечно, не понадобятся.
Правило очень мерцающее, поэтому на анимациях убран каждый второй фрейм. Оригинальный вид оставим под спойлером.
![](https://habrastorage.org/webt/et/_q/wq/et_qwqb0dp9bgekk22v8seto89m.gif)
15с., 112×112; Заполненный центральный блок 27×27
![](https://habrastorage.org/webt/in/gk/j-/ingkj-jvldavbnwa_iewjvsu9k8.gif)
57с., 224×224; Заполненные блоки 6×6, 2×2 и 2×2
Мерцание
Раз уж вы сюда заглянули, давайте сразу покажу полностью случайное распределение (3%)
![](https://habrastorage.org/webt/fv/xg/ed/fvxgedaakywretizlhisxdnbkmu.gif)
17с., 224×224
Ну а теперь оригиналы анимаций над спойлером:
![](https://habrastorage.org/webt/v3/zu/5i/v3zu5igmscrzhwiy1uwkiegyvue.gif)
27с., 112×112
![](https://habrastorage.org/webt/vi/q9/nd/viq9ndrpzhtkd_wtcee5zovylhw.gif)
55с., 224×224
![](https://habrastorage.org/webt/fv/xg/ed/fvxgedaakywretizlhisxdnbkmu.gif)
17с., 224×224
Ну а теперь оригиналы анимаций над спойлером:
![](https://habrastorage.org/webt/v3/zu/5i/v3zu5igmscrzhwiy1uwkiegyvue.gif)
27с., 112×112
![](https://habrastorage.org/webt/vi/q9/nd/viq9ndrpzhtkd_wtcee5zovylhw.gif)
55с., 224×224
Поведение, которое можно видеть на границах примера, вызвано нецикличной сеткой. Если связать границы, вид существенно изменится:
![](https://habrastorage.org/webt/v-/bj/3f/v-bj3falzb5lwsrdn6_ejeam_98.gif)
25с., 224×224
Мерцание
![](https://habrastorage.org/webt/8g/-h/9i/8g-h9ixzelrxphjh1jmkd_6cm2y.gif)
40с., 224×224
![](https://habrastorage.org/webt/8g/-h/9i/8g-h9ixzelrxphjh1jmkd_6cm2y.gif)
40с., 224×224
❯ 6. Криттеры
Развитие инструкций Tron'а привело к появлению правила Critters, интересного своими планерами.
Симметрия: поворот
0, 0, 0, 0: 1, 1, 1, 1
0, 0, 0, 1: 1, 1, 1, 0
0, 1, 1, 1: 1, 0, 0, 0
1, 1, 1, 1: 0, 0, 0, 0
Планеры на этом правиле очень устойчивы. Они могут проходить друг через друга без повреждений, с разным смещением, менять направление полёта, а если и будут повреждены, могут восстановиться следующим столкновением. Так как в основе лежат правила Tron'а, анимация опять мерцающая, и опять сокращена вдвое.
![](https://habrastorage.org/webt/qq/ec/b1/qqecb1dqcd-nctjxzm_j9khoekk.gif)
56с., 224×224, 50×40%
Мерцание
![](https://habrastorage.org/webt/ri/cw/yo/ricwyoh7bmdswrbfjb2ylrh70ke.gif)
56с., 224×224, 50×60%
![](https://habrastorage.org/webt/ri/cw/yo/ricwyoh7bmdswrbfjb2ylrh70ke.gif)
56с., 224×224, 50×60%
❯ 7. Rotations
Ещё одно простое правило, порождающее «путешественников».
Симметрия: поворот
1, 0, 0, 0: 0, 1, 0, 0
![](https://habrastorage.org/webt/c5/mw/em/c5mwemthnnz_3rfqay-osmbxf4a.gif)
59с., 112×112
❯ 8. M0,2,8,12,1,10,9,11,4,6,5,14,3,7,13,15
Под конец познакомимся с ещё одним вариантом описания переходов.
Для блочных КА с двумя состояниями, расположения могут быть представлены как бинарные числа и в этом случае может использоваться упрощённая запись
M0,1,2,…,14,15
, где индекс обозначает изначальное расположение, а значение по индексу – шаблон расположения после перехода. Например M15,1,2,…,14,15
будет соответствовать правилу с единственной инструкцией «все пустые -> все заполненные», без обратного перехода.Этот вариант достаточно компактен, но, к сожалению, не универсален.
Вернёмся к правилу.
M0,2,8,12,1,10,9,11,4,6,5,14,3,7,13,15
. Как вы видите, всего два значения остались на своих позициях, а остальная часть изменилась. В явной записи с сокращением симметрией это бы выглядело следующим образом:Симметрия: поворот
1, 0, 0, 0: 0, 1, 0, 0
1, 1, 0, 0: 0, 0, 1, 1
0, 1, 1, 0: 1, 0, 0, 1
1, 1, 1, 0: 1, 1, 0, 1
На этом правиле можно найти много разных любопытных фигур.
![](https://habrastorage.org/webt/dd/gl/z_/ddglz_4m3ddhgsmwis9lzaz2h0e.gif)
17с., скорость 5, 112×112
![](https://habrastorage.org/webt/o2/0t/fa/o20tfays10ijfqwhpnwqn-0q2mk.gif)
12с., скорость 3, 224×224
❯ 9. M0,14,13,0,11,0,0,0,7,0,0,0,0,0,0,0
Занимательное правило, как по виду, так и по переходам: мы сохраняем переходы всего для четырёх расположений с одной заполненной клеткой, инвертируя состояние блока, и сбрасываем все остальные расположения к пустым блокам. Ну а в результате получаем орнаментно-фрактальные виды, с большой зависимостью от стартового состояния.
![](https://habrastorage.org/webt/bh/fg/6q/bhfg6q-gviycskgu4x2izjazop8.gif)
33с., 672×672
![](https://habrastorage.org/webt/wj/ua/5u/wjua5uo8xe2nvzpxwxfvlct-4kc.gif)
30с., 672×672
![](https://habrastorage.org/webt/lg/mw/b6/lgmwb611orzz4p4waglk_u0q-ni.gif)
27с., 672×672
❯ 10. M0,1,2,3,4,10,6,11,8,9,5,13,12,14,7,15
И закончим сегодняшний обзор занятным колебательным правилом.
![](https://habrastorage.org/webt/8p/oy/no/8poyno0gzyfjgjxm9o0jjotbocm.gif)
35с., 112×112
Другие фигуры, конечно, тоже возможны.
![](https://habrastorage.org/webt/xd/s5/rk/xds5rkivbchfvgtl1rnhc1z8qds.gif)
21с., 112×112
И на сегодня всё. Увидимся через неделю!
Читайте также
О клеточных автоматах:
Прочее:
- Базовая «life-like» конфигурация
- Старение клеток: параметр поколений
- Нотация Хенселя: учёт расположения соседей
- LtL: расширенный радиус поиска соседей
- Циклические клеточные автоматы
- Альтернативные окрестности и HROT
- Блочные КА: окрестность Марголуса (вы здесь)
- Взвешенные окрестности, окрестность Гаусса, Far Corners/Edges
- Направленные и пользовательские окрестности
- Клетки-киллеры, BSFK[L]
- Дефицитные правила
- Обратные и расширенные поколения
- Моделирование лесных пожаров: теория, клеточный автомат на Python
- Сегрегация общества: модель Шеллинга и распределение этнических групп в городах Израиля
Прочее:
- ? История моделирования лесных пожаров
- ? REcollapse: фаззинг с использованием unicode-нормализации
- ? Хватит использовать [a-zа-яё]: правильная работа с символами и категориями Unicode в регулярных выражениях
- ? Краткая история календаря и фантазии о шестидневной неделе
- ? Пройти LeetCode за год: экскурсия по сайту и roadmap
← Предыдущая часть | Следующая часть →
![](https://habrastorage.org/webt/b5/pj/of/b5pjofdoxth14ro-rjsrn7sbmiy.png)