Следующая статья поможет вам: Игра жизни Конвея в Swift
Вернуться в блог
«Игра жизни Конвея» — это увлекательная игра-симулятор, и мы собираемся написать ее на Swift! Опираясь на 3 простых правила, мы увидим, какой из пикселей попадет в следующее поколение. Это отличная практика программирования, идеально подходящая для воскресного дня.
«Игра жизни» — клеточный автомат, изобретенный британским математиком Джоном Конвеем (1937–2020). Это симуляция, определяющая простые правила развития популяции (пикселей!) после создания начальной настройки.
Звучит скучно, но это абсолютно увлекательно. Проверь это:
Здесь вы видите планер Госпера. Это конфигурация, которая производит планеры, крошечные штуки, похожие на космические корабли, которые вылетают из середины. Эта «игра», основанная на трех простых правилах и первоначальной настройке, продолжается бесконечно.
Игра «Жизнь» происходит на двухмерной сетке ячеек, например, наподобие пиксельного изображения. Каждая клетка может быть живой или мертвой. В каждом поколении игры вы определяете, какие клетки будут жить в следующем поколении. Это происходит на основе живого/мертвого состояния 8 соседей ячейки и 3 правил.
Эти правила, если быть точным:
- Живая клетка с двумя или тремя живыми соседями выживает.
- Мертвая клетка с тремя живыми соседями становится живой клеткой.
- Все остальные живые клетки умирают в следующем поколении, а все остальные мертвые клетки остаются мертвыми.
Можно сказать, что клетка остается живой, если вокруг нее есть несколько клеток (1). Новые клетки «рождаются», когда вокруг нее появляются 3 клетки (2). Все остальное потеряно (3).
Вот пример того, как это работает для планеров, которые вы видели раньше.
Вы смотрите на стартовую конфигурацию планера. Соседи центральной ячейки выделены. Сохранится ли этот пиксель до следующего поколения? Посчитайте количество живых соседей и убедитесь сами! (Состояние других ячеек также показано на втором изображении.)
А что насчет поворотника? Это простая конфигурация из трех ячеек, которая переключается между горизонтальной и вертикальной линией. Он стабилен, поэтому будет мигать вечно.
Но почему? Центральная ячейка всегда останется живой. Две ячейки на концах чередуются между горизонтальными и вертикальными, потому что у них всегда будет 3 соседа. Интригующе, правда?
Это не все…
- Игра «Жизнь» может имитировать машину Тьюринга; это полнота по Тьюрингу. По сути, вы можете моделировать любой возможный алгоритм в Игре Жизни. Теоретически вы можете создать начальное состояние Жизни, которое производит цифры Пи. Вы можете создать Игру Жизни сама по себе. В вашем воображении закончатся идеи еще до того, как вы исчерпаете «Игру жизни»!
- Концепция Game of Life заключается в том, стабилизируется ли структура клеток за определенное количество поколений. Многие модели будут оставаться хаотичными в течение длительного времени, пока не стабилизируются. Из-за проблемы остановки, общего правила (или проблемы) в теории вычислений, не существует алгоритма, который мог бы предсказать, появится ли более поздний шаблон. Вы можете продолжать играть в Игру Жизни буквально бесконечно. Это неизбежно!
- Game of Life увлекательна и довольно безумна. Быстрый поиск в Интернете покажет вам множество видеороликов со сложными, хаотичными конфигурациями, создающими самые поразительные узоры. Однако вам не нужно сходить с ума, чтобы получить аккуратные выкройки; при простой начальной настройке вы получаете планеры, космические корабли, шоры, пульсары, буханки, лодки и так далее.
Авторы Note: Джон Хортон Конвей (82 года) умер 11 апреля 2020 года от осложнений, вызванных COVID-19. Его неоценимый вклад в математику, теорию игр и информатику выходит далеко за рамки моего понимания. В то же время меня бесконечно завораживает простота «Игры Жизни».
Вы можете получить пример кода для этого руководства в этом репозитории GitHub. Вы найдете 3 проекта:
- Игра «Жизнь» с массивами: игровая площадка с кодом из этого урока.
- Игра «Жизнь с наборами»: альтернативная реализация на основе набора.
- Проект Game of Life Xcode: приложение для iOS с лучшей производительностью на iPhone
В этом уроке мы создадим реализацию, использующую массивы, поскольку она лучше работает на игровой площадке Xcode. Реализация Game of Life, использующая Set, довольно элегантна, но из-за создания/уничтожения тяжелых объектов она плохо работает на игровой площадке Xcode.
Код в этом руководстве был вдохновлен «Игрой жизни» Конвея в Википедии, «Игрой жизни с Functional Swift» Колина Эберхардта и «Игрой жизни» Конвея в Rosetta Code.
Прежде чем мы начнем, давайте обсудим структуру кода, который мы собираемся написать. С высоты птичьего полета эта реализация Game of Life состоит из двух компонентов:
- Структура Grid, которая представляет ячейки Game of Life в двумерном массиве. Он отвечает за расчет следующего поколения.
- Представление GridView (UIView), которое будет отображать сетку на экране. Он просто перебирает ячейки, рисуя черные пиксели, если ячейка живая.
Мы также создадим структуру Factory, содержащую статические функции, создающие шаблон Game of Life. Применив немного волшебства X/Y, мы добавим эти узоры в сетку, чтобы вы могли легко создать первоначальную настройку.
Давайте займемся этим!
Начните свой проект с создания пустой игровой площадки в Xcode. Начнем с чистого листа – интересно!
Затем добавьте следующий код в верхней части игровой площадки:
импортировать UIKit
импортировать поддержку игровой площадки
Мы импортируем UIKit для типа UIView и PlaygroundSupport, чтобы мы могли запускать игровую площадку бесконечно.
Затем добавьте следующий код:
структура сетки
{
var size = (ширина: 50, высота: 50)
вар ячейки:[[Int]]
}
Эта структура Grid представляет собой структуру данных для ячеек в Game of Life. Например, там будут размещены функции, которые будут вычислять новое поколение.
Мы добавили 2 свойства: размер и ячейки. Тип размера (Int, Int), который представляет собой кортеж. Мы назвали два значения в кортеже шириной и высотой. Они соответствуют размеру сетки, поэтому теперь у нас есть сетка размером 50×50 ячеек.
Тип клеток такой. [[Int]]. Это массив массивов целых чисел, точнее, двумерный массив целых чисел. Вы можете представить это как двумерную сетку X/Y из 1 и 0. Мы можем добраться до состояния каждой ячейки с помощью ячеек[x][y]†.
Наконец, добавьте следующий инициализатор в структуру Grid:
в этом() {
self.cells = Array(повторяющийся: Массив(повторяющийся: 0, количество: размер.высота), количество: размер.ширина)
}
Что тут происходит? Приведенный выше код инициализирует свойство ячеек двумерным массивом нулей. Результирующий массив будет иметь размер ширины по высоте. Это пустая сетка ячеек; пустое начало Игры Жизни.
Если вы присмотритесь, вы увидите, что мы делаем 2 вызова Array(repeating:count:). Внутренний вызов будет повторять 0 раз size.height, т. е. строку нулей. Внешний вызов будет повторять внутренний Array() раз size.width, т. е. ряд строк нулей.
†: Для простоты мы используем сетку ячеек в качестве ячеек.[x][y] и назовем это сеткой X/Y. Умный читатель теперь заметит, что индексы в массиве ячеек будут соответствовать координате Y, а индексы ячеек[y] будет соответствовать координате X. Это означает, что если вы распечатаете значения в ячейках, вы увидите сетку Y/X. Если вас это беспокоит, смело транспонируйте массив!
Хорошо, дальше структура Factory. Этот компонент будет иметь некоторые жестко запрограммированные шаблоны ячеек, которые мы можем вставить в структуру Grid. Его API позволяет быстро создавать аккуратные начальные конфигурации для Game of Life без ручного написания 1 и 0.
Добавьте следующий код на свою игровую площадку:
структура Фабрика
{
статический планер() -> [[Int]]
{
возвращаться [
[0, 1, 0],
[0, 0, 1],
[1, 1, 1],
]
}
статическая функция мерцания() -> [[Int]]
{
возвращаться [
[0, 1, 0],
[0, 1, 0],
[0, 1, 0],
]
}
статическая функция случайная (размер: Int) -> [[Int]]
{
var ячейки = Массив (повторяющийся: Массив (повторяющийся: 0, количество: размер), количество: размер)
пусть коэффициенты = 1,0/5,0
для x в 0..= 0 && yd >= 0 && xd < size.width && yd < size.height { ячейки[xd][yd] = вставленные ячейки[x][y] } } } } Давайте посмотрим, как это работает. Эта функция имеет 4 важных аспекта:
- Функция называется InsertCells(_:at:). Вы можете вставить двумерный массив, то есть сетку ячеек, по координатам start.x и start.y.
- Внутри функции мы проходим по двумерному массиву InsertCells. Мы рассматриваем каждую ячейку двумерного массива.
- Внутри цикла мы сначала вычисляем координаты назначения xd и yd. Мы делаем это путем смещения 2D-координаты ячейки с координатами start.x и start.y начальной точки.
- Наконец, мы проверяем, находятся ли места назначения xd и yd в пределах ячеек. Если это так, мы добавляем значение ячейки из вставленных ячеек в свойство ячеек сетки.
Видите, как это работает? По сути, мы берем 2D-массив – (маленький) узор – и добавляем его к (большой) сетке Game of Life. Дополнительным преимуществом является отправная точка: например, вы можете добавить планер в середине сетки, указав значение для start.x и start.y.
Теперь, когда для сетки имеется некоторый код, пришло время нарисовать эту сетку на экране. Мы собираемся сделать это, определив GridView, который является подклассом типа UIView. Вы можете поместить это представление в любое приложение на основе UIKit.
Сначала добавьте следующий код на игровую площадку:
класс GridView: UIView
{
вар сетка = Сетка()
}
Это класс GridView, который является подклассом UIView. У него есть одно свойство, называемое сеткой типа Grid. Это структура, которую мы определили ранее; по сути, мы прикрепляем эту структуру данных к представлению GridView.
Далее добавьте в класс GridView следующую функцию:
переопределить функцию draw (_ rect: CGRect)
{
}
Эта функция draw(_:) является частью UIView, и здесь мы переопределяем ее нашей собственной реализацией. Он вызывается каждый раз, когда представление необходимо (пере) отрисовать. Все, что мы «рисуем» в этой функции, отображается в представлении, так что это идеальный способ отрисовки содержимого сетки (в пикселях).
Вот как будет работать рисунок:
- Получите графический контекст, то есть «холст», на котором мы собираемся рисовать.
- Очистите холст, чтобы начать с чистого листа.
- Заполните холст белым фоном.
- Определите размер ячейки в пикселях на основе сетки и размера представления.
- Переберите каждую координату X/Y в сетке ячеек и, если ячейка есть, нарисуйте черный прямоугольник на холсте в соответствующей координате.
Пойдем!
Настройка холста
Сначала добавьте следующий код в функцию draw(_:):
Guard let context = UIGraphicsGetCurrentContext () еще {
возвращаться
}
context.clear(CGRect(x: 0.0, y: 0.0, ширина: границ.ширина, высота: границы.высота))
Вот что происходит:
- Сначала мы получаем ссылку на графический контекст и присваиваем ее контексту. Если это не удается, функция возвращается и завершает выполнение.
- Затем мы очищаем графический контекст. Все, что там есть, удалено. Мы делаем это внутри прямоугольника (0, 0, ширина, высота).
Заполнение белого фона
Затем добавьте этот код в функцию draw(_:):
context.setFillColor(UIColor.white.cgColor)
context.addRect(CGRect(x: 0.0, y: 0.0, ширина: границ.ширина, высота: границы.высота))
контекст.fillPath()
Это делает следующее:
- Установите цвет заливки на белый, т.е. возьмите ведро с белой краской.
- Определите прямоугольник того же размера, что и вид.
- Залейте этот прямоугольник белым цветом.
Теперь мы нарисовали полностью белый вид.
Рисование клеток
Прежде чем мы сможем нарисовать ячейки Игры Жизни на экране, нам нужно определить размер ячейки в пикселях. Например, наша сетка имеет размер 50×50 ячеек, а размер представления может составлять 400×400 точек (пикселей†), так что это означает, что 1 ячейка имеет размер 8×8 пикселей.
Добавьте в функцию следующий код:
let cellSize = (ширина: границы.ширина/CGFloat(grid.size.width), высота: границы.высота/CGFloat(grid.size.height))
Константа cellSize представляет собой кортеж со значениями ширины и высоты. Оба рассчитываются путем деления ширины представления на width.grid и высоты представления, разделенной на Grid.height.
соответственно. Представление разделено сеткой, и теперь у нас есть отдельная ячейка размером cellSize.width × cellSize.height пикселей.
†: Технически приложения iOS используют концепцию «точек» для учета плотности экрана (DPI) между различными устройствами iPhone/iPad. В этом уроке вы можете считать точки и пиксели синонимами. Узнайте больше здесь: Объяснение масштабирования изображения в 1x, 2x и 3x на iOS.
Затем добавьте следующий код. Цвет заливки станет черным:
context.setFillColor(UIColor.black.cgColor)
Наконец, добавьте следующий код в функцию draw(_:):
для х в 0..
Потрясающий!
На данный момент мы создали Grid с ячейками, создали Factory для шаблонов ячеек (например, планер) и создали GridView, который будет рисовать сетку Game of Life на экране. Давайте применим этот код!
Добавьте следующий код на свою игровую площадку внизу кода, ниже всего остального:
PlaygroundPage.current.needsIndefiniteExecution = true
пусть GridView = GridView (кадр: CGRect (x: 0, y: 0, ширина: 400, высота: 400))
PlaygroundPage.current.liveView = GridView
GridView.grid.insertCells(Factory.glider(), at: (x: 2, y: 2))
GridView.grid.insertCells(Factory.glider(), at: (x: 10, y: 10))
GridView.grid.insertCells(Factory.blinker(), at: (x: 5, y: 10))
GridView.grid.insertCells(Factory.random(size: 20), at: (x: 20, y: 20))
GridView.setNeedsDisplay()
Вот что делает код:
- Включить бесконечное выполнение для этой игровой площадки; это означает, что игровая площадка не прекратит выполнение в конце кода, поэтому мы сможем использовать таймеры и асинхронное программирование. (Эта настройка понадобится нам позже.)
- Создайте экземпляр GridView размером 400×400 точек и назначьте его компоненту liveView игровой площадки. Если эта сетка установлена, она теперь будет отображаться в режиме Live View игровой площадки. Вы можете показать/скрыть его с помощью Option + Command + Enter.
- С помощью InsertCells(_:at:) мы добавляем в сетку набор предустановленных шаблонов Game of Life. Вы смотрите на кучу планеров, поворотник и несколько случайных точек. Не стесняйтесь добавлять еще! (Только внутри прямоугольника (0, 0, 50, 50).)
- Наконец, setNeedsDisplay() проверит GridView, что его необходимо перерисовать. Это вызовет функцию draw(_:), которая отрисует содержимое GridView.grid.cells на экране.
Вот что вы должны увидеть на своем экране сейчас:
В следующем разделе мы собираемся вычислить следующее поколение Game of Life, просматривая каждую ячейку и проверяя, живы они или мертвы. Но прежде чем мы сможем это сделать, нам нужно будет написать функцию, которая будет определять, доживет ли отдельная клетка до следующего поколения. Давайте закодируем это!
Сначала добавьте в структуру Grid (!) следующую функцию:
func StaysAlive(_ x: Int, _ y: Int, isAlive: Bool) -> Bool
{
}
Функция StaysAlive(_:_:isAlive:) определяет, останется ли ячейка с координатами сетки (x, y) живой в следующем поколении. Он вернет true для живых и false для мертвых.
Параметр isAlive типа Bool используется для указания того, что ячейка активна в текущем поколении. Этот статус важен для определения того, останется ли клетка живой в следующем поколении.
Внутри функции StaysAlive() нам нужно будет определить, останется ли ячейка живой. Как мы обсуждали в начале этого урока, мы будем использовать 3 правила для определения судьбы клетки:
- Живая клетка с двумя или тремя живыми соседями выживает.
- Мертвая клетка с тремя живыми соседями становится живой клеткой.
- Все остальные живые клетки умирают в следующем поколении, а все остальные мертвые клетки остаются мертвыми.
Алгоритм, который мы используем для этого, проще, чем вы думаете – он состоит всего из двух компонентов! Сначала мы подсчитываем количество живых соседей, а затем принимаем решение по этому числу и состоянию isAlive. Очень просто!
Сначала добавьте в функцию следующий код:
количество вар = 0
пусть пары = [
[-1,-1], [0,-1], [1,-1],
[-1, 0], [1, 0],
[-1, 1], [0, 1], [1, 1]
]
Переменная count используется для отслеживания количества живых соседей. Разумеется, все начинается с нуля.
Константа пары представляет собой двумерный массив с относительными координатами X/Y. По сути, это матрица пар X/Y. Представьте себе ячейку, а затем представьте, что вы помещаете поверх нее матрицу 3×3.
Каждый из 8 соседей ячейки соответствует элементу массива пар. Например, (-1, -1) — это ячейка в верхнем левом углу относительно центральной ячейки. (Мы используем форматирование, чтобы облегчить чтение этого кода.)
Далее мы собираемся перебрать пары. Добавьте этот код в функцию:
для пары в парах
{
пусть xd = x + пара[0]
пусть yd = y + пара[1]
}
Выглядит знакомо? Проходя цикл по массиву пар, мы берем значения X и Y, пара[0] и пара[1] соответственно, и добавьте их к параметрам x и y функции StaysAlive().
Пример:
- Мы определяем, должна ли ячейка в (3, 3) оставаться живой.
- Перебирая пары, находим относительную координату (-1, -1)
- Это соответствует абсолютной координате (2, 2), поскольку (2, 2) == (3 + -1, 3 + -1) == (3 – 1, 3 – 1). (Помните, плюс и минус — это минус!)
Затем добавьте следующий код внутри цикла for in под существующим кодом:
если xd >= 0 && yd >= 0 &&
xd < размер.ширина && yd < размер.высота && ячейки[xd][yd] == 1 { count += 1 } Что здесь происходит? Вы видите 4 шага:
- Установив относительные координаты xd и yd, проверьте, больше ли они или равны нулю, то есть внутри границ сетки.
- Проверьте, меньше ли они ширины и высоты сетки, т. е. находятся ли в пределах сетки.
- Проверьте, есть ли ячейка в ячейках[xd][yd]то есть соседняя ячейка, жива – ее значение равно 1, если она жива, и 0, если она мертва.
- Если все это правда, увеличьте счет на 1, потому что мы нашли живую соседнюю ячейку!
Давайте теперь подведем краткий итог. Мы пытаемся выяснить, должна ли данная ячейка в сетке остаться живой в следующем поколении. Мы знаем его координату, поэтому, используя матрицу ячеек вокруг этой координаты, мы проверяем их статус. Просматривая каждую из соседних ячеек, мы проверяем, живы ли они. Если сосед жив, мы увеличиваем счетчик на 1.
Наконец, добавьте следующий код в функцию StaysAlive() вне цикла for in, под существующим кодом:
if isAlive && (count == 2 || count == 3) {
вернуть истину
} else if !isAlive && count == 3 {
вернуть истину
}
вернуть ложь
Ах, что это!? Это похоже на правила Игры Жизни, верно? Кто знал, что это может быть так просто…
- Если ячейка, которую мы проверяем, в настоящее время жива, и количество ее живых соседей равно 2 или 3, текущая ячейка остается живой.
- Если ячейка, которую мы проверяем, неживая и у нее есть 3 живых соседа, то текущая ячейка остается/становится живой.
- Что-нибудь еще? Извините, вы мертвы!
Потрясающий! На этом работа над функцией StaysAlive() завершается. Мы готовы применить это к сетке сейчас и вычислить следующее поколение.
Когда вы разбиваете проблему на более мелкие подзадачи и решаете их, «большую» проблему становится легче решить. Это одно из чудес компьютерного программирования. Мы проделали всю эту работу только для того, чтобы упростить программирование ядра Game of Life — вычислений следующего поколения. Давайте займемся этим!
Добавьте следующий код в структуру Grid:
генерация мутирующей функции()
{
var nextCells = Array(повторяющийся: Array(повторяющийся: 0, количество: size.height), количество: size.width)
для х в 0..
Что еще можно сказать об этой функции!? Мы проходим по сетке, вычисляем состояние мертвой/живой каждой ячейки и фиксируем следующее поколение в свойстве ячеек сетки. Потрясающий!
И последнее, но не менее важное: нам понадобится код, чтобы собрать все это воедино. Мы создали Grid, GridView и некоторый код для вычисления следующих поколений. По сути, вы можете поместить это в цикл и позволить ему работать вечно.
Именно это мы и собираемся сделать! Добавьте следующий код на игровую площадку под существующим кодом:
пусть таймер = DispatchSource.makeTimerSource()
timer.schedule(крайний срок: .now(), повторение: .миллисекунды(500))
timer.setEventHandler(обработчик: {
GridView.grid.генерация()
DispatchQueue.main.async {
GridView.setNeedsDisplay()
}
})
таймер.активировать()
Этот код создает таймер, который повторяет некоторый код каждые 500 миллисекунд. Вы можете видеть, что мы вызываем функцию генерации() в сетке, а затем вызываем setNeedsDisplay(), чтобы перерисовать представление. В последней строке мы активируем таймер.
Проблема с работой Game of Life заключается в том, что вычисления должны происходить в последовательной очереди. Вы можете вычислить только одно поколение, а затем следующее, следующее и так далее. Что не работает, так это параллельный или параллельный процесс.
Скорость вычислений также важна, особенно на игровой площадке Xcode. Вычисления потенциально могут замедлиться, если в сетке присутствует больше ячеек или когда ваш Mac делает что-то еще. Вот почему мы запускаем функцию генерации() только раз в 0,5 секунды.
Почему мы не использовали здесь более простой компонент Timer? Этот компонент Timer для выполнения работы использует цикл выполнения и работает асинхронно. DispatchSourceTimer, который возвращает makeTimerSource(), использует последовательную фоновую очередь по умолчанию, поэтому мы гарантируем, что работа выполняется последовательно. Два поколения не могут пересекаться, так сказать.
Внутри обработчика таймера, после вызова Generation(), мы переходим в основной поток и планируем там setNeedsDisplay(), то есть перерисовку. Это должно происходить асинхронно, но это также означает, что вычисления в генерации() потенциально могут выполняться быстрее, чем обновляется представление. Мы избегаем этого, устанавливая разумный темп (500 мс) для таймера.
Быстрый Note: В пример кода я включил пример приложения для iOS, которое вы можете запустить на своем iPhone. Рендеринг представлений на iPhone происходит намного быстрее, чем то же самое на игровой площадке Xcode. Я видел хорошую производительность при запуске таймера каждые 50 миллисекунд или около того. Это означает, что вы можете моделировать больше поколений за меньшее время!
Вот и все! Запустите игровую площадку Xcode или приложение для iPhone и увидите, как «Игра жизни» Конвея оживает. Потрясающий!
