????, Хабр!

На прошлой неделе мы снова расширили классическую «life-like» модель, добавив к ней параметр радиуса поиска соседей. Сегодня немного отойдём от этого вида и заглянем в область прочих конфигураций. Начнём с циклических КА.

Отличия конфигурации


Давайте вспомним, что лежит в основе всех рассмотренных нами ранее конфигураций:

  • Клетка может быть пустой или заполненной;
  • Правила перехода клетки между этими состояниями определяются количеством живых соседей (заполненных, с состоянием 1).

И всё. Это наша основа, которую мы расширяли новыми характеристиками и условиями. Потому и говорили о «life-like» модели, так как все конфигурации соответствовали этим базовым правилам.

Сегодняшняя же модель вносит изменения в саму основу и выглядит следующим образом:

  • Клетки всегда заполнены и логически равны, отличается только числовое значение состояний;
  • Правила перехода определяются количеством соседей, находящихся в следующем состоянии от значения самой клетки.

Как следует из названия, состояния цикличны: следующее состояние для клетки с максимальным значением – 0.

Многие рассмотренные ранее расширения актуальны и для новой основы – мы всё так же указываем окрестность, радиус и количество состояний (ранее мы называли их поколениями). Но мы отказываемся от характеристик B и S, которыми обозначали количество соседей для рождения/выживания, а вместо них вводим одну новую – T (Threshold) – количество соседей в следующем состоянии для перехода клетки.

Общепринятой нотации для циклических КА нет. Часто параметры указывают просто в порядке «Радиус/Пороговое_значение_перехода/Количество_состояний/Тип_окрестности» без буквенных обозначений, со слешами в качестве разделителей. Воспользуемся этим вариантом записи, но сопроводим её явным буквенным обозначением параметров – R, T, G, N. В отличии от ранее рассмотренных конфигураций, в циклических КА окрестность фон Неймана (NN) используется если не чаще, то наравне с окрестностью Мура (NM).

Демоны


Согласно LifeWiki, «циклические клеточные автоматы – это класс КА, широко известных тем, что они создают спиральные узоры». И это действительно визитная карточка конфигурации.

В основе спиралей находятся, так называемые, «демоны» – завихрения бесконечно сменяющих друг друга состояний, волны от которых распространяются во все стороны от демона, создавая характерную картину.
Подробно возникновению спиралей в циклических КА посвящена отдельная статья.

Стоит отметить, что необходимо как минимум 3 состояния для появления демона. Они часто устойчивы, и на многих правилах не могут быть разрушены в принципе, защищаясь от повреждений генерируемыми волнами.

Как и жуки в LtL, демоны – преобладающие структуры на всей конфигурации.

Начнём с самого наглядного представления:

R1/T1/G14/NN
R1/T1/G14/NN

Данное правило интересно своим двойным поведением – сначала случайно сгенерированное поле расчищается однородными участками состояний, и только после этого столкновением участков образуются демоны. Здесь они представлены в своём самом явном виде, на прочих же правилах они могут быть менее оформлены, но всё ещё будут являться системообразующими.

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

R2/T2/G6/NN
R2/T2/G6/NN

Угловатость примеров выше обусловлена не только использованием окрестности фон Неймана. На обоих окрестностях можно найти как скруглённые, так и угловатые виды.

R3/T4/G5/NN
R3/T4/G5/NN

На правилах с большим количеством демонов, они могут сливаться с соседями в цепи, образуя более сложные – двойные, тройные, и более (на анимации – справа от центра) структуры:

R3/T15/G3/NM
R3/T15/G3/NM

Повышенные пороговые значения часто дают виды с «артефактами», как на примерах ниже:

R2/T9/G4/NM
R2/T9/G4/NM

R2/T5/G8/NM
R2/T5/G8/NM

На некоторых правилах можно встретить местный аналог космических кораблей, которые хвостами-линиями формируют фоновый узор:

R2/T3/G5/NN
R2/T3/G5/NN

R1/T2/G5/NM
R1/T2/G5/NM

R1/T3/G4/NM
R1/T3/G4/NM

Стабильные виды


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

R2/T5/G3/NN
R2/T5/G3/NN

R1/T2/G3/NN
R1/T2/G3/NN

R2/T11/G3/NM
R2/T11/G3/NM

Два состояния


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

R5/T23/G2/NN
R5/T23/G2/NN

R1/T4/G2/NM
R1/T4/G2/NM

R2/T5/G2/NN
R2/T5/G2/NN

Последние примеры могли напомнить вам модель сегрегации Шеллинга. Это действительно довольно близкое поведение, но с несколькими уточнениями: по Шеллингу поиск соседей происходит в одном радиусе, а поиск позиции для «переселения» – по всей сетке. У нас же оба процесса выполняются по одному радиусу. Также важно, что клетки в модели сегрегации не меняют собственное состояние, а обмениваются позициями (мы не привязаны к идентификации конкретной клетки, потому можно сказать, что клетки обмениваются состояниями), а обмен, в классическом представлении, происходит с пустой клеткой.

Модификации конфигурации


Как и с любой другой конфигурацией, мы вольны вносить любые изменения, если хотим того.

Для примера, давайте внесём модификацию в одно из рассмотренных ранее правил, и с 50% вероятностью будем недосчитываться одного соседа.

R2/T2/G6/NN

Не узнали? Это R2/T2/G6/NN, второе рассмотренное сегодня, угловатое правило. Незначительная модификация, а вид уже совершенно другой. Тут даже интересен не столько новый вид, сколько новое поведение – демоны с этой модификацией менее устойчивы: они легче разрушаются, а пока живы могут немного смещать собственный центр.

Альтернативные окрестности

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

Например, мы можем сделать периметр фон Неймана, оставив от одноимённой окрестности только внешние клетки – , что даст нам очень интересный сетчатый вид на правилах с чётным радиусом.

R4/T4/G6/NNR
R4/T4/G6/NNR

Аналогично можно изменить и окрестность Мура – . Как и с прошлой модификацией – при R1 окрестность эквивалентна стандартной.

R2/T5/G4/NMR
R2/T5/G4/NMR

Через окрестность мы можем также задать и направление смены состояний –

R5/T16/G4/NS1
R5/T16/G4/ND

Ну и напоследок, давайте попробуем придумать линейный вид: зададим в качестве окрестности только первую, последнюю и центральную вертикальные линии. А для дополнительного направления обрежем первую до середины, а последнюю от середины, включительно –

R3/T3/G5/NL
R3/T3/G5/NL

Камень-ножницы-бумага


Можно заметить, что циклический КА с тремя состояниями работает как будто по правилам всем известной игры – 3 состояния, каждое из которых «бьёт» следующее и повреждается предыдущим. В нашем случае победа над клеткой заканчивается её поглощением, а «играет» клетка сразу против группы соседей.

Однако если взглянуть на варианты этой игры с большим количеством состояний, то под циклический КА они уже не очень подходят. Но мы можем их адаптировать.

КНБ 5

R1/T3/G5/NM

Самым известным, из расширенных вариантов правил, будет игра с двумя дополнительными состояниями, в разных названиях от «огонь, вода» до «ящерица, Спок». Вне зависимости от названий, исход столкновения чередуется с каждым следующим состоянием. 0 выигрывает у 1 и 3, а проигрывает 2 и 4, и так для каждого.

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

Тут у нас есть ещё одно допущение – если победителей несколько, мы можем учитывать первого, последнего, с максимальным значением и просто случайного. В случае, если рассматриваем максимальное значение, может возникнуть дополнительный выбор первый/последний/случайный, если таких победителей несколько. Всё это тоже может влиять на вид симуляции. На примерах ниже будем использовать первого победителя.

R1/T3/G5/NM
КНБ5 – R1/T3/G5/NM

Мы получили не самый уникальный вид, хотя контуры волн имеют довольно нехарактерный вид для циклических КА. Тем не менее, это правило интересно, скорее, концептуально.

КНБ 7/9/15/25/101/…


Все дальнейшие расширения правил КНБ идут по одному шаблону – нечётное количество состояний; каждое «орудие» проигрывает следующей половине и побеждает предыдущую. Такое простое разделение на две целочисленные половины позволяет нам реализовать симуляцию для любого количества состояний.

Небольшой интерактив: на основе предыдущего абзаца предположите, что мы увидим на анимации ниже?

КНБ15 – R1/T3/G15/NM
R1/T3/G15/NM


У нас возникают демоны на трёх состояниях. И, заметьте, несмотря на то, что мы берём первого победителя, демоны всё равно приходят к структуре, где состояния клеток перепрыгивают больше трети прочих. На правилах с неустойчивыми демонами вся система, в конечном счёте, сведётся к трём победившим цветам-состояниям.

Учитывая, что каждый демон приходит к собственной комбинации, финальный вид получается достаточно разнообразным на цвета. Повторить это поведение на классических циклических КА нельзя, а значит мы нашли уникальную особенность этой модификации.

R1/T2/G101/NM
R1/T2/G101/NM




← Предыдущая часть

Комментарии (7)


  1. gsaw
    00.00.0000 00:00
    +2

    Ну вот, а под статьей про ретропричинность спрашивали, зачем кому то понадобилось бы симулировать нашу скучную жизнь. Было бы интересно послушать, о чем рассуждают клеточки в клеточном автомате.


  1. leshabirukov
    00.00.0000 00:00
    +2

    Думаю, "сетчатость" "R4/T4/G6/NNR" объясняется тем, что чётные клетки влияют только на чётные и наоборот. Поле развалилось на два независимых.


    1. TLHE Автор
      00.00.0000 00:00

      Да, если задать нечётный радиус, этот эффект пропадёт. Спасибо за дополнение.

      R3/T3/G6/NNR


  1. Mingun
    00.00.0000 00:00
    +1

    Походу сервер с картинками хабраэффект накрыл — половина анимаций просто не грузится, а вторая висит в вечной загрузке где-то на половине.


    1. TLHE Автор
      00.00.0000 00:00
      +1

      Крайне досадно вышло.

      Пересобрал анимации, где-то подрезал, где-то цвета убрал. Вроде на качестве не сильно сказалось, зато теперь бо́льшая часть на habrastorage поместилась. Теперь должно быть лучше.


      1. Mingun
        00.00.0000 00:00
        +1

        Вот это совсем другое дело. Теперь всё отображается.


  1. Krasnoarmeec
    00.00.0000 00:00
    +3

    R1/T1/G14/NN, R2/T2/G6/NN и R1/T2/G101/NM сильно напоминают кристаллы висмута:

    Hidden text