Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!
Всем привет! На написание этой статьи меня вдохновил автор YouTube канала PeaAshMeter. В своем видео автор показывает простейший генератор 2D мира, который основан на простейшем правиле клеточного автомата. Что такое клеточный автомат? Какие клеточные автоматы бывают? На эти и многие другие вопросы я попробую ответить.
Проект я решил написать на Python, но поскольку не являюсь экспертом в этой области, то любые замечания, предложения по улучшению кода или проекта — приветствуются!
1. Что такое клеточный автомат?
Клеточным автоматом называют множество клеток, которые можно представить в виде матрицы с x‑строк и y‑столбцов. Пересечение x и y даёт на координату текущую клетку. Состояние у клеток может быть разным. Простейшие клеточные автоматы могут быть лишь в двух состояниях, закрашенным(1) или не закрашенным(0). Для каждой такой клетки определяется окрестность — соседние клетки вокруг текущей. Радиус такой окрестности может быть разным в разных автоматах, как и правило того, каких соседей можно учитывать, например только соседей слева и справа, или только сверху и снизу. Нужна такая окрестность для того, чтобы исходя из состояния клеток соседей изменять состояние текущей клетке, на каждом витке итерации. Изменение состояние текущей клетки происходит по определенным правилам. Например, если текущая клетка имеет состояние не закрашенная(0), а в окрестности есть 3 и более соседа, которые закрашены(1), тогда мы закрашиваем текущую клетку.
Один шаг автомата подразумевает обход всех клеток и на основе данных о текущем состоянии клетки и её окрестности определение нового состояния клетки, которое будет у неё при следующем шаге. Перед стартом автомата оговаривается начальное состояние клеток, которое может устанавливаться целенаправленно или случайным образом. Набор таких простых правил создаёт удивительные анимации, вот один из таких примеров.
Чтобы не растягивать статью, то ограничимся этой вводной, если вы хотите узнать больше, то ниже я приведу ссылки на полезные материалы по теме этой статьи.
2. Хаотичное распределение как начальное состояние
Для этого проекта мы будем использовать PyGame, почему именно его я расскажу в самом конце статьи, а пока примем это как данность. Набросаем основную структуру приложения для PyGame. В инициализации класса App определим разрешение нашего окна, таймер для вывода кадров и класс Biomes, в нём и будет вся логика работы с биомами. В методе run будем отлавливать слушатели кнопок и показывать счетчик fps. Еще нужно создать файл settings, в нем будем хранить константы для проекта, через такой файл мы сможем легко менять настройки проекта, например, ограничитель кадров или базовое разрешение окна.
class App:
def __init__(self):
self.screen = pg.display.set_mode(settings.RES)
self.clock = pg.time.Clock()
self.biomes = bm.Biomes(app=self, pg=pg)
def run(self):
while True:
for event in pg.event.get():
if event.type == pg.QUIT:
pg.quit()
elif event.type == pg.KEYDOWN:
if event.key == pg.K_SPACE:
self.biomes.main_render_biomes()
self.clock.tick(settings.FPS)
pg.display.set_caption(f'FPS: {self.clock.get_fps()}')
if __name__ == '__main__':
app = App()
app.run()Теперь когда базовый класс готов, перейдем к работе с рендером кадров. На первом кадре будет хаотичное распределение суши и моря. Для этого нам подойдет матрица, которая будет заполнена случайным образом. Но чтобы заполнять такую матрицу, нам понадобятся типы биомов поэтому без enum нам не обойтись, в нем мы определим основные биомы с которыми будем работать. У нас будет всего 5 биомов, а именно: суша, море, песок, побережье, лес.
class BiomesType(Enum):
LAND = 1
SEA = 2
SAND = 3
SEA_SHORE = 4
WOODS = 5Теперь создадим метод, который будет инициализировать матрицу случайным распределением суши и моря, их вероятность я выбрал 50%. Нужно еще отметить, что количество столбцов и строк будет равно 300, таким образом при разрешении 600 на 600 пикселей, каждый “пиксель” биома будет равен размеру 2 на 2 реальных пикселя, это нужно учитывать при отрисовке реальных пикселей, поскольку их точка будет смещаться на величину размера “пикселя” биома.
def create_start_matrix(self):
rows = settings.Rows
cols = settings.Columns
matrix = [[0] * cols for _ in range(rows)]
for i in range(rows):
for j in range(cols):
r = random.randint(1, 2)
matrix[i][j] = BiomesType.SEA if (r == 1) else BiomesType.LAND
self.paint_pixel_element(matrix[i][j], i, j)
self.pg.display.update()
return matrixТеперь пару слов про отрисовку. После инициализации каждого элемента матрицы, мы сразу наносим его на холст. Этим занимается метод paint_pixel_element, который принимает тип текущего биома и его координаты. После сравнения типа биома он задает цвет и рисует элемент учитывая реальный размер пикселя и его смещение.
def paint_pixel_element(self, biome, x, y):
if biome == BiomesType.LAND:
color = settings.COLOR_LAND
elif biome == BiomesType.SEA:
color = settings.COLOR_SEA
elif biome == BiomesType.SAND:
color = settings.COLOR_SAND
elif biome == BiomesType.SEA_SHORE:
color = settings.COLOR_SEA_SHORE
elif biome == BiomesType.WOODS:
color = settings.COLOR_WOODS
self.pg.draw.rect(self.app.screen, color,
(x * settings.basicX, y * settings.basicY, settings.basicX, settings.basicY))
После того как мы создали матрицу и отрисовали каждый элемент, нам нужно вызвать метод display.update() для обновления текущего холста, и мы увидим случайное распределение.
3. Порядок из хаоса
Для того чтобы получить упорядоченные группы клеток, которые будут напоминать острова нам следует применить одно из правил клеточного автомата, в этом проекте мы будем использовать правило “День и ночь”(B3678/S34678). Следует отметить, что новое состояние всей матрицы после применение правила называют поколением. С каждым поколением случайное распределение будет носить упорядоченный характер, так что выбор количества поколений может быть разным.
Итак, приступим к созданию первого слоя. Для этого нам необходимо пройтись по сгенерированной матрице и просчитать количество соседей для каждого итерируемого элемента, ещё нужно учитывать углы, чтобы не выйти за индексы матрицы. Если текущая клетка это суша, а счётчик соседних клеток моря равен 3, 6, 7, 8 тогда мы изменяем текущую клетку на море и наоборот для клеток моря. Радиус соседей примем за 1 клетку. Это можно изобразить следующим образом.
def next_generation_lands(self):
for x in range(len(self.matrix)):
for y in range(len(self.matrix[x])):
counter_sea = 0
counter_land = 0
if (x - 1) >= 0:
if self.matrix[x - 1][y] == BiomesType.SEA:
counter_sea += 1
else:
counter_land += 1
if (y - 1) >= 0:
if self.matrix[x][y - 1] == BiomesType.SEA:
counter_sea += 1
else:
counter_land += 1
if (x + 1) <= settings.Columns - 1:
if self.matrix[x + 1][y] == BiomesType.SEA:
counter_sea += 1
else:
counter_land += 1
if (y + 1) <= settings.Rows - 1:
if self.matrix[x][y + 1] == BiomesType.SEA:
counter_sea += 1
else:
counter_land += 1
if (y - 1) >= 0 and (x + 1) <= settings.Columns - 1:
if self.matrix[x + 1][y - 1] == BiomesType.SEA:
counter_sea += 1
else:
counter_land += 1
if (y + 1) <= settings.Rows - 1 and (x + 1) <= settings.Columns - 1:
if self.matrix[x + 1][y + 1] == BiomesType.SEA:
counter_sea += 1
else:
counter_land += 1
if (y - 1) >= 0 and (x - 1) >= 0:
if self.matrix[x - 1][y - 1] == BiomesType.SEA:
counter_sea += 1
else:
counter_land += 1
if (y + 1) <= settings.Rows - 1 and (x - 1) >= 0:
if self.matrix[x - 1][y + 1] == BiomesType.SEA:
counter_sea += 1
else:
counter_land += 1
if self.matrix[x][y] == BiomesType.LAND:
if counter_sea == 3 or counter_sea == 6 \
or counter_sea == 7 or counter_sea == 8:
self.matrix[x][y] = BiomesType.SEA
self.paint_pixel_element(self.matrix[x][y], x, y)
if self.matrix[x][y] == BiomesType.SEA:
if counter_land == 3 or counter_land == 6 \
or counter_land == 7 or counter_land == 8:
self.matrix[x][y] = BiomesType.LAND
self.paint_pixel_element(self.matrix[x][y], x, y)
self.pg.display.update()
Приблизительно через 200 поколений мы наблюдаем, что наш шум теперь выглядит, как архипелаг островов. Я думаю, что такой результат вполне удовлетворительный, поэтому можно приступать к работе над следующим слоем.
4. Пляж и мелководье
Следующим шагом будет создание песочного берега вокруг каждого из островов. Фактически нам просто необходимо сделать обводку вокруг каждого острова, сделать это довольно просто. Для каждой клетки нужно проверить условие: если текущая клетка суша, и она находится между клетками море и сушей, тогда мы меняем ее на песок.
Но, следует отметить, что простой контур островов в виде песка выглядит совсем не естественно, поэтому необходимо добавить случайный эффект для преобразования суши в песок. Воспользуемся старым правилом для формирования суши, только модифицируем его, если у текущего элемента более 5 соседей клеток песка, то с вероятностью в 2% мы будем изменять текущую клетку на песок. После того как пройдёт 100 поколений, мы получим вот такой результат.
Формирование мелководья происходить по такому же принципу, разница лишь в том, что теперь мы проверяем, что клетка находится между песком и морем. Точно так же обводим контур, а после добавляем случайное распределение в 2%.
В итоге после 100 поколений мы получаем мелководье.
5. Лес
Последним слоем мы будем создавать густой лес. Для начала нужно сделать хаотичное распределение, которое будем группировать всё тем же правилом “День и ночь”(B3678/S34678), так что процесс создание леса такой же, как и у первого слоя (суши и моря). Главным отличием есть то, что распределение будет в границах островов, а значит только на клетках суши.
Поколений для отрисовки леса требуется меньше, приблизительно 30. Это связано с тем, что из-за граничных условий количество клеток для леса сильно меньше, поэтому для группировки требуется меньше поколений.
6. PyGame вместо Kivy
Теперь пара слов о том, почему я выбрал PyGame. Изначально я использовал Kivy, у которого есть возможность рисовать примитивы на холсте, но сразу столкнулся с тем, что этот способ крайне неэффективный. Отрисовка каждого поколения происходила только после полного просчёта матрицы, что не давало наглядности, это не удивительно поскольку Kivy больше подходить для построения небольшого UI. В PyGame есть буферизация кадров из коробки (она рисует только те участки, которые были изменены), это позволяет в реал тайме видеть отрисовку карты. Еще одним плюсом будет ограничитель кадров, он позволяет косвенно судить о производительности. Всё это в сумме с хорошей документацией и отличными примерами, заставило меня выбрать PyGame.
В дальнейшем я бы хотел повысить производительность и увеличить разрешение рендеринга карты. В планах реализовать следующие пункты:
Рефакторинг кода.
Использование NumPy, Numba для ускорения работы с матрицей.
Уменьшить обращение к отрисовке.
7. Заключение
В заключении хотелось бы сказать, что потенциал клеточных автоматов большой и применить их можно в разных сферах, генерация 2D мира одно из них. Такой способ довольно простой и универсальный. Если брать только процедурную генерацию ландшафта, то у меня в планах создать генератор на основе алгоритма diamond square или шума Перлина, эти варианты хорошо себя зарекомендовали и их часто используют, поэтому вызывают у меня большой интерес. Спасибо за ваше внимание! Надеюсь, что эта статья была познавательной. И отдельное спасибо, если дочитали до этого места!
Ссылка на исходники проекта.
8. Рекомендованные материалы
Видеоматериал который меня вдохновил
Большая статья с разбором генератора Minecraft
Вики Клеточный автомат
Моделирование лесных пожаров: теория, клеточный автомат на Python
10 удивительно зрелищных простейших клеточных автоматов
Битва дроидов и джедаев на клеточном автомате
Сыграем в "Жизнь"! Клеточный автомат на Python [ Pygame ]
Онлайн конструктор клеточных автоматов
