"Жизнь" Конвея и другие клеточные автоматы

22.03.23

Разработка - Математика и алгоритмы

Я думаю, нет нужды представлять математика Джона Конвея и его "Game of Life" - игру "Жизнь". Предлагаю вспомнить эту игру, а также другие "жизне"-подобные клеточные автоматы. К статье приложен файл с реализацией этой игры.

Скачать файлы

Наименование Файл Версия Размер
"Жизнь" Конвея и другие клеточные автоматы:
.erf 15,94Kb
8
.erf 15,94Kb 8 Скачать

Об игре

История Game of Life началась даже не с Джона Конвея, а с Джона фон Неймана - основоположника сегодняшней компьютерной архитектуры (архитектура фон Неймана, в противоположность гарвардской архитектуре). В процессе доказательства существования самовоспроизводящихся машин он смоделировал автомат, работающий на клеточной доске. Радикально упростив этот автомат, Джон Конвей получил набор правил, которые и стали основой для игры "Жизнь".

Правила из Википедии:

  • Место действия игры — размеченная на клетки плоскость, которая может быть безграничной, ограниченной или замкнутой.
  • Каждая клетка на этой поверхности имеет восемь соседей (окрестность Мура), окружающих её, и может находиться в двух состояниях: быть «живой» (заполненной) или «мёртвой» (пустой).
  • Распределение живых клеток в начале игры называется первым поколением. Каждое следующее поколение рассчитывается на основе предыдущего по таким правилам:
    • в пустой (мёртвой) клетке, с которой соседствуют три живые клетки, зарождается жизнь;
    • если у живой клетки есть две или три живые соседки, то эта клетка продолжает жить; в противном случае (если живых соседей меньше двух или больше трёх) клетка умирает («от одиночества» или «от перенаселённости»).
  • Игра прекращается, если
    • на поле не останется ни одной «живой» клетки;
    • конфигурация на очередном шаге в точности (без сдвигов и поворотов) повторит себя же на одном из более ранних шагов (складывается периодическая конфигурация)
    • при очередном шаге ни одна из клеток не меняет своего состояния (частный случай предыдущего правила, складывается стабильная конфигурация)

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

Очевидно, что максимальная скорость распространения популяции - 1 клетка за 1 ход (по горизонтали, вертикали или диагонали). Логично, что она получила название скорость света.

Удивительно, но игра имеет отношение к самым разным наукам: квантовой физике, электротехнике, химии, даже биологии - у некоторых ящериц окраска чешуек формируется по похожим принципам

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

 

 

Эта фигура за каждые 4 хода смещается на 1 клетку по диагонали.  Таким образом планер двигается со скоростью 1/4 скорости света.

С помощью планеров можно конструировать счётчикилогические вентили ИИЛИНЕ. С использованием планеров можно доказать, что «Жизнь» в качестве вычислительной машины является полной по Тьюрингу.

О реализации

Первая проблема, с которой сталкивается любой, кто собрался реализовать эту игру - поле. Так как прямоугольное поле имеет границы, то как должна развиваться колония клеток на границе? Есть два подхода - первый: считать, что за границей поля нет и не может быть живых клеток, и второй: соединить противоположные края, превратив прямоугольник в тор. Обычно используется второй вариант - планер, вылетев за нижний край, вернется сверху. 

Основных подходов к реализации алгоритмов тоже два. 

Первый подход заключается в создании двумерного массива по размеру поля, элемент массива соответствует клетке поля. Автор этих строк когда-то использовал в качестве такого массива видеопамять VGA. Очевидно, что а) при таком подходе поле ограничено доступной памятью, б) алгоритм игры содержит обход по двумерному массиву, его производительность значительно падает при увеличении поля, в) обычно скорость выполнения почти не зависит от заполненности поля. Второй подход вместо массива для поля предполагает массив для клеток. Элемент массива содержит координаты клетки. Потенциально с помощью такого подхода можно иметь в игре "бесконечное" поле. Но в этом случае а) скорость и объем необходимой памяти зависит от количества клеток в популяции, б) появляется проблема быстрого поиска клеток по координатам.

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

 
 Пример игры

Еще один интересный алгоритм на основе запроса описан в Игра "Жизнь" в одном запросе

Аналогов игры в интернете полно, в том числе и на Инфостарте: раз, два, три ... Но игры на основе клеточных автоматов не ограничиваются указанными выше правилами. А что если изменить количество соседей?

 

Другие клеточные автоматы

Предположим, что новая клетка рождается (birth) если у нее 3 соседа, а выживает (survival) если имеет 2 или 3 соседей. Тогда правила для игры "жизнь" описываются формулой B3/S23. Меняя в этой формуле цифры, мы получим другие правила и другие игры, со своими закономерностями и интересными эффектами.

 
День и ночь (B3678 / S34678)
 
 Пример осциллятора и движущаяся "бабочка"

Есть интересная особенность: поле можно "инвертировать", тогда конфигурация "мертвых" клеток будет вести себя так же, как и бывшая конфигурация "живых клеток".

 
Жизнь без смерти (B3 / S012345678)

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

 
 Во что превращается планер
 
HighLife (B36 / S23)

Во многом похожа на "Жизнь". Здесь интересен репликатор - конфигурация клеток которая создает свои копии по обеим сторонам, эти копии - свои копии, которые сталкиваются, уничтожаются, после чего остаются два экземпляра удаляющиеся друг от друга.

 
 Репликтор

Семена (B2 / S)

Здесь ни одна из клеток не выживает, но перед смертью может дать жизнь новой клетке. Интересно наличие фотонов, движущихся со скоростью света. Сталкиваясь, фотоны могут погибнуть, а могут породить другие фотоны (чем не физика элементарных частиц!))).

 
 Фотоны

Morley (B368 / S245)

Эта игра примечательна наличием простого паровоза, двигающейся фигуры, оставляющей за собой дым. За 170 шагов он перемещается на 13 клеток

 
Паровоз

 

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

 

 

Прочие виды правил перечислены здесь, и здесь, а еще здесь.

 

Игра тестировалась в тонком клиенте 8.3.22.1709.

Как всегда, приветствуются замечания / дополнения / комментарии.

 
 Некоторые из прочих моих публикаций  

  

Игра Жизнь Конвей Game of Life Клеточный Автомат

См. также

Метод Дугласа-Пойкера для эффективного хранения метрик

Математика и алгоритмы Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    1757    stopa85    12    

33

Алгоритм симплекс-метода для решения задачи раскроя

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    4432    user1959478    50    

34

Регулярные выражения на 1С

Математика и алгоритмы Инструментарий разработчика Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    7473    4    SpaceOfMyHead    17    

56

Игра Балда (одномерный вариант)

Игры Платформа 1С v8.3 Конфигурации 1cv8 Абонемент ($m)

Одномерный или "устный" вариант игры Балда.

1 стартмани

05.12.2022    3880    2    Alexei_Siva    1    

39

Сетевая игра "Захват клеток"

Игры 8.3.14 Конфигурации 1cv8 ИТ-компания Россия Абонемент ($m)

Сетевая игра "Захват клеток" с возможностью играть на время, а также с поддержкой игры оффлайн против компьютера.

1 стартмани

12.09.2022    6232    13    Sergey_Borisovi4    9    

33

Карточная игра "Дурак"

Игры Платформа 1С v8.3 Россия Абонемент ($m)

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

1 стартмани

07.06.2022    7518    19    user676027_svikator    16    

46

Модель распределения суммы по базе

Математика и алгоритмы Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    7859    7    kalyaka    11    

44

Изменения формата файлов конфигурации (CF) в 8.3.16

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    4451    fishca    13    

36
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. RustIG 1382 22.03.23 16:49 Сейчас в теме
(0) спасибо! поучительно!
2. Alxby 1136 22.03.23 17:23 Сейчас в теме
(1)Ага. Вроде бы ничего особенного, а затягивает.
3. aSHA-1 26.03.23 09:26 Сейчас в теме
а шаблоны будут? хотя бы как у Гарднера?
5. Alxby 1136 26.03.23 12:26 Сейчас в теме
(3)Возможно. Но потом. Сейчас на очереди другие игры.Кстати, для тех, кто не знает, - Мартин Гарднер - автор научно-популярных книг по математике, несколько глав в них он посвятил этой игре.
7. aSHA-1 26.03.23 14:28 Сейчас в теме
(5)Буду ждать, подписался
4. AndreyCh75 26.03.23 09:53 Сейчас в теме
Спасибо! Прям ностальгия, писал в свое время на дельфи) А потом сидел перед монитором и медитировал)
6. Alxby 1136 26.03.23 12:39 Сейчас в теме
(4)Первый раз я ее написал на asm86 под DOS. Потом - на Delphi с ассемблером на поле 1000*1000. По сравнению с DOS, возможность создать двумерный массив на мегабайт - это было круто! Про всякие там DirectX, OpenGL и прочие Unity тогда не знали, поэтому графика тоже была на ассемблере.
Прикрепленные файлы:
dicwork; manuel; tsmult; Somebody1; AndreyCh75; +5 Ответить
8. YA_523322930 02.04.23 18:45 Сейчас в теме
Слушай, мы же 1сники, мы в этом вообще не шарим, это все для настоящих программистов и математиков, а нам лучше что-нибудь про НДС, это наш потолок. Ну или там как зп рассчитывать, вот и вся математика, доступная 1сникам.
9. Alxby 1136 05.04.23 06:56 Сейчас в теме
(8)1с - это всего лишь инструмент. Умение на 1с решать нестандартные задачи (в том числе, но не обязательно игры) - признак мастерства. Вы же не против повышать свое мастерство?
G_116449793522595596167; +1 Ответить
10. YA_523322930 05.04.23 20:49 Сейчас в теме
(9) Мастерство у 1сника - это клепать управляемые формочки с кнопочками, настраивать обмены и периодически перезагружать сервер бд, все высокие технологии и математика уже за гранью 1с, там уже программирование.
11. Alxby 1136 05.04.23 22:23 Сейчас в теме
(10)Я надеюсь, большинство не разделяют Ваше мнение
Климов; G_116449793522595596167; +2 Ответить
12. dicwork 07.04.23 10:55 Сейчас в теме
Я писал такую программу в 1980 году на языке ПЛ/1. Набивал на перфокартах. Выводил на печать на бумагу. С этого началось мое увлечение программированием.
13. Климов 26.04.23 16:49 Сейчас в теме
Студентов-практикантов заставляю "Жизнь" писать.
А слабо множество Мандельброта на 1С нарисовать? Тоже затягивающая штука...
14. Alxby 1136 26.04.23 20:58 Сейчас в теме
(13)Множество Мандельброта я рисовал на Си. В 1С как вывести результат? В табличном документе слишком низкое разрешение получится. Да и производительность математики здесь под вопросом. А студенты на чем "Жизнь" пишут?
15. Климов 27.04.23 16:23 Сейчас в теме
(14) А кому легко! :-) На Си и я писал. Или на Паскале? Давно это было...
А "Жизнь" студенты на 1С пишут. Или крестики-нолики. Несмотря на кажущуюся несерьёзность эти задачи хорошо учат разделять клиентскую и серверную части, вычисления и и визуализацию.
16. Alxby 1136 28.04.23 08:30 Сейчас в теме
(15)Абсолютно согласен, для целей обучения написание игр - почти идеальный вариант. Но, занудства ради, в моих играх, в основном, вся работа происходит на клиенте, серверной части почти нет :).
Оставьте свое сообщение