![](https://habrastorage.org/webt/iy/bw/v0/iybwv0lkxqbbyl1jd9uutofazds.gif)
?, Хабр!
В прошлой статье о циклических КА мы мельком затронули тему альтернативных окрестностей, рассмотрев несколько примеров. Несмотря на то, что ранее мы использовали только окрестности Мура и фон Неймана, существует ещё множество прочих именованных окрестностей, а потенциал для создания новых ограничен лишь нашей фантазией.
Сегодняшний обзор мы совместим с ещё одним расширением: в статье об LtL было упомянуто, что параметры рождения и выживания клетки могут поддерживать множество значений и диапазонов в некоторых прочих конфигурациях. В первую очередь речь шла о HROT (Higher-Range Outer-Totalistic) – обобщении LtL конфигурации, на котором и будут наши сегодняшние примеры.
Тема альтернативных окрестностей крайне слабо исследована сообществом. Энтузиасты КА больше сконцентрированы на рассмотрении уже известных правил, редко отходя от общепризнанных конфигураций. И это вполне объяснимо – даже простейшая B/S конфигурация содержит огромное количество правил и паттернов, с любым отдельно взятым расширением представляя чуть ли не бесконечный потенциал для исследования. Мы же движемся как раз «в ширину», рассматривая не столько частные случаи, сколько вариативность всей области.
❯ 1. Окрестность Мура
Для порядка стоит упомянуть все именованные окрестности, и начнём со всем знакомого примера.
![](https://habrastorage.org/webt/te/y7/yc/tey7ycvvgnrvox43dehjdte5qxi.png)
Вид окрестности на радиусах 1-4
В нотации данная окрестность всегда обозначается как NM. Если в правиле не указано иное, принимается окрестность Мура в качестве стандартного значения.
В дальнейшем мы будем обозначать логическое правило составления окрестности на основе x и y координат, с центральной клеткой (0, 0). Для окрестности Мура же мы просто берём все значения [-R, R].
Центральная (рассматриваемая) клетка никогда не задаётся окрестностью. Принято не включать eё в подсчёт соседей, а для явного включения используется параметр M1 в правиле. Данное дополнение было введено в LtL конфигурации, и, что несколько странно, HROT обобщение этот пункт в классической нотации опускает, хотя нам, конечно, ничто не мешает использовать и его.
Каждую окрестность будем сопровождать примерами с, как минимум, одним орнаментным видом и одним случайным. Некоторые примеры подобраны специально, для соответствия окрестности, но не стоит забывать, что окрестность не является определяющим параметром для финального вида, а является только частью правила.
![R2/G40/S8-24/B1,3,5,7,9/NM | 24с., 200×200, 4×100%](https://habrastorage.org/webt/sb/ik/ho/sbikhopqv3ybbrjfvzmtkig1a_q.gif)
24с., 200×200, 4×100% | R2/G40/M0/S8-24/B1,3,5,7,9/NM
:h Нотация
R – радиус поиска соседей. Регулирует окрестность.
G – количество состояний клеток. Минимум – 2 (жива/мертва), бо́льшие значения отвечают за длительность «старения» клетки, когда она уже не считается живым соседом для прочих клеток, но ещё не освободила клетку для рождения новой. Если совсем правильно, в HROT и LtL принято использовать C (Count of states).
M – булевый параметр, учитывается ли собственное состояние клетки при подсчёте соседей. В HROT данный параметр отсутствует (=всегда принимается за 0), но мы сохраним возможность использования этого параметра.
S – значения и/или диапазоны количества соседей, необходимых для выживания клетки. Диапазоны записываются через дефис (если учитывать обратную совместимость с LtL, может быть использовано двое- и троеточие или t), значения и диапазоны отделяются друг от друга запятыми.
B – полностью аналогично S, но отвечает за количество соседей, необходимых для рождения новой клетки.
N – обозначение используемой окрестности. Как раз об этом мы сегодня и говорим.
/ – разделитель между параметрами правила. В правильной нотации используются «,» (да, и между параметрами, и между диапазонами/значениями), но также встречается и вариант вовсе без разделителей между параметрами.
Характеристики примера – длительность анимации; [ускорение анимации от 100мс. на фрейм, если есть]; размер поля; размер и процент центрального заполнения на старте.
G – количество состояний клеток. Минимум – 2 (жива/мертва), бо́льшие значения отвечают за длительность «старения» клетки, когда она уже не считается живым соседом для прочих клеток, но ещё не освободила клетку для рождения новой. Если совсем правильно, в HROT и LtL принято использовать C (Count of states).
M – булевый параметр, учитывается ли собственное состояние клетки при подсчёте соседей. В HROT данный параметр отсутствует (=всегда принимается за 0), но мы сохраним возможность использования этого параметра.
S – значения и/или диапазоны количества соседей, необходимых для выживания клетки. Диапазоны записываются через дефис (если учитывать обратную совместимость с LtL, может быть использовано двое- и троеточие или t), значения и диапазоны отделяются друг от друга запятыми.
B – полностью аналогично S, но отвечает за количество соседей, необходимых для рождения новой клетки.
N – обозначение используемой окрестности. Как раз об этом мы сегодня и говорим.
/ – разделитель между параметрами правила. В правильной нотации используются «,» (да, и между параметрами, и между диапазонами/значениями), но также встречается и вариант вовсе без разделителей между параметрами.
Характеристики примера – длительность анимации; [ускорение анимации от 100мс. на фрейм, если есть]; размер поля; размер и процент центрального заполнения на старте.
![R2/G5/S2,4/B4/NM | 23с., 200×200, 100×10%](https://habrastorage.org/webt/yn/tm/rq/yntmrqrm_fh3fv_tztkxihxf58y.gif)
23с., 200×200, 100×10% | R2/G5/S2,4/B4/NM
❯ 2. Окрестность фон Неймана
Вторая по популярности, также известная нам окрестность, строится по «Манхэттенскому расстоянию» или «метрике городских кварталов», где учитываются только смежные клетки, а диагональные достигаются за два шага.
![](https://habrastorage.org/webt/05/fu/tk/05futkrxuzodboiaraa-eojh3cm.png)
Обозначение: NN
Правило: abs(y) + abs(x) <= R
![R2/G5/S2,5-9/B3-4,10/NN | 38с., 200×200, 100×100%](https://habrastorage.org/webt/ax/_j/ms/ax_jmswkczr0hcfazy4au7mlmli.gif)
38с., 200×200, 100×100% | R2/G5/S2,5-9/B3-4,10/NN
![R2/G5/S2,5-9/B3-4,10/NN | 35с., 200×200, 50×20%](https://habrastorage.org/webt/qa/wt/_k/qawt_kdwevle1et2wuua9oivpcs.gif)
30с., 200×200, 100×50% | R3/G6/S3-5/B4/NN
Ещё немного интересных кораблей
![R3/G6/S3-5/B4/NN | 30с., 200×200, 100×50%](https://habrastorage.org/webt/nm/_i/w-/nm_iw-w3qghptqe_fnd04mampmi.gif)
30с., 200×200, 100×50% | R3/G6/S3-5/B4/NN
![R5/G8/M1/S4-6/B5/NN | 25с., 400×400, 50×30%](https://habrastorage.org/webt/bb/el/dt/bbeldtfb5hd8ynisym5yonarfys.gif)
25с., 400×400, 50×30% | R5/G8/M1/S4-6/B5/NN
![R3/G6/S3-5/B4/NN | 30с., 200×200, 100×50%](https://habrastorage.org/webt/nm/_i/w-/nm_iw-w3qghptqe_fnd04mampmi.gif)
30с., 200×200, 100×50% | R3/G6/S3-5/B4/NN
![R5/G8/M1/S4-6/B5/NN | 25с., 400×400, 50×30%](https://habrastorage.org/webt/bb/el/dt/bbeldtfb5hd8ynisym5yonarfys.gif)
25с., 400×400, 50×30% | R5/G8/M1/S4-6/B5/NN
Мерцание
![R3/G2/S1,3,5,7,9,11,13,15,17,19,21,23/B1,3,5,7,9,11,13,15,17,19,21,23/NN | 19с., 300×300, 10×100%](https://habrastorage.org/webt/uc/i1/ke/uci1ker2d_cgmxfxehytuzpssjk.gif)
19с., 300×300, 10×100% | R3/G2/S1,3,5,7,9,11,13,15,17,19,21,23/B1,3,5,7,9,11,13,15,17,19,21,23/NN
![R1/G2/M1/S2,4/B1,3/NN | 35с., 200×200, 30×100%](https://habrastorage.org/webt/te/qj/ri/teqjri6ligwrgopstdif4k6tdzg.gif)
35с., 200×200, 30×100% | R1/G2/M1/S2,4/B1,3/NN
![R3/G2/S1,3,5,7,9,11,13,15,17,19,21,23/B1,3,5,7,9,11,13,15,17,19,21,23/NN | 19с., 300×300, 10×100%](https://habrastorage.org/webt/uc/i1/ke/uci1ker2d_cgmxfxehytuzpssjk.gif)
19с., 300×300, 10×100% | R3/G2/S1,3,5,7,9,11,13,15,17,19,21,23/B1,3,5,7,9,11,13,15,17,19,21,23/NN
![R1/G2/M1/S2,4/B1,3/NN | 35с., 200×200, 30×100%](https://habrastorage.org/webt/te/qj/ri/teqjri6ligwrgopstdif4k6tdzg.gif)
35с., 200×200, 30×100% | R1/G2/M1/S2,4/B1,3/NN
❯ 3. Евклидово расстояние
Первая незнакомая нам окрестность немного скругляет окрестность фон Неймана всем знакомыми штанами. Для наглядности, новые, по сравнению с прошлой окрестностью, клетки отмечены синим.
![](https://habrastorage.org/webt/79/rd/8b/79rd8bzvvxsmws8qzk_2xnsgcsg.png)
Обозначение: N2
Правило: (y**2 + x**2) ** 0.5 <= R
![R2/G25/S4-8/B4,6-10/N2 | 21с., 200×200, 80×100%](https://habrastorage.org/webt/_n/jw/rx/_njwrxt0l-qoogbj5y26fswpnkc.gif)
21с., 200×200, 80×100% | R2/G25/S4-8/B4,6-10/N2
![R3/G4/S10-15,19/B8-15,21-28/N2 | 45с., 200×200, 70×50%](https://habrastorage.org/webt/gx/4r/kz/gx4rkzcafapmp5jfvrefj9qava4.gif)
45с., 200×200, 70×50% | R3/G4/S10-15,19/B8-15,21-28/N2
![R3/G2/S5-8,17-18,21,24,26-27/B7-8,17,19,22-28/N2 | 25с., 200×200, 150×50%](https://habrastorage.org/webt/du/ah/97/duah97zccoav3zlulkxpb67pmqy.gif)
25с., 200×200, 150×50% | R3/G2/S5-8,17-18,21,24,26-27/B7-8,17,19,22-28/N2
❯ 4. Круг
Ещё большего скругления мы можем достичь, если добавим клетки, вписанные окружности которых имеют какую-либо площадь пересечения с окружностью от (0, 0) с радиусом R.
![](https://habrastorage.org/webt/d7/6e/zb/d76ezbxer1tb4i6yzap-yx-eb_0.png)
Обозначение: NC
Правило: (y**2 + x**2) ** 0.5 <= R + 0.5 (upd: DrSmile)
![R2/G5/S2-6/B1-2/NC | 25с., 550×550, 10×100%](https://habrastorage.org/webt/4m/ek/8e/4mek8e5p-mjh9t_hx3bzaqpdclk.gif)
25с., 550×550, 10×100% | R2/G5/S2-6/B1-2/NC
1024×1024; G3
![R2/G3/S2-6/B1-2/NC | 27с., 1024×1024, 10×100%](https://habrastorage.org/webt/gk/xv/m0/gkxvm0s30knw7qoz87w7zoyz5mm.gif)
27с., 1024×1024, 10×100% | R2/G3/S2-6/B1-2/NC
![R2/G3/S2-6/B1-2/NC | 27с., 1024×1024, 10×100%](https://habrastorage.org/webt/gk/xv/m0/gkxvm0s30knw7qoz87w7zoyz5mm.gif)
27с., 1024×1024, 10×100% | R2/G3/S2-6/B1-2/NC
![R6/G2/S37-64/B38-51/NC | 33с., 200×200, 100×50%](https://habrastorage.org/webt/5w/_5/h5/5w_5h53troj10dbtim7nb0ffcek.gif)
33с., 200×200, 100×50% | R6/G2/S37-64/B38-51/NC
❯ 5. Шахматная доска
![](https://habrastorage.org/webt/ub/qb/5s/ubqb5s8pxalzisskn7mqg54z-ca.png)
Пожалуй, самая недооценённая окрестность, с массой интереснейших правил.
Обозначение: NB
Правило: (y + x) % 2
![R3/G2/S0-5,8,11-22,24/B6,16/NB | 14с., 400×400, 400×100%](https://habrastorage.org/webt/s_/sq/qp/s_sqqpvq_mpo285ssmywkaqhw3e.gif)
14с., 400×400, 400×100% | R3/G2/S0-5,8,11-22,24/B6,16/NB
![R3/G3/S0-5,8,11-22,24/B6,16/NB | 15с., «Rivers», 200×200, 180×50%](https://habrastorage.org/webt/hl/fl/ef/hlflefnjozak1ke9gisg6hxkaic.gif)
15с., «Rivers», 200×200, 180×50% | R3/G3/S0-5,8,11-22,24/B6,16/NB
Бонус
![R10/G2/S25-28/B72-133/NB | 2мин., 10 запусков, 200×200, 100×50%](https://habrastorage.org/webt/0k/zf/bw/0kzfbwngz6jxswj0ygttkuaruik.gif)
2мин., 10 запусков, 200×200, 100×50% | R10/G2/S25-28/B72-133/NB
![R2/G5/S2-3/B3,8/NB | 35с., 200×200, 100×50%](https://habrastorage.org/webt/ei/r9/xt/eir9xt7x0ezfrrcq0dydjiunwgs.gif)
35с., 200×200, 100×50% | R2/G5/S2-3/B3,8/NB
![R10/G2/S25-28/B72-133/NB | 2мин., 10 запусков, 200×200, 100×50%](https://habrastorage.org/webt/0k/zf/bw/0kzfbwngz6jxswj0ygttkuaruik.gif)
2мин., 10 запусков, 200×200, 100×50% | R10/G2/S25-28/B72-133/NB
![R2/G5/S2-3/B3,8/NB | 35с., 200×200, 100×50%](https://habrastorage.org/webt/ei/r9/xt/eir9xt7x0ezfrrcq0dydjiunwgs.gif)
35с., 200×200, 100×50% | R2/G5/S2-3/B3,8/NB
❯ 6. Шахматная доска: инверсия
![](https://habrastorage.org/webt/kl/-d/tn/kl-dtnffpc1xq2kvnhbx7fqclou.png)
Данная вариация куда интереснее, чем может показаться. Инверсия в данном случае вносит одно ма-а-аленькое, но очень важное изменение – рассматриваемая клетка и все её соседи по окрестности оказываются одной «чётности», чего не было в обычном шахматном виде. Это приводит к тому, что у нас на поле одновременно сосуществуют два независимых друг от друга вида, что даёт интересные результаты на некоторых правилах.
Инвертированный вид не имеет устоявшегося обозначения в нотации. Полагаю, добавление «i» – наиболее логичный вариант.
Обозначение: NBi
Правило: (y + x) % 2 == 0
![R5/G13/S9-33/B16-24/NBi | 20с., 200×200, 10×100%](https://habrastorage.org/webt/pl/mn/s1/plmns1b1xjjoxeahu_nzohgjrws.gif)
20с., 200×200, 10×100% | R5/G13/S9-33/B16-24/NBi
![R1/G2/S1-10/B2-10/NBi | 33с., частичное заполнение, 200×200, 150×50%](https://habrastorage.org/webt/c6/rv/yz/c6rvyzgyhsxfuv4djfj_shvq0ro.gif)
33с., частичное заполнение, 200×200, 150×50% | R1/G2/S1-10/B2-10/NBi
![R1/G2/S1-10/B2-10/NBi | 35с., полное заполнение, 200×200, 150×50%](https://habrastorage.org/webt/5x/zb/rf/5xzbrffpj1zdpnvxjunxjolqqu0.gif)
35с., полное заполнение, 200×200, 150×50% | R1/G2/S1-10/B2-10/NBi
❯ 7. Решётка
![](https://habrastorage.org/webt/nm/6c/sc/nm6csczuxsmgeqg3yhjxbrtbpo4.png)
Обозначение: N#
Правило: (abs(y) == 1) | (abs(x) == 1)
![R2/G3/S2-4,6-9/B1/N# | 25с., 672×672, 1×100%](https://habrastorage.org/webt/sz/ac/-q/szac-qnr4lskhvomfhbsy5alei4.gif)
25с., 672×672, 1×100% | R2/G3/S2-4,6-9/B1/N#
![R2/G2/S4-6,12-16/B5-6,14/N# | 54с., 200×200, 100×15%](https://habrastorage.org/webt/hp/fz/r7/hpfzr7o8zo8drnwipdgocl1htgi.gif)
54с., 200×200, 100×15% | R2/G2/S4-6,12-16/B5-6,14/N#
❯ 8. Крест
![](https://habrastorage.org/webt/vs/3z/c1/vs3zc1wl9jvft_etiqscljszhxu.png)
Обозначение: N+
Правило: (y == 0) | (x == 0)
![R4/G2/S3,6-12/B4/N+ | 40с., скорость ×3, 200×200, 7×100%](https://habrastorage.org/webt/m1/xm/ht/m1xmhtcu7dk-lpoxo9fff73ikja.gif)
40с., скорость ×3, 200×200, 7×100% | R4/G2/S3,6-12/B4/N+
Спустя 10.000 итераций
![R4/G2/S3,6-12/B4/N+](https://habrastorage.org/webt/5o/kq/6l/5okq6lk7fe7axylznm9xq3pmeza.gif)
Это финальный вид. Остались только небольшие мигалки.
![R4/G2/S3,6-12/B4/N+](https://habrastorage.org/webt/5o/kq/6l/5okq6lk7fe7axylznm9xq3pmeza.gif)
Это финальный вид. Остались только небольшие мигалки.
![R3/G2/S5-9/B3/N+ | 38с., скорость ×2, 200×200, 7×100%](https://habrastorage.org/webt/nu/ca/pm/nucapmkfpnglqrm4lb41mj-_uxm.gif)
38с., скорость ×2, 200×200, 7×100% | R3/G2/S5-9/B3/N+
![R3/G2/S5-9/B3/N+ | 24с., скорость ×1.5, 200×200, 100×70%](https://habrastorage.org/webt/hm/ko/dt/hmkodtayqkw32h6yjh6hyuw4aow.gif)
24с., скорость ×1.5, 200×200, 100×70% | R3/G2/S5-9/B3/N+
❯ 9. Андреевский крест
![](https://habrastorage.org/webt/iu/m5/k6/ium5k6w4njn9n3mjat0n8feeayk.png)
Ещё одна окрестность с единой «чётностью».
Названия последних двух окрестностей – прямые переводы оригинальных английских названий «cross» (не jebus) и «saltire», хотя в адаптации, вероятно, ближе были бы «плюс» и «[диагональный] крест», соответственно.
Обозначение: NX
Правило: abs(y) == abs(x)
![R3/G2/S6-10/B3,8/NX | 27с., скорость ×2, 400×400, 8×100%](https://habrastorage.org/webt/_i/el/dc/_ieldciyfr_2cuodupaxpkgp5fo.gif)
27с., скорость ×2, 400×400, 8×100% | R3/G2/S6-10/B3,8/NX
Продолжение
![R3/G2/S6-10/B3,8/NX | 29с., скорость ×2, 400×400, 8×100%](https://habrastorage.org/webt/tn/np/mx/tnnpmx81wq0jmslic-q2okseava.gif)
![R3/G2/S6-10/B3,8/NX | 29с., скорость ×2, 400×400, 8×100%](https://habrastorage.org/webt/tn/np/mx/tnnpmx81wq0jmslic-q2okseava.gif)
Продолжение...
![R3/G2/S6-10/B3,8/NX | 25с., скорость ×2, 400×400, 8×100%](https://habrastorage.org/webt/gu/we/9c/guwe9cuoztvfpnepfuwbq2lzo94.gif)
![R3/G2/S6-10/B3,8/NX | 25с., скорость ×2, 400×400, 8×100%](https://habrastorage.org/webt/gu/we/9c/guwe9cuoztvfpnepfuwbq2lzo94.gif)
Финал
![R3/G2/S6-10/B3,8/NX | 18с., скорость ×2, 400×400, 8×100%](https://habrastorage.org/webt/zd/fg/ox/zdfgoxqixnmmub6hcjzju-xcffy.gif)
![R3/G2/S6-10/B3,8/NX | 18с., скорость ×2, 400×400, 8×100%](https://habrastorage.org/webt/zd/fg/ox/zdfgoxqixnmmub6hcjzju-xcffy.gif)
![R3/G2/S6-10/B3,8/NX | 30с., скорость ×2, 400×400, 200×50%](https://habrastorage.org/webt/yw/v9/zw/ywv9zw6uerv1uwmuuta2ved_ghy.gif)
30с., скорость ×2, 400×400, 200×50% | R3/G2/S6-10/B3,8/NX
❯ 10. Звезда
![](https://habrastorage.org/webt/cb/q6/d3/cbq6d3yjc63gnklyk3oopq11jwe.png)
Объединение двух прошлых «крестов».
Обозначение: N*
Правило: (abs(y) == abs(x)) | (y == 0) | (x == 0)
![R2/G12/S2-15/B1-3,6-12/N* | 15с., 250×250, 10×100%](https://habrastorage.org/webt/ln/kj/tl/lnkjtlxzbygu1khdfql0xqsgdgc.gif)
15с., 250×250, 10×100% | R2/G12/S2-15/B1-3,6-12/N*
![R2/G3/S0-2,4-8/B6-7/N* | 40с., 200×200, 200×10%](https://habrastorage.org/webt/el/go/pv/elgopvl4fg4rnewu3fobm5sedz0.gif)
40с., «Ледоколы», 200×200, 200×10% | R2/G3/S0-2,4-8/B6-7/N*
Как упоминалось в начале, тема окрестностей довольно слабо исследована, и даже список «признанных» окрестностей с устоявшимися обозначениями заканчивается на десятом номере.
Несмотря на это, существуют ещё окрестности для прочих сеток, множество пользовательских окрестностей, а также несколько крайне занимательных частностей.
Обо всём ещё поговорим. Не переключайтесь.
Читайте также
О клеточных автоматах:
Прочее:
- Базовая «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)