Game of Life

Game of Life

LINE

Введение

Game of Life, или игра в жизнь - это клеточный автомат с довольно простыми правилами и интересной механикой. Впервые он был предложен английским математиком Джоном Конвеем в 1970 году.

Основные идеи

Представьте себе прямоугольное поле, состоящее из клеток. Каждая клетка может быть в двух состояниях - живая или мертвая. Клетка может перейти из одного состояния в другое при определенных условиях - именно поэтому это автомат (есть несколько состояний и правила перехода из одного состояния в другое). Такое поле, 5 на 6, изображено ниже. Живые клетки обозначены черным цветом, мертвые - белым.

Игра в жизнь представляет из себя поле, состоящее из таких клеток. Каждая (почти) клетка имеет 8 соседей вокруг себя. Например, для клетки с координатами row = 2, column = 2 (красный цвет) соседи будут следующие (серый цвет). Соответственно число живых соседей может быть в диапазоне от 0 до 8.

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

Всего есть несколько правил перехода клетки, они зависят от числа соседей

  • Если клетка живая и число соседей меньше 2(0 или 1) или число соседей больше 3 (4 и больше), клетка умирает (от одиночества или перенаселения соответственно0).
  • Если клетка мертва и число соседей равно 3, клетка становится живой.
  • Если клетка жива и число соседей равно 2 или 3, клетка остается живой

Эти правила можно проиллюстрировать на примере конечного автомата с 2-мя состояниями (живая и мертвая) и несколькими переходами

Реализация

Мы напишем реализацию используя Processing (скачать Processing можно здесь). Чтобы не усложнять задачу сразу, напишем по работающей цепочке: Правильно - просто - быстро. Т.е. сначала заставим алгоритм работать так, как он должен. Затем перепишем отдельные фрагменты для большей понятности. Затем разберемся с выделением памяти.

Первое что нужно сделать - создать файл processing и добавить метода setup (вызывается 1 раз в самом начале) и draw (вызывается каждый фрейм). Добавим размер и цвет фона. Для начала будем рисовать на поле размером 5 строк на 6 столбцов, с размером клетки 40, поэтому размер будет 240 на 200.

За поле будет отвечать класс Grid (или Field)

Этому классу нужно знать, сколько у нас строк(rows), столбцов(columns) и длину каждой клетки(len). Все ячейки хранятся в двумерном массиве размера rows x columns. Значение элемента массива - просто boolean, где true - клетка живая, false - клетка мертва. Изначально все клетки сейчас мертвы, т.к. значение по умолчанию для boolean - false.

Добавим метод для отрисовки клеток draw. Если клетка живая - рисуем ее черным цветом, если мертвая - белым (или наоборот, это не важно). fill(0) означает заполнять содержимое фигур черным, fill(255) - белым.

Чтобы посмотреть, что получилось сделаем в конструкторе несколько клеток живыми

Теперь можно посмотреть что получилось, создав объект Grid и вызвав метод draw() (frameRate(1) означает вызывать метод draw 1 раз в секунду, можете убрать эту строчку)

Мы получим такое изображение

Следующее поколение

Следующее, что нужно сделать - рассчитать новое значение каждой клетки. Для этого нужно посчитать количество соседних живых клеток.

Здесь есть важный момент. Давайте посмотрим на клетку, отмеченную красным.

Эта клетка мертвая, и у нее есть 3 живых соседей (3 нижние клетки). Значит следующий раз эта клетка должна стать живой. Можно отметить ее как черную и перейти к следующей - той, что теперь отмечена красной.

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

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

Подсчет соседей

Затем нам нужно рассчитать количество соседей для каждой клетки. Самый простой вариант - просто написать все эти значения.

Выглядит не очень, но работать будет. Почти.

Здесь также есть особенность - у крайних клеток соседей меньше. Например, у клетки отмеченной красным их только 3 (отмеченные серым), а не 8.

Если мы попробуем запустить текущую версию с таким набором if-в, мы получим ошибку связанную с тем что выходим за границы массива(если i = 0, то мы обратимся по индексe i - 1 = -1)

Как высчитывать соседей для такой клетки? Есть 3 основных варианта

Игнорировать клетки на границах.

Мы просто удаляем из цикла все клетки, у которых row равен 0 или (rows - 1) и columns равен 0 или (columns - 1). Тогда сетка уменьшится и станет такой

Игнорировать несуществующих соседей

Т.е. мы вычисляем количество соседей, если можем. Можно воспользоваться связкой if-ов, можно сделать это хитрее.

Возьмем случайную точку в центре и обозначим всех соседей цифрами от 1 до 8

Теперь возьмем byte и представим его не как число в десятичной системе, а как битовый вектор. В нем тоже будет 8 бит. Мы можем обозначить каждый бит как одного соседа. В случае клетки в центре у нее будут все соседи и в каждой позиции битового вектора будет 1. Так как byte в Java знаковый - это будет число -1.

Если теперь посмотреть на клетку на границе, то у нее не будет некоторых соседей. Мы можем использовать битовый вектор чтобы указать, каких соседей нет у клетки. Например, у клетки с row = 0 и column = 3 не будет соседей 8, 1 и 2, и битовый вектор будет иметь значение 124

А для клетки с row = 4 и column = 0 у клетки будут только соседи 1, 2 и 3. Битовый вектор такой клетки равен 7.

В итоге мы имеем следующее правило:

  • Если row равно 0, удаляем соседей 8, 1, 2 из битового вектора (удалить можно с помощью операции & ~, например 1111 (15) & ~1001(9) = 0110(6) )
  • Если row равно значения rows - 1 (4 в нашем случае), удаляем значения 6, 5, 4
  • Если column равно 0, удаляем 8, 7, 6
  • Если column равно columns - 1 (5 в нашем случае), удаляем 2, 3, 4

Дальше мы прибавляем к общем числу соседей, если сосед есть и он равен true

Соединить края

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

Для красной клетки есть 3 обычные соседние клетки (внизу, справа и справа внизу). Соседней клетки вверху и слева нет, поэтому мы берем самую нижнюю клетку или самую правую. Мы как бы соединяем верхний край с нижним и левый край с правым. Так мы получим трехмерную фигуру тор.

Как это реализовать? Посмотрим на упрощенный пример, в котором только одна строка и 6 столбцов.

Когда значение i = 0, соседняя клетка слева будет иметь значение с i = -1. Нам нужно, чтобы это значение стало (n - 1), т.е. 5.

Когда значение i = 5, соседняя клетка справа будет иметь значение с i = 6. Нам нужно, чтобы это значение стало 0.

Если мы запишем эту строку как две подряд, мы можем заметить что использование модуля от длины строки решит нашу проблему.

Если индекс равен -1, мы прибавляем длину строки и получаем 5, то что нам нужно. Если индекс равен 6, мы вычисляем остаток от деления на длину строки и получаем 0. Мы можем свести обе формулы к одному выражению

i = (i + N) % N, где N - длина строки (количество столбцов).

Это работает и для столбцов, тогда

j = (j + N) % N, где N - длина столбца (количество строк).

Вот что мы получаем в итоге (методы newI и newJ вычисляют новые значения i и j соответственно)

Обновление следующего поколения

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

В конце population становится next, а ссылка на предыдущий population пропадает.

Улучшение

Вся логика на данный момент реализована. Можете запустить приложение и посмотреть как клетки переходят из одного состояния в другое. Теперь сделаем код более читаемым.

Во-первых вся логика и обновления и изображения находится в методе draw(). Разделим вывод на экран методом draw(), обновление состояния методом update() и общий метод redraw(), который будет вызывать оба эти метода.

Добавим метод подсчета соседей neighborsFor

Метод создает 2 цикла, с переменными li и lj (local i и local j). Значения li и lj меняются от -1 до 1, т.е. мы берем все значения в окрестности точки.

Здесь выполняется 9 итераций, т.к. мы считаем саму клетку тоже как сосед клетки. Поэтому если клетка живая, мы вычитаем из числа 1 (строка 9).

Проблемы с памятью

Сейчас каждый фрейм мы выделяем память для двумерного массива. Вот в чем проблема

Изначально у нас есть только один двумерный массив population. Затем мы создаем такой же двумерный массив каждый фрейм, обновляем его значения и присваиваем этот новый массив population. Ссылок на оригинальный массив population теперь нет и его очистит garbage collector. Переменная next будет удалена при выходе из метода обновления. Нам нужно перестать создавать массивы в методе.

Для этого можно воспользоваться копированием или замещением.

Копирование

При копировании мы создаем отдельный массив, например temp, такой же как и population, но на уровне класса. Дальше обновляем этот массив temp и в конце метода обновления копируем все значения из temp в population.

Визуально это выглядит так

В конце метода update мы добавили метод copy, который копирует значения из temp в population. В самом методе update обновляется массив temp.

Замещение

Принцип метода замещения - мы создаем 2 массива и по очереди используем то первый, то второй как основной (и другой как временный соответственно)

Разберем схему обновления поподробнее. Сначала нам нужно создать 2 массива и две переменные t1 и t2, которые всегда будут указывать каждый на свой массив. Затем нам нужно создать 2 ссылки на эти массивы population и temp. Это просто ссылки на те же массивы, в памяти будут только 2 массива и на каждый ведут по 2 ссылки.
Ссылки population и temp будут по очереди указывать то на t1, то на t2.

Нам понадобится некоторый переключатель, по которому мы поймем какой из массивов t1 или t2 сейчас population, а какой temp. Для этих целей подойдет boolean, назовем его toggle.

В начале population указывает на t1, temp на t2. Мы обновляем temp (и t2 соответственно). Обновление temp говорит нам о том, что в следующее поколение игра должны выглядеть именно так. Можно сказать, что population это текущее поколение, а temp - следующее.

Мы могли бы скопировать следующее поколение в текущее (temp в population), как в способе с копированием. Но вместо этого мы переставим ссылки на t1 и t2. То, каким будет temp неважно, он все равно заменит все свои значения в следующий вызов метода. Поэтому мы говорим, что теперь текущее поколение - это t2, а temp t1. Дальше все аналогично, только мы меняем значения обратно: population на t1, а temp на t2. Так они будут менять друг друга постоянно, но в памяти будут только 2 массива.

Для аналогии можно привести пример из сельского хозяйства. Предположим есть 2 поля одинакового по размеру. В первый год вы садите на первом поле, а второе отдыхает. В следующий год вы садите на втором поле, а первое отдыхает. На третий год вы опять садите только на первом поле и т.д.

Замена population и temp происходит в строке 29 - 31.

Наслаждаемся жизнью

Добавим метод init, который задает начальные значения первого поколения. Это могут быть любые правила, в том числе рандомное значение.

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

Заключение

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

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

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

И напоследок несколько интересных ссылок.

Report content on this page

Report Page

Please submit your DMCA takedown request to dmca@telegram.org