Удивительные клеточные автоматы: направленные и пользовательские окрестности / forpes.ru

Главная
Удивительные клеточные автоматы: направленные и пользовательские окрестности

Удивительные клеточные автоматы: направленные и пользовательские окрестности +43

22.04.2023 08:01

TLHE 7 2200 Источник

????, Хабр!

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

Что здесь происходит (для новых читателей серии)

В этой серии мы разбираем клеточные автоматы – дискретную модель, основой которой является сетка из ячеек-клеток, которые изменяют (или не изменяют) своё состояние в зависимости от количества соседей.
Учёт соседей определяется правилами, которые устанавливаются нами. Вариаций правил существует бесчисленное множество, и они были систематизированы в определённые конфигурации.
Самая популярная конфигурация – «B/S», или «life-like», по названию крайне широко известного клеточного автомата «Game of Life», где B/S обозначает, что в нашем правиле мы описываем всего два параметра – количество соседей необходимых для рождения новой клетки в пустой ячейке, и количество соседей для выживания существующей клетки.
В каждой статье серии мы углубляемся в данную конфигурацию, добавляя новые параметры, либо дополняя существующие. Иногда заглядываем и в прочие конфигурации.
Для понимания сегодняшней статьи достаточно знать, что:

поиск соседей изначально выполняется в радиусе 1 (8 окружающих клеток – ), но мы можем установить другой, добавив к правилу Rx, где x – нужный нам радиус;
мы можем изменять шаблон окрестности поиска соседей. Изначально подразумевается окрестность Мура – R в каждую сторону (и диагональ) от рассматриваемой клетки, – но указывая Nxx мы будем определять иной шаблон, что, конечно, изменит вид правила. Сегодня мы продолжаем расширение этой части правила. Знакомство с предыдущими расширениями не является необходимым, но вы, конечно, можете предварительно ознакомиться с ними и прочими дополнениями, для большей последовательности чтения. Ссылки в конце материала и в профиле.

Пользовательские окрестности можно разделить на два типа – ручные расположения и шаблоны построения. Начнём с первых.

❯ Ручные расположения

Данный тип поддерживаeтся в нотации через параметр окрестности N@x, где x – код нашего расположения, составленный по определённым правилам:

Мы строим наше расположение в одномерном виде, последовательно указывая нулями и единицами учёт каждой клетки окрестности. К примеру, окрестность фон Неймана для радиуса 2 будет выглядеть как 00100 01110 11c11 01110 00100 (пробелы для читаемости, построение происходит без них);
Убираем центральную клетку c, в данном варианте она никогда не учитывается (только если конфигурация/реализация не поддерживает параметр M в правиле, но к параметру окрестности он всё равно не относится);
Переводим получившееся двоичное число в шестнадцатеричную систему счисления. Всё, код для нотации готов. Для примера с окрестностью фон Неймана и R2 это будет N@23BDC4.

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

Интереснее всего на пользовательских окрестностях смотрятся направленные варианты, построенные без интуитивно напрашивающейся полной симметрии.

R2/G2/S4-6,8-9/B6-9/N@839DE7

_{Или NW10000 01110 01011 01111 00111}

:h Нотация

R – радиус поиска соседей. Регулирует окрестность.
G – количество состояний клеток. Минимум – 2 (жива/мертва), бо́льшие значения отвечают за длительность «старения» клетки, когда она уже не считается живым соседом для прочих клеток, но ещё не освободила клетку для рождения новой. Если совсем правильно, в HROT и LtL принято использовать C (Count of states).
M – булевый параметр, учитывается ли собственное состояние клетки при подсчёте соседей. В HROT данный параметр отсутствует (=всегда принимается за 0), но мы сохраним возможность использования этого параметра.
S – значения и/или диапазоны количества соседей, необходимых для выживания клетки. Диапазоны записываются через дефис (если учитывать обратную совместимость с LtL, может быть использовано двое- и троеточие или t), значения и диапазоны отделяются друг от друга запятыми.
B – полностью аналогично S, но отвечает за количество соседей, необходимых для рождения новой клетки.
N – обозначение используемой окрестности. Как раз об этом мы сегодня и говорим.
/ – разделитель между параметрами правила. В правильной нотации используются «,» (да, и между параметрами, и между диапазонами/значениями), но также встречается и вариант вовсе без разделителей между параметрами.

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

В направленных окрестностях много очень простых, но забавных примеров. Как эти «капли на стекле»…
R2/G2/S4-6,8-9/B6-9/N@839DE7 | 20с., 356×356, 300×20%

^{20с., 356×356, 300×20%}

R2/G2/S1,3/B2,4/N@3C00

_{NW00000 00000 11011 00000 00000}

… просто линии (обратите внимание на корабли в верхней части примера)
R2/G2/S1,3/B2,4/N@3C00 | 25с., 356×356, 300×20%

^{25с., 356×356, 300×20%}

R4/G3/S/B2/N@1018080000202

_{NW000000000 000000000 000000000 000010000 000101000 000010000 000000000 000000001 000000010}

… обычные направленные корабли
R4/G3/S/B2/N@1018080000202 | 47с., 178×178, 50×50%

^{47с., 178×178, 50×50%}

R3/G3/S/B2/N@E1860001

_{NW0000000 0000000 0011100 0010100 0011000 0000000 0000001}

… более сложные порождающие корабли-паровозы
R3/G3/S/B2/N@E1860001 | 49с., скорость ×1.5, 356×356, 50×50%

^{49с., скорость ×1.5, 356×356, 50×50%}

R2/G3/S0/B3/N@FFD9C4

_{NW11111 11111 01010 01110 00100}

^{44с., 356×356, 3×100%}

Продолжение

^{13с., 356×356, 3×100%}

R1/G2/S2-3/B2-3/N@4D

_{NW010 001 101}

… и многие другие структуры
R1/G2/S2-3/B2-3/N@4D | 18с., скорость ×1.5, 178×178, 50×20%

^{18с., скорость ×1.5, 178×178, 50×20%}

R2/G2/S0-3/B1-2/N@891891

_{NW10001 00100 01010 00100 10001 (а вот и FC)}

Напоследок взглянем на более привычный, орнаментный вид.
R2/G2/S0-3/B1-2/N@891891 | 16с., 356×356, 1×100%

^{16с., 356×356, 1×100%; для сглаживания мерцания обрезан каждый второй фрейм}

❯ Пользовательские шаблоны окрестностей

Хоть через ручную нотацию и можно реализовать любую другую окрестность (кроме взвешенных, у них собственный аналог), она не является полноценной заменой. Ручная окрестность неудобна, сложно воспринимается, и, что главное, – она строго ограничена тем радиусом, под который написана. Шаблоны окрестностей лишены этих недостатков. Мы уже рассматривали 10 «признанных» окрестностей, но, так как потенциал для создания новых шаблонов огромен, пользователи не преминули описать собственные.

Конечно, пытаться упомянуть все наработки нет ни возможности, ни смысла, потому мы, для примера, рассмотрим только набор шаблонов предложенных энтузиастом Antonio Sánchez Chinchón, которые он описал при реализации собственного симулятора циклических КА.

Контур Мура

^{Вид окрестности на радиусах 1-4}

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

Правило: (abs(x) == R) | (abs(y) == R)
Обозначение: Mr

Обозначение в нотации исключительно авторское и, к сожалению, не поддерживается популярными симуляторами, впрочем, как и пользовательские шаблоны в целом. Они могут быть реализованы только в таких же пользовательских симуляторах, а для использования в, например, Golly и LifeViewer придётся делать переложения на N@/NW под каждый радиус.

^{61с., 356×356, 50×70%| R3/G3/S9-20/B4,7/NMr}

^{13с., 356×356, 1×100%| R3/G3/S2-6,8,10,12,14,16,18,20,22,24/B1-2,4,6/NMr}

Контур фон Неймана

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

Правило: abs(x) + abs(y) == R
Обозначение: Nr

^{24с., 237×237, 6×100%| R4/G2/S5-16/B5,13-16/NNr}

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

^{28с., 237×237, 100×15%| R4/G3/S4-11/B6-9/NNr}

S-shape #1

Первый пример направленного шаблона.

Правило: ((y < 0) & (x > 0)) | ((y > 0) & (x < 0))
Обозначение: S1

^{48с., 356×356, 200×2% | R2/G3/S5/B2/NS1}

^{8с., 356×356, 2×100% | R7/G4/S0-7/B1-2/NS1}

Hourglass

Правило: abs(y) > abs(x)
Обозначение: D1

^{31с., 712×712, 200×100% | R3/G2/S3-16/B7-9/ND1}

^{43с., 356×356, 200×10% | R3/G4/S3/B4-6/ND1}

Hourglass remote

Правило: (abs(y) == abs(x)) | (abs(y) == R)
Обозначение: D2

^{15с., 356×356, 200×20% | R4/G2/S2-5/B4/ND2}

^{10с., 178×178, 20×100% | R2/G2/S1-9/B3/ND2}

Углы

Или же «инвертированная окрестность фон Неймана».

Правило: abs(y) + abs(x) > R
Обозначение: C2

^{14с., 356×356, 8×100% | R4/G4/S1-9/B8-40/NC2}

^{30с., 356×356, 250×25% | R2/G2/S3-11/B6-9/NC2}

Tick Mark

Комбинация диагонального креста и контура Мура.

Правило: (abs(y) == abs(x)) | (abs(y) == R) | (abs(x) == R)
Обозначение: TM

^{26с., 356×356, 50×5% | R2/G7/S6-15/B3/NTM}

^{8с., 356×356, 1×100% | R4/G3/S0-20/B1,17-30/NTM}

S-shape #2

Правило: (x == 0) | (y == R) & (x < 0) | (y = -R) & (x > 0)
Обозначение: S2

^{23с., 356×356, 50×20% | R4/G2/S/B3/NS2}

^{20с., 712×712, 2×100% | R2/G2/S1-5/B1/NS2}

Бонус: больше окрестностей

Буквально по одному случайному примеру на окрестность.

^{Шахматная доска mod 2 – Nb3 – (x % 2 == 0) & (y % 2 == 0)}

^{8с., 356×356, 1×100% | R4/G2/S0-9/B1/Nb3}

^{Контур фон Неймана mod 2 – Nrl – (abs(y) + abs(x) == R) & (x % 2 == 0)}

^{40с., 356×356, 50×95% | R4/G3/S/B2/NNrl}

^{T – NT – (x == 0) | (y == -R)}

Мерцание и немного залипание. Осторожно.

^{41с., 356×356, 10×100% | R3/G2/S0-5/B2-3/NT}

^{H – NH2 – (y == 0) | (abs(x) == R)}

^{52с., 356×356, 50×15% | R3/G2/S1-2/B4/NH2}

^{М – NM2 – (abs(x) == R) | (abs(y) == abs(x)) & (y > 0)}

^{15с., 356×356, 1×100% | R2/G2/S0-2,4/B1/NM2}

^{U – NU – (y == R) | (abs(x) == R)}

^{34с., 356×356, 50×15% | R3/G3/S/B4-5/NU}

^{Z – NZ – (abs(y) == R) | (y == -x)}

^{19с., 356×356, 20×100% | R6/G3/S0/B5-6/NZ}

^{Линии – Nln – (x == 0) | (x == R) & (y < 0) | (x == -R) & (y > 0)}

^{27с., 356×356, 50×20% | R3/G2/S1/B3/Nln}

Читайте также

О клеточных автоматах:

Базовая «life-like» конфигурация
Старение клеток: параметр поколений
Нотация Хенселя: учёт расположения соседей
LtL: расширенный радиус поиска соседей
Циклические клеточные автоматы
Альтернативные окрестности и HROT
Блочные КА, окрестность Марголуса
Взвешенные окрестности, окрестность Гаусса, Far Corners/Edges
Направленные и пользовательские окрестности (вы здесь)

Прочее:

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

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

Tzimie
22.04.2023 08:11
#25474726
+2
А есть ли статистика/таблица, какие правила являются алгоритмически неразрешимыми?
1. TLHE Автор
  22.04.2023 08:11
  #25475910
  Честно, не знаю. Подожду ответ вместе с вами.

phenik
22.04.2023 08:11
#25475028
Некоторые напомнили разбегающихся мультяшных козявочек)

Daddy_Cool
22.04.2023 08:11
#25476142
А какое на сегодня есть прикладное значение у этой темы? А то картинки вижу часто, но хочется чего-то э... применимого.
1. TLHE Автор
  22.04.2023 08:11
  #25476942
  +3
  Крайне широкий потенциал применения. В первую очередь – моделирование различных процессов в физике, химии, биологии, социологии, etc. Есть применения в математике и, разумеется, информатике, вплоть до новых подходов, вроде цифровой физики. Есть применения для криптографии, дизайна, генеративной музыки, …. Сложно сказать, в каких областях они не могут быть применены.
  
  Но так как различных конфигураций и правил бесконечно много, мы не можем сказать, что для некоторой задачи применяется строго КА с такой-то конфигурацией и правилом. Тем более, что чаще всего КА применяются в тех проблемах, где либо вовсе нет эталонного результата, который бы достигался одним КА, либо изначально моделирование предполагает упрощённое приближение.
  Потому нет и единого списка "проблема = правило КА", есть только список областей применения, где вы уже можете искать частные, зачастую научные, работы.
  
  Если всё же с частными примерами – в преддверии текущей серии, я делал переводы по упрощённому моделированию лесных пожаров и модели сегрегации Шеллинга (обратите внимание, что и в этих примерах нет единого "ответа", – разбирается проблема с различными модификациями КА, пусть и в рамках одной конфигурации).
  На Хабре были статьи про генерацию 2D мира (и ещё несколько) и анимацию смерти монстров в играх, генеративную музыку, моделирование пешеходных потоков, и даже серия статей «Логика сознания» не обошла тему КА.
  И многие другие примеры. И это не касаясь сугубо математического интереса к области, о котором можно годичную серию писать, но об этом лучше пусть расскажут авторы, которые в этом хорошо разбираются.
  1. Daddy_Cool
    22.04.2023 08:11
    #25477310
    Ага, спасибо! Посмотрел модель лесного пожара.У нас парень в лаборатории всё носился с КА, но с применением КА для задач сплошной среды как-то сложно. Логика поведения клеток жестко определяется законами физики и обычных численных методов оказывается вполне достаточно.

commanderkid
22.04.2023 08:11
#25476226
+1
Также некоторые белки - прионы, работают.