И так сегодня мы с вами войдём в мир одновременно простой и сложной "игры" под названием "жизнь".
Правила:
В начале как и в любой другой "игре" мы ознакомимся с правилами:
- Место действия этой игры — «вселенная» — это размеченная на клетки поверхность или плоскость — безграничная, ограниченная, или замкнутая (в пределе — бесконечная плоскость).
//хочу отметить что Game of Life, даже игрой назвать нельзя, это клеточный автомат ( вот вам ссылка на вики, почитайте если интересно https://ru.wikipedia.org/wiki/Клеточный_автомат) Игрок не принимает прямого участия в игре, а лишь расставляет или генерирует начальную конфигурацию «живых» клеток, которые затем взаимодействуют согласно правилам уже без его участия (он является наблюдателем).
- Каждая клетка на этой поверхности может находиться в двух состояниях: быть «живой» (заполненной) или быть «мёртвой» (пустой). Клетка восемь соседей , окружающих её.
- Распределение живых клеток в начале игры называется первым поколением. Каждое следующее поколение рассчитывается на основе предыдущего по таким правилам:в пустой (мёртвой) клетке, рядом с которой ровно три живые клетки, зарождается жизнь;
если у живой клетки есть две или три живые соседки, то эта клетка продолжает жить; в противном случае, если соседей меньше двух или больше трёх, клетка умирает («от одиночества» или «от перенаселённости»)
- Игра прекращается, если на поле не останется ни одной «живой» клетки
конфигурация на очередном шаге в точности (без сдвигов и поворотов) повторит себя же на одном из более ранних шагов (складывается периодическая конфигурация)
при очередном шаге ни одна из клеток не меняет своего состояния (складывается стабильная конфигурация; предыдущее правило, вырожденное до одного шага назад)
Эти простые правила приводят к огромному разнообразию форм, которые могут возникнуть в игре.
Как же произошла наша "вселенная"?
Джон Конвей заинтересовался проблемой, предложенной в 1940-х годах известным математиком Джоном фон Нейманом , который пытался создать гипотетическую машину, которая может воспроизводить сама себя. Джону фон Нейману удалось создать математическую модель такой машины с очень сложными правилами. Конвей попытался упростить идеи, предложенные Нейманом, и в конце концов ему удалось создать правила, которые стали правилами игры «Жизнь».
Впервые описание этой игры было опубликовано в октябрьском
(1970 год )выпуске журнала Scientific American , в рубрике «Математические игры» Мартина Гарднера (Martin Gardner ) .
//Хочу уточнить что в 1970 году у Конвея только были сами правила игры, но не сама готовая игра
Компьютерная реализация
В компьютерных реализациях игры поле ограничено и (как правило) верхняя граница поля «соединена» с нижней, а левая граница — с правой, что представляет собой эмуляцию поверхности тора , но на экране поле всегда отображается в виде равномерной сетки.
Простейший алгоритм «смены поколения» последовательно просматривает все ячейки решётки и для каждой ячейки подсчитывает соседей, определяя судьбу каждой клетки (не изменится, умрёт, родится). Такой простейший алгоритм использует два двумерных массива — один для текущего поколения, второй — для следующего.
Более сложный, но и более быстрый алгоритм составляет списки клеток для просмотра в последующем поколении; клетки, которые не могут измениться, в списки не вносятся. Например, если какая-либо клетка и ни одна из её соседей не поменялись на предыдущем ходу, то эта клетка не поменяется и на текущем ходу.
Ну что разработчики? Поняли как нужно оптимизировать игры? CD Project увидьте! (Нет я серьёзно, представьте как тяжело было компьютерам той эпохи, воспроизводить столько вычислений, автор молодец!)
Фигуры
//Подготовьте свои мозги ///Все названия фигур кликабельны, можете почитать
Вскоре после опубликования правил было обнаружено несколько интересных шаблонов (вариантов расстановки живых клеток в первом поколении), в частности: r -пентамино и планер (glider ).
Некоторые такие фигуры остаются неизменными во всех последующих поколениях, состояние других периодически повторяется, в некоторых случаях со смещением всей фигуры. Существует фигура (Diehard ) всего из семи живых клеток, потомки которой существуют в течение ста тридцати поколений, а затем исчезают.
Конвей первоначально предположил, что никакая начальная комбинация не может привести к неограниченному размножению и предложил премию в 50 долларов тому, кто докажет или опровергнет эту гипотезу. Приз был получен группой из Массачусетского технологического института , придумавшей неподвижную повторяющуюся фигуру, которая периодически создавала движущиеся «планеры». Таким образом, количество живых клеток могло расти неограниченно. Затем были найдены движущиеся фигуры, оставляющие за собой «мусор» из других фигур.
К настоящему времени более-менее сложилась следующая классификация фигур:
Планерное ружьё Госпера — первая бесконечно растущая фигура
- Устойчивые фигуры : фигуры, которые остаются неизменными
- Долгожители : фигуры, которые долго меняются, прежде чем стабилизироваться ;
- Периодические фигуры : фигуры, у которых состояние повторяется через некоторое число поколений, большее 1;
- Двигающиеся фигуры : фигуры, у которых состояние повторяется, но с некоторым смещением;
- Паровозы : двигающиеся фигуры с повторяющимися состояниями, которые оставляют за собой другие фигуры в качестве следов;
- Пожиратели : устойчивые фигуры, которые могут пережить столкновения с некоторыми двигающимися фигурами, уничтожив их;
- Отражатели : устойчивые или периодические фигуры, способные при столкновении с ними движущихся фигур поменять их направление;
- Размножители : конфигурации, количество живых клеток в которых растёт как квадрат количества шагов;
- Фигуры, которые при столкновении с некоторыми фигурами дублируются.
Райский сад
Райским садом (садом Эдема) называется такое расположение клеток, у которого не может быть предыдущего поколения. Практически для любой игры, состояние клеток в которой определяется несколькими соседями на предыдущем шаге, можно доказать существование садов Эдема, но построить конкретную фигуру гораздо сложнее.