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

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

-         Понимание основ процедурной генерации воксельных миров.

-         Практические навыки создания простого воксельного ландшафта.

Программа реализована на языке программирования Python. В качестве основного инструмента процедурной генерации используются клеточные автоматы.

Результатом работы описанного процедурного генератора является 3D модель виртуального мира в формате OBJ, который представляет собой сгенерированные участки моря (случайной высоты) и суши. Пример сгенерированного мира:

Исходный код: https://github.com/CoffeeWithFiree/theEngineOfProceduralGenerationOfVirtualWorlds.git

Но не все модули здесь связаны с темой этой статьи, дело в том, что я разрабатываю одну программу для нескольких видов генерации и часть модулей связана с генерацией рогаликовых уровней, которую я также расписал в своей предыдущей статье: https://habr.com/ru/articles/924588 и думаю, что появятся еще и другие виды генераторов если прошло достаточно много времени с публикации этой статьи. Также на момент написания статьи еще не реализован адекватный графический интерфейс и всё редактирование входных данных, условий и т.д. происходит через код, но в будущем это все исправится (если еще не исправилось).

Модули, связанные с темой этой статьи смотри в самом конце, вместе с диаграммой классов.

Теоретические основы клеточных автоматов

Процедурный генератор будет основан на клеточных автоматах, поэтому важно понять, что это такое.

Клеточные автоматы я описывал в своей предыдущей статье о рогаликовом генераторе, поэтому, чтобы не повторяться, попрошу вас перейти на ту самую статью, перейти к главе “Теоретические основы клеточных автоматов” и узнать, что это такое из той статьи, ссылка на неё: https://habr.com/ru/articles/924588

Постановка задачи и настройки

Генерируемый виртуальный мир должен состоять из участков суши и моря. Участки суши должны иметь неровности (холмы, ямы, возможно даже горы), не должно быть летающих участков. Море будет иметь одну высоту (В моём случае генерируемую случайно в диапазоне от 1 до 4 клеток).

Настройки и входные параметры находятся в модуле settings:

    Res = [160, 24, 160] #x #y #z

    width = 80  #x
    height = 12 #y
    length = 80 #z

    color_land = (0, 153, 0)
    color_sea = (0, 102, 255)

    height_water = random.randint(0,3)

    day_and_night_base = 100
    day_and_night_height = 50

    average_percentage_sea = 50 #0 - 100, >= 100: full sea; <= 0 full land

·        Res – разрешение мира;

·        width, height, length – количество кубов в высоту, ширину, длину;

·        color_land и color_sea – цвета кубов суши и моря;

·        height_water – глубина океана, в моём случае генерируется случайным образом от 0 до 3;

·        day_and_night_base – кол-во итераций правила «День и ночь» для суши и моря, подробнее её влияние будет рассмотрено позже;

·        day_and_night_height – кол-во итераций правила «День и ночь» для высоты суши, подробнее её влияние так-же будет рассмотрено позже;

·        average_percentage_sea – среднее соотношение воды к суше, если значение меньше или равно 0, то сгенерированный мир будет одним морем, если больше или равно 100, то моря не будет (для для полного отключения моря нужно еще в height_water поставить 0);

Здесь же хочется упомянуть модуль BiomesType:

class BiomesType:
    air = 0
    land = 1
    sea = 2

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

Запускающий файл

Прежде чем перейдём к генерации, небольшое предисловие о запускающем файле, если вас интересует лишь алгоритм генерации, то можете пропускать эту главу.

Запускающим файлом является модуль MainRasterization3D:

from Rasterization3D import Rasterization3D
from CellularAutomata import CellularAutomata
import numpy as np
import pygame as pg


class main():

    def __init__(self):
        pg.init()
        self.graphic3D = Rasterization3D(self, pg, np)
        self.screen = self.graphic3D.screen
        self.cell_automata = CellularAutomata(pg, np, self.graphic3D)

        self.font = pg.font.SysFont('Arial', 30)

    def run(self):


        pg.display.set_caption('Rasterization')

        running = True
        while running:
            for event in pg.event.get():
                if event.type == pg.QUIT:
                    running = False

            self.screen.fill((255, 255, 255))

            self.cell_automata.DrawingScene()

            text = self.font.render("Generation complete", True, (0, 0, 0))
            text_rect = text.get_rect(center=(self.screen.get_width() / 2, self.screen.get_height() / 2))
            self.screen.blit(text, text_rect)

            pg.display.flip()

        pg.quit()

if __name__ == "__main__":
    app = main()
    app.run()

Импортируем 4 библиотеки: Rasterization3D (моя библиотека по отрисовке простейшей трёхмерной графики, но вместо её использования лучше экспортировать получившуюся модель в OBJ), CellularAutomata (библиотека, реализующая генерацию мира), numpy (библиотека для работы с матрицами, векторами и продвинутыми математическими операциями), pygame (библиотека для работы с графикой, в нашем случае с помощью нее создается окно и выводится надпись о том, что генерация завершена или же, если использовать модуль Rasterization3D, то эта библиотека используется ещё и там).

В функции init инициируем pygame, шрифт, библиотеку Rasterization, окно и запускаем генератор.

В функции run реализован простой цикл на библиотеке pygame, который выполняет следующие функции:

·        Создает окно с заголовком «Rasterization»

·        Обрабатывает событие выхода (закрытие окна)

·        Заливает экран белым цветом

·        Вызывает метод для экспорта сгенерированного мира (сгенерировался он на этапе инициализации)

·        Выводит сообщение о завершении генерации

·        Обновляет дисплей

·        Завершает работу pygame при выходе из цикла

Генерация мира

Генерация мира состоит из нескольких этапов, все их можно увидеть в функции init в модуле CellularAutomata:

    def __init__(self, pg, np, graphic3D):
        self.pg = pg
        self.np = np
        self.graphic3D = graphic3D

        self.matrix = self.CreateStartMatrix()

        for _ in range(settings.day_and_night_base):
            self.matrix = DayAndNight.NextGenerationLands(self.matrix, settings.width, settings.length, BiomesType.sea, BiomesType.land)

        self.MatrixHigh()
        for _ in range(settings.day_and_night_height):
            for y in range(1, settings.height):
                self.matrix = DayAndNight.NextGenerationLandsForHigh(self.matrix, settings.width, settings.length, BiomesType.air, BiomesType.land, y)

        #Water height level
        h = settings.height_water
        print(f"water height level = {h}")
        if h > 0:
            for x in range(0, settings.width):
                for y in range(0, h + 1):
                    for z in range(0, settings.length):
                        if h != y:
                            self.matrix[x][y][z] = BiomesType.sea
                        else:
                            if self.matrix[x][y][z] == BiomesType.air:
                                self.matrix[x][y][z] = BiomesType.sea

Подробное их описание будет ниже, а сейчас кратко:

1.     Начальная генерация

2.     Упорядочивание мира с использованием правила «День и ночь»

3.     Начальная генерация высот

4.     Упорядочивание высот с использованием правила «День и ночь»

5.     Высота моря

Начальная генерация

Код начальной генерации выглядит следующим образом:

def CreateStartMatrix(self):
        Res_x = settings.width  #Right
        Res_y = settings.height  #Up
        Res_z = settings.length  #forward

        matrix = self.np.zeros((Res_x, Res_y, Res_z))  #y-axis fixation: matrix[:, y, :]

        for x in range(Res_x):
            for z in range(Res_z):
                ver = settings.average_percentage_sea
                r = random.randint(1, 100)
                if r > ver:
                    matrix[x, 0, z] = BiomesType.land
                else:
                    matrix[x, 0, z] = BiomesType.sea
        return matrix

Вначале мы получаем размеры мира из настроек и создаем нулевую матрицу состояний соответствующих размеров (нулевая матрица – матрица, всеми значениями которой являются нули), эта матрица будет хранить состояния клеток нашего мира, 0 означает воздух.

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

При вероятности появления клеток суши и моря 50 на 50, получаем примерно следующий результат:

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

Упорядочивание мира с использованием правила "день и ночь"

В связи с популярностью правила «День и ночь» в моих алгоритмах процедурной генерации, было принято решение вынести его в отдельный модуль под названием DayAndNight.

Для наглядного пояснения работы этого правила, снова перенаправляю вас на мою предыдущую статью и на главу в ней «Теоретические основы клеточных автоматов» https://habr.com/ru/articles/924588 . Сейчас же я кратко поясню техническую сторону этого правила.

Код программы выглядит следующим образом:

    def NextGenerationLands(matrix, columns, rows, first_type, second_type):
        """the ordered state of land and sea"""
        y = 0 #Use just for first layer
        warning_amounts = [3, 6, 7, 8]

        for x in range(len(matrix)):
            for z in range(len(matrix[x, y])):
                counters = {"land_counter": 0,
                            "air_counter": 0}


                def NextGenHelper(x, z):
                    if matrix[x][y][z] == second_type:
                        counters["land_counter"] += 1
                    else:
                        counters["air_counter"] += 1

                CellsAround.EightCellsAround(x, z, NextGenHelper, columns, rows)

                #current cell is land
                if matrix[x][y][z] == second_type:
                    if counters["air_counter"] in warning_amounts:
                        matrix[x][y][z] = first_type

                #current cell is air
                elif matrix[x][y][z] == first_type:
                    if counters["land_counter"] in warning_amounts:
                        matrix[x][y][z] = second_type
        return matrix

На вход подаются следующие данные: матрица состояний, ширина мира, длина мира, первое состояние (в нашем случае это море), второе состояние (в нашем случае это суша).

Закрепляем y (высоту) в значение 0 (нижний слой), т.к. пока что мы все еще работаем с двухмерным миром.

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

Запускаем цикл, в котором проходимся по каждой клетке нижнего слоя.

Создаем словарь counters, который отвечает за количество клеток первого типа и второго типа.

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

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

class CellsAround:
    @staticmethod
    def EightCellsAround(x, y, action, columns, rows):
        # [x - 1][z - 1]
        if (x - 1) >= 0 and (y - 1) >= 0:
            action(x - 1, y - 1)

        # [x][z - 1]
        if (y - 1) >= 0:
            action(x, y - 1)

        # [x + 1][z - 1]
        if (x + 1) <= (columns - 1) and (y - 1) >= 0:
            action(x + 1, y - 1)

        # [x - 1][z]
        if (x - 1) >= 0:
            action(x - 1, y)

        # [x + 1][z]
        if (x + 1) <= (columns - 1):
            action(x + 1, y)

        # [x - 1][z + 1]
        if (x - 1) >= 0 and (y + 1 <= (rows - 1)):
            action(x - 1, y + 1)

        # [x][z + 1]
        if (y + 1 <= (rows - 1)):
            action(x, y + 1)

        # [x + 1][z + 1]
        if ((x + 1) <= (columns - 1)) and (y + 1 <= (rows - 1)):
            action(x + 1, y + 1)

На вход подаются 2 координаты текущей клетки, функция, в которой прописано, что нужно делать с клетками вокруг (в нашем случае это функция NextGenHelper, которая считает кол-во клеток первого и второго состояния) и ширина с длиной мира.

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

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

Возвращаем матрицу.

После описания логики упорядочивания мира, я приведу несколько примеров, где будет разное количество итераций упорядочивания. Напоминаю, что кол-во итераций можно изменять в модуле settings в переменной day_and_night_base:

50 итераций:

100 итераций:

150 итераций:

Начальная генерация высот

Код программы:

    def MatrixHigh(self):
        Res_x = settings.width  #Right
        Res_y = settings.height  #Up
        Res_z = settings.length  #forward

        for x in range(Res_x):
            for z in range(Res_z):
                if self.matrix[x, 0, z] == BiomesType.land:
                    step = 100 / Res_y
                    ver = step
                    for y in range(1, Res_y, 1):
                        r = random.randint(1, 100)
                        if r > ver:
                            self.matrix[x, y, z] = BiomesType.land
                            ver += step
                        else:
                            break

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

Далее написан такой алгоритм, при котором вероятность поставить следующую клетку в высоту каждый раз снижается. И шаг, на который мы каждый раз снижаем вероятность создан таким образом, чтобы не была построена клетка, выходящая за границы мира, а именно 100 / высоту мира, т.е. если высота равна 10, то и шаг у нас будет равен 10, причем начальная вероятность равна шагу и в конце (на вершине мира) вероятность построить клетку будет равна 0, потому что при ver == 100, не найдется числа строго больше в диапазоне от 1 до 100. А вероятность снижается за счёт того, что ver постепенно растёт и уменьшается вероятность того, что получим число от 1 до 100, больше текущего значения ver.

Если клетка не была построена (случайное число оказалось больше, чем текущее значение вероятности), то мы оставляем высоту данного участка суши такой, на которой остановились и переходим к следующему участку.

Упорядочивание высот

Реализовано по аналогии с упорядочиванием мира, с помощью того же правила «День и ночь», но с небольшими изменениями:

    @staticmethod
    def NextGenerationLandsForHigh(matrix, columns, rows, first_type, second_type, y):
        """the ordered state of land and sea"""
        warning_amounts = [3, 6, 7, 8]

        for x in range(len(matrix)):
            for z in range(len(matrix[x, y])):

                if matrix[x][y][z] == second_type or matrix[x][y][z] == first_type:

                    counters = {"land_counter": 0,
                                "air_counter": 0}

                    def NextGenHelper(x, z):
                        if matrix[x][y][z] == second_type:
                            counters["land_counter"] += 1
                        else:
                            counters["air_counter"] += 1

                    CellsAround.EightCellsAround(x, z, NextGenHelper, columns, rows)


                    # current cell is land
                    if matrix[x][y][z] == second_type:
                        if counters["air_counter"] in warning_amounts:
                            if y + 1 < matrix.shape[1] and matrix[x][y + 1][z] == first_type:
                                matrix[x][y][z] = first_type

                    # current cell is air
                    elif matrix[x][y][z] == first_type:
                        if counters["land_counter"] in warning_amounts:
                            if y > 0 and matrix[x][y - 1][z] == second_type:
                                matrix[x][y][z] = second_type
        return matrix

Разница в том, что добавился новый параметр y: высота, а также в конце есть дополнительные проверки, направленные на то, чтобы не оказалось блоков, левитирующих в воздухе: if y + 1 < matrix.shape[1] and matrix[x][y + 1][z] == first_type и if y > 0 and matrix[x][y - 1][z] == second_type. Т.е. для земли мы смотрим, нет ли земли сверху, чтобы текущий блок земли поменять на воздух, а для воздуха мы смотрим, есть ли блок земли снизу, чтобы блок воздуха поменять на землю.

В цикле мы проходимся по всем блокам в том числе в высоту количество раз, указанное в переменной day_and_night_height из модуля settings.

Несколько примеров с разным значением итераций:

50 итераций:

10 итераций:

100 итераций:

Высота моря

h = settings.height_water
        print(f"water height level = {h}")
        if h > 0:
            for x in range(0, settings.width):
                for y in range(0, h + 1):
                    for z in range(0, settings.length):
                        if h != y:
                            self.matrix[x][y][z] = BiomesType.sea
                        else:
                            if self.matrix[x][y][z] == BiomesType.air:
                                self.matrix[x][y][z] = BiomesType.sea

Вначале мы получаем высоту моря из модуля настроек.

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

Далее мы проходимся по всему полю по слоям (высоте) от нуля до высоты моря и заливаем все слои водой, кроме последнего. На последнем слое мы заливаем морем лишь пустые участки, которые не являются сушей, чтобы остались островки на уровне моря.

На этом этапе генерация мира завершена.

Диаграмма классов

Здесь модули Rasterization2D и Rasterization3D вам могут не пригодиться, это реализация простейшего движка, используйте, если сразу на месте хотите отрендерить мир, но на самом деле не советую, тк движок еще далек от идеала. Лучше использовать модуль ExportWorld, который экспортирует мир в формате OBJ, затем открывайте с помощью любого 3D редактора, который этот формат поддерживает. Но и экспорт еще также не идеален, дело в том, что каждый куб экспортируется отдельным объектом, что грузит систему и 3D редакторы, в дальнейшем этот модуль будет улучшаться.

Что дальше?

В этой статье я расписал генерацию базового и минимального мира, дальше его можно дорабатывать, добавляя, например, пляжи, леса и другое. Сама реализация тоже далека от идеала в плане оптимизации, сейчас даже на генерацию небольшого мира (При размерах, например, 80x12x80 клеток) уходит достаточно много времени даже на мощном железе. Решением обеих задач я собираюсь заниматься в дальнейшем, как и улучшением экспорта в формат OBJ и дальнейшие мои статьи будут этому посвящены.