Предисловие

Программа реализована на языке Python.

Отрисовываться сгенерирированные уровни будут с помощью реализованного мной простейшего растрового движка, который реализован в модулях Rasterization2D и Rasterization3D. Весь проект на GitHub.

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

Генерируемые виртуальные миры будут иметь следующую структуру: будет определенное количество островов (уровней), которые должны иметь размер в диапазоне от k до j клеток. Из начального острова D можно попасть в конечный остров E, преодолев какое-то количество промежуточных островов. Допускаются развилки (имеется выбор, с текущего острова A можно попасть на остров B или же на остров C).

В моем случае разрешение всего мира будет 48 (по оси x) на 4 (по оси y) на 48 (по оси z) вокселей (воксель, это тоже самое, что пиксель, но в трёхмерном пространстве), при этом пускай одна ячейка клеточного автомата будет иметь размеры 2 вокселя по всем трём осям. Состояния клетки: воздух (air_RL) и суша (land_RL). Воздух будет представлять собой пустое пространство, а суша, это куб, для которого выбран зелёный цвет (0, 153, 0) по RGB.

Для примера зададим следующие ограничения на количество и размеры островов: пускай в результате работы программы будет генерироваться 9 - 13 островов, которые имеют размер 18-23 клетки.

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

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

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

Автоматом называют устройство (или совокупность устройств), которое без непосредственного участия человека выполняет процессы приема, преобразования и передачи энергии, материалов или информации в соответствии с заложенной в него программой. Нас интересуют автоматы, выполняющие дискретное преобразование информации, для которых заданы множества А входных сигналов, Q внутренних состояний и V выходных сигналов, а также две функции: функция переходов и функция выходов. Первая определяет, в какое состояние q’ (из множества возможных состояний Q) перейдет автомат, если он находится в состоянии q и на вход поступил сигнал, а вторая показывает, какой при этом образуется выходной сигнал v (из множества выходных сигналов V): X(q, a) = v. . Подобные автоматы называются конечными.

Клеточные автоматы являются частным случаем конечных автоматов. Клеточный автомат можно представить, как регулярную решетку (или «таблицу») ячеек («клеток»), каждая из которых может находиться в конечном числе возможных состояний, например 0 или 1. Состояние системы полностью определяется значениями переменных в каждой клетке. Важными особенностями клеточных автоматов являются следующие:

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

Каждому элементу клеточного автомата ставится в соответствие элементарный автомат, имеющий форму квадрата (реже треугольника или шестиугольника) и именуемый клеткой. Совокупность клеток образует клеточное пространство, в котором функционирует клеточный автомат. В зависимости от свойств моделируемого объекта, выбирают различные типы окрестностей, в простейшем случае это 4 или 8 клеток вокруг текущей:

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

Самое популярное правило для процедурной генерации, это правило, которое известно под названием «день и ночь», которое гласит следующее: пусть мы рассматриваем 2 вида поверхностей. Если текущее состояние первое, то запускаем счетчик и проходимся по всем клеткам вокруг (по 8), считаем клетки, которые второго состояния, если их 3, 6, 7 или 8, то меняем текущую клетку с первого состояния на второе. Данное правило хорошо тем, что спустя примерно 200 итераций мы группируем в аккуратную и красивую структуру случайно разбросанные клетки с первым и вторым состоянием.

Например, была реализована небольшая программа, которая случайным образом (с вероятностью 50 на 50 процентов) раздает состояния суша или море для каждой клетки в клеточном пространстве, затем в цикле на 200 итераций к этому клеточному пространству применяется правило «день и ночь»:

Случайное распределение клеток суши и моря

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

Для начала необходимо сгенерировать начальную структуру уровней и затем их чуть подзгруппировать с помощью правила "День и ночь".

Для этого был создан класс RoguelikeKA, который на вход получает ссылку на класс main (управляющий программой), ссылки на библиотеки pygame, numpy и Rasterization3D (Класс, реализующий 3D движок).

Первым делом необходимо создать нулевую трёхмерную матрицу, которая будет хранить состояния всех клеток: self.matrix. Размеры матрицы заранее заготовлены в модуле settings, где эти значения, это разрешение, деленное на 2 (как было оговоренно ранее, 1 клетка, это воксель размером 2x2x2). Итого матрица будет размером 24 (по оси x) на 2 (по оси y) на 24 (по оси z). Следующим шагом мы проходимся в цикле по всем значениям матрицы по нулевому слою и генерируем случайное число от 1 до 3 и если выпала 1, то текущей клетке присваиваем состояние «суша», иначе «воздух» (1/3 вероятность выбрана экспериментальным путем, так мы получаем начальную группировку островов наиболее подходящую для нужного мира). Клетки при y больше 0 становятся воздухом:

 def CreateStartMatrix(self):
        Res_x = settings.width_RL  # Right
        Res_y = settings.height_RL  # Up
        Res_z = settings.length_RL  # forwardd

        matrix = self.np.zeros((Res_x, Res_y, Res_z))
        for y in range(Res_y):
            for x in range(Res_x):
                for z in range(Res_z):
                    if y == 0:
                        r = random.randint(1, 3)
                        matrix[x, y, z] = BiomesType.land_RL if (r == 1) else BiomesType.air_RL
                    else:
                        matrix[x, y, z] = BiomesType.air_RL

        return matrix

Итак, у нас есть начальная расстановка островов, но заранее известно, что после случайной расстановки суши, мир с наибольшей вероятностью имеет хаотичную структуру Чтобы привести в порядок острова и немного их сгруппировать, необходимо к нижнему слою применить правило «День и ночь». Для этой задачи была создан класс DayAndNight и функция NextGenerationLands. Создаем список из критических значений (при которых меняется состояние текущей клетки на противоположное): [3, 6, 7, 8]. Проходимся по всем клеткам нижнего слоя и для текущей клетки смотрим ее 8 окружающих клеток и считаем, сколько вокруг клеток воздуха и сколько клеток суши. Узнав состояние текущей клетки, смотрим, сколько клеток противоположного состояния и если их количество попадает в список критических значений, то меняем текущее состояние на противоположное:

class DayAndNight():
    @staticmethod
    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

Модуль CellsAround, используемый здесь выглядит следующим образом:

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)

Оптимальным количеством итераций правила «День и ночь» будет 20. Нам нужно 9-13 островов с размерами 18-23 клетки, а правило «День и ночь» с течением итераций группирует острова в один большой. Нужную группировку дает именно 20 итераций, примерно в 50 процентов случаев получается сразу же нужное количество островов.

Теперь можно отрисовать генерируемые миры. Для этой задачи реализована соответствующая функция под названием «DrawingScene». В ней задается куб размерами 2 на 2 на 2 вокселя, расположенный в центре координат мира. Далее мы проходимся по всем ячейкам клеточного автомата и там, где состояние клетки «суша», отрисовываем куб по индексу клетки, умноженному на 2, используя для этого метод RenderScene из модуля Rasterization3D (полный код функции смотри по ссылке в начале статьи в модуле RoguelikeKA).

def DrawingScene(self):
        vertices = {0: self.np.array([1, 1, 1]),
				...
                    7: self.np.array([1, -1, -1])}
        triangles_land = {0: {0: vertices[0], 1: vertices[1], 2: vertices[2], "color": settings.color_land_RL},
...
                     11: {2: vertices[2], 7: vertices[7], 3: vertices[3], "color": settings.color_land_RL}}
        objects = dict()
        Res_x, Res_y, Res_z = self.matrix.shape
        i = 0
        for x in range(Res_x): for z in range(Res_z):
                for y in range(Res_y):
                    def CreateObj(triangles):
                        nonlocal i      vertices_cur = vertices
                        triangles_cur = triangles
                        position_cur = self.np.array([x * 2 + 15, y * 2 + 35, z * 2 + 25])
                        object_cur = {"vertices": vertices_cur, "triangles": triangles_cur, "postition": position_cur}
                        objects[f"object{i}"] = object_cur
                        i += 1
                    if self.matrix[x, y, z] == BiomesType.land_RL:
                        CreateObj(triangles_land)
        self.graphic3D.RenderScene(objects)

В результате работы данной программы, получим примерно следующий виртуальный мир:

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

У нас есть начальный процедурный генератор виртуальных миров. На данном этапе он не гарантирует, что у нас будет ровно нужное количество островов и каждый из них будет нужных размеров. Ситуация такова, что при каждой генерации, в мире будет минимум 2 острова размера 1 клетка и еще минимум 2 с размерами от 2 до 17, а также каждые 2-4 генерации попадаются острова размером более 50 клеток. Данная ситуация видна на изображении выше. Здесь все острова, кроме, вероятно, одного имеют размер менее 18, а 7 из них и вовсе размером 1 клетка. Такая ситуация нас не устраивает, необходимо прописать алгоритм, который будет упорядочивать острова.

Для начала необходимо отделить все острова друг от друга. Для этой задачи в программу введена важная матрица: self.matrix_cond, это двумерная матрица, которая дублирует нижнюю плоскость self.matrix, но вместо состояний суша и воздух, в этой матрице хранится индекс острова (от 1, до n), а там, где нет островов, хранится значение 0. Также необходимо посчитать текущее количество островов, для этого будет использоваться переменная self.amounts_lands. Словарь self.size_of_land служит для того, чтобы хранить размер каждого острова (ключ: индекс острова, значение: размер острова). Для заполнения матрицы self.matrix_cond создана функция CounterLand. Для начала создаем нулевую матрицу self.matrix_cond. Следующим шагом проходимся в цикле по всем клеткам нижней плоскости мира и там, где self.matrix_cond равна нулю (еще не отметили остров по этому индексу) и в self.matrix состояние равно land_RL (остров), запускаем алгоритм Flood feel по текущим координатам и так до тех пор, пока не пометим каждый остров:

 def CounterLand(self):
        """a counter for the number of islands and their sizes"""
        Res_x = settings.width_RL  # Right
        Res_y = settings.height_RL  # Up
        Res_z = settings.length_RL  # forward
        matrix_cond = self.np.zeros((Res_x, Res_z))

        number_of_matrix = 1
        size_of_land = dict()
        for i in range(len(self.matrix)):
            for j in range(len(self.matrix[i][0])):
                if matrix_cond[i][j] == 0 and self.matrix[i][0][j] == BiomesType.land_RL:
                    flood_feel = FloodFeelCounter(self.matrix, matrix_cond, i, j, number_of_matrix, self.np)
                    matrix_cond, size_of_land[number_of_matrix] = flood_feel.Feel()
                    number_of_matrix += 1
        return matrix_cond, size_of_land, number_of_matrix - 1

Алгоритм Flood feel работает следующим образом: создаем стэк (способ организации данных, который соответствует принципу «последним пришёл, первым вышел» или LIFO), в который изначально помещаем текущие координаты в цикле, затем идет проверка, имеет ли клетка по текущим координатам в матрице состояний self.matrix состояние суша, а в матрице self.matrix_cond значение 0 (еще не помеченный остров). Если условие истинно, то отмечаем эту клетку, как часть текущего острова и добавляем в стэк все клетки вокруг. Продолжаем до тех пор, пока не опустошим стэк:

from collections import deque

class FloodFeelCounter:
    def __init__(self, matrix, matrix_cond, x, z, value, np, min_limit = 0):
        self.matrix = matrix
        self.matrix_cond = matrix_cond
        self.x = x
        self.z = z
        self.x_len = len(matrix)
        self.z_len = len(matrix[0][0])
        self.condition = matrix[x][0][z]
        self.value = value
        self.np = np
        self.min_limit = min_limit

    def Feel(self):
        stack_ = deque([(self.x, self.z)])
        counter = 0
        while stack_:

            r, c = stack_.pop()
            if self.matrix[r][0][c] == self.condition and self.matrix_cond[r][c] == 0:
                self.matrix_cond[r][c] = self.value
                counter += 1

                if r + 1 < self.x_len:
                    stack_.append((r + 1, c))
                if r - 1 >= 0:
                    stack_.append((r - 1, c))
                if c + 1 < self.z_len:
                    stack_.append((r, c + 1))
                if c - 1 >= 0:
                    stack_.append((r, c - 1))

        return self.matrix_cond, counter

В результате работы, матрица matrix_cond будет выглядеть следующим образом:

Матрица с индексами островов self.matrix_cond

Теперь, прежде чем приступить к упорядочиванию островов, необходимо пресечь ситуацию, когда относительно какого-то острова, на углу находится клетка другого острова. Эта ситуация плоха тем, что мы не сможем проложить путь между этими двумя островами, не соединив их в один остров. Эта ситуация проиллюстрирована на следующем рисунке, здесь острова 13, 14 и 17 расположены по углам острова 6.

Для решения этой задачи была реализована функция FixDiagonalConflict. Эта функция работает следующим образом: для каждой клетки матрицы self.matrix_cond, которая является сушей с помощью вспомогательной функции CheckAround проверяем, есть ли чужие острова вокруг клетки (под чужими островами понимаются острова, которые не являются островами текущей клетки). Если есть, то ищем их по диагоналям от клетки и удаляем их. Также проверяем удалили ли мы целый остров или же лишь клетку острова и в первом случае удаляем данные об этом острове и уменьшаем счетчик островов на 1:

    def FixDiagonalConflict(self):                      
        """Removing islands at the corners of other islands"""
        for x in range(len(self.matrix_cond)):
            for y in range(len(self.matrix_cond[x])):
                if self.matrix_cond[x][y] != 0:
                    if self.CheckAround(x, y, self.matrix_cond[x][y]) == False:
                        # [x - 1][y - 1]
                        if (x - 1) >= 0 and (y - 1) >= 0:
                            if self.matrix_cond[x - 1][y - 1] != 0 and self.matrix_cond[x - 1][y - 1] != self.matrix_cond[x[y]:
                                self.CheckZeroIsland(self.matrix_cond[x - 1][y - 1])
                                self.matrix_cond[x - 1][y - 1] = 0

                        # [x + 1][y - 1]
                        if (x + 1) <= (settings.columns - 1) and (y - 1) >= 0:
                            if self.matrix_cond[x + 1][y - 1] != 0 and self.matrix_cond[x + 1][y - 1] != self.matrix_cond[x][y]:
                                self.CheckZeroIsland(self.matrix_cond[x + 1][y - 1])
                                self.matrix_cond[x + 1][y - 1] = 0

                        # [x - 1][y + 1]
                        if (x - 1) >= 0 and (y + 1 <= (settings.rows - 1)):
                            if self.matrix_cond[x - 1][y + 1] != 0 and self.matrix_cond[x - 1][y + 1] != self.matrix_cond[x][y]:
                                self.CheckZeroIsland(self.matrix_cond[x - 1][y + 1])
                                self.matrix_cond[x - 1][y + 1] = 0

                        # [x + 1][y + 1]
                        if ((x + 1) <= (settings.columns - 1)) and (y + 1 <= (settings.rows - 1)):
                            if self.matrix_cond[x + 1][y + 1] != 0 and self.matrix_cond[x + 1][y + 1] != self.matrix_cond[x][y]:
                                self.CheckZeroIsland(self.matrix_cond[x + 1][y + 1])
                                self.matrix_cond[x + 1][y + 1] = 0
                                                                                                                          
    def CheckZeroIsland(self, number_of_land):
        """Checking that the island is no more"""
        self.size_of_land[number_of_land] -= 1
        if self.size_of_land[number_of_land] == 0:
            del self.size_of_land[number_of_land]
            self.amounts_lands -= 1

Здесь функция CheckAround проверяет все 8 клеток вокруг текущей клетки и если какая-то клетка не равна 0 и не равна номеру текущего острова, то возвращает False, иначе True:

    def CheckAround(self, x, y, number_of_land):           
        """A function that checks that there are no foreign islands around the cell"""
        # [x - 1][y - 1]
        if (x - 1) >= 0 and (y - 1) >= 0:
            if self.matrix_cond[x - 1][y - 1] != 0 and self.matrix_cond[x - 1][y - 1] != number_of_land:
                return False

        # [x][y - 1]
        if (y - 1) >= 0:
            if self.matrix_cond[x][y - 1] != 0 and self.matrix_cond[x][y - 1] != number_of_land:
                return False

        # [x + 1][y - 1]
        if (x + 1) <= (settings.columns - 1) and (y - 1) >= 0:
            if self.matrix_cond[x + 1][y - 1] != 0 and self.matrix_cond[x + 1][y - 1] != number_of_land:
                return False

        # [x - 1][y]
        if (x - 1) >= 0:
            if self.matrix_cond[x - 1][y] != 0 and self.matrix_cond[x - 1][y] != number_of_land:
                return False

        # [x + 1][y]
        if (x + 1) <= (settings.columns - 1):
            if self.matrix_cond[x + 1][y] != 0 and self.matrix_cond[x + 1][y] != number_of_land:
                return False

        # [x - 1][y + 1]
        if (x - 1) >= 0 and (y + 1 <= (settings.rows - 1)):
            if self.matrix_cond[x - 1][y + 1] != 0 and self.matrix_cond[x - 1][y + 1] != number_of_land:
                return False

        # [x][y + 1]
        if (y + 1 <= (settings.rows - 1)):
            if self.matrix_cond[x][y + 1] != 0 and self.matrix_cond[x][y + 1] != number_of_land:
                return False

        # [x + 1][y + 1]
        if ((x + 1) <= (settings.columns - 1)) and (y + 1 <= (settings.rows - 1)):
            if self.matrix_cond[x + 1][y + 1] != 0 and self.matrix_cond[x + 1][y + 1] != number_of_land:
                return False

        return True

На этом этапе подготовка к упорядочиванию островов завершена. Начать алгоритм упорядочивания стоит с создания массивов, в которых содержатся подходящее количество островов и подходящие размеры этих островов: self.need_lands = self.np.array([9, 10, 11, 12, 13]) и self.need_size = self.np.array([18, 19, 20, 21, 22, 23]). Следующим шагом необходимо определить статус количества островов (мало, достаточно или много сейчас островов в мире). Для этой задачи используется переменная под названием status_amount_of_lands и функция SetStatusAmounts, которая просто сравнивает текущее количество островов с нужным количеством островов:

    def SetStatusAmount(self):
        """sets the status as to whether the current number of islands is greater, less, or equal to the one we need"""
        if self.amounts_lands > self.need_lands[-1]:
            return "more"
        elif self.amounts_lands < self.need_lands[0]:
            return "less"
        elif self.amounts_lands in self.need_lands:
            return "equel"

Далее начинается большой цикл while, который длится до тех пор, пока количество островов не равно нужному количеству или пока хоть один остров не подходящего размера. Внутри этого цикла создается сигнал равный False, который изменит свой статус на True если с миром было произведено хоть одно изменение за один проход по всем островам. Если же сигнал не изменится за весь проход, это значит, что все острова нужных размеров и мы не сможем повлиять на количество островов, изменяя текущие острова, значит нам нужно просто добавить недостающее количество островов или удалить лишние. Далее создаем копию словаря size_of_land, который содержит индексы островов и их размеры и проходимся по элементам этого словаря, проходясь тем самым по всем островам в мире.

Первым шагом в проходе по островам, необходимо определить их границы и центр для того, чтобы не проходиться по клеткам всего мира и не искать остров, а проходиться по границам острова. Для этой задачи создана функция SearcIslGeomCentAndBords. Функция работает следующим образом: создаются 2 списка по оси x и оси y (минимумы и максимумы). В цикле проходимся по всем клеткам мира и если текущая клетка, это клетка текущего острова, то проверяется, меньше ли индекс этой клетки по оси x или y минимального индекса в массиве, а затем проверяется больше ли максимального, если какое-то условие выполнено, то соответствующий индекс в массиве по соответствующей оси заменяется на текущий индекс. Так в результате получим границы острова. Центральная точка острова вычисляется по формуле арифметического среднего, т.е. минимальная граница сложить с максимальной границей и разделить на 2

class SearchingIslandGeometricCenterAndBorders:
    @staticmethod
    def SearcIslGeomCentAndBords(number_of_land, matrix_cond):
        """search for the geometric central cell of the island and borders"""
        sides_x = [len(matrix_cond), 0]  # min and max
        sides_y = [len(matrix_cond[0]), 0]  # min and max

        for x in range(len(matrix_cond)):
            for y in range(len(matrix_cond[x])):
                if matrix_cond[x][y] == number_of_land:
                    if x < sides_x[0]:
                        sides_x[0] = x
                    if x > sides_x[1]:
                        sides_x[1] = x

                    if y < sides_y[0]:
                        sides_y[0] = y
                    if y > sides_y[1]:
                        sides_y[1] = y

        centr = [int(sum(sides_x) / 2), int(sum(sides_y) / 2)]
        return centr, sides_x, sides_y

После того, как получены границы острова и его центр, проверяется меньше ли размер текущего острова или больше нужного размера. Для начала рассмотрим ветку, где размер острова меньше нужного размера. Здесь идет проверка на статус количества островов. Если островов слишком много, то необходимо удалить текущий остров, пересчитать количество островов и статус количества островов. Для непосредственного удаления острова создана функция DeleteIsland, которая работает следующим образом: проходимся в цикле по границам острова и если текущая клетка, это клетка текущего острова, то просто зануляем эту клетку (что означает, что теперь эта клетка является воздухом):

    def DeleteIsland(self, number_of_land, sides_x, sides_y):
        """removes the island with the specified number from the matrix"""
        for i in range(sides_x[0], sides_x[1] + 1):
            for j in range(sides_y[0], sides_y[1] + 1):
                if self.matrix_cond[i][j] == number_of_land:
                    self.matrix_cond[i][j] = 0

Если же статус островов показывает, что островов слишком мало или достаточно, то необходимо расширить текущий остров до подходящих размеров, если это возможно. Дело в том, что бывают ситуации, когда остров ограничен другими островами или границами мира, из-за чего ему некуда расширяться. В таком случае необходимо удалить текущий остров используя функцию DeleteIsland (рассмотренную ранее) и создать новый остров. Для расширения острова создана функция Expansion, которая работает следующим образом: для начала создается счетчик iter_ и ограничение счетчика max_iter, равное 20 итерациям. Далее запускается цикл while, работающий до тех пор, пока размер острова не достигнет нужного размера или пока количество итераций не достигнет 20. Последнее означает, что уже прошло 20 итераций, а остров все еще не достиг нужных размеров, что в свою очередь означает, что что-то не дает ему расшириться до нужных размеров, в таком случае функция возвращает True и программа удалит этот остров, а вместо него создаст остров в другом месте. Сам алгоритм расширения проверяет область вокруг текущей клетки с помощью функции CheckZeroAround, которая в свою очередь проверяет все 8 клеток вокруг текущей клетки и добавляет в список indexes те клетки, которые свободны (равны нулю), если же алгоритм пройдется по всем клеткам и список indexes останется пустым, то это означает, что вокруг текущей клетки нет пустых клеток, в таком случае переходим к следующей клетке. Если же список indexes остался не пустым, то проходимся по всем клеткам в списке и проверяем с помощью описанной ранее функции CheckAround нет ли вокруг клетки чужих островов (нам нельзя пересекать один остров с другим, между островами всегда должно быть расстояние мнинимум 1 клетка). Также проверяем, что вокруг текущей клетки есть клетка снизу, или сверху, или справа, или слева, чтобы избежать появления угловых клеток. Когда остров расширился до нужных размеров, то функция возвращает False и это означает, что остров успешно расширился

 def Expansion(self, number_of_land, sides_x, sides_y):
        """The expansion of too small islands"""
        max_iter = 20

        def ExpansionAction(x, y):
            if self.matrix_cond[x][y] == number_of_land:
                empty_islands = self.CheckZeroAround(x, y)
                if empty_islands:
                    for k_x, k_y in empty_islands:
                        if self.CheckAround(k_x, k_y, number_of_land):
                            if self.Check4CellsAround(number_of_land, k_x, k_y):
                                self.matrix_cond[k_x][k_y] = number_of_land
                                self.size_of_land[number_of_land] += 1
                                if self.size_of_land[number_of_land] >= self.need_size[0]:
                                    raise StopIteration

        for i in range(max_iter):
            try:
                start_x = [max(0, sides_x[0] - i), min(len(self.matrix_cond) - 1, sides_x[1] + i)]
                start_y = [max(0, sides_y[0] - i), min(len(self.matrix_cond[0]) - 1, sides_y[1] + i)]

                TraverseSquareAlgorithm.TraverseSquare(
                    start_x,
                    start_y,
                    ExpansionAction)

            except StopIteration:
                return False

        return True

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

class TraverseSquareAlgorithm:
    @staticmethod
    def TraverseSquare(side_x, side_y, action):
        """The square passage algorithm"""
        d_x = side_x[0]
        for d_y in range(side_y[0], side_y[1] + 1):
            action(d_x, d_y)

        d_y = side_y[0]
        for d_x in range(side_x[0], side_x[1] + 1):
            action(d_x, d_y)

        d_x = side_x[1]
        for d_y in range(side_y[0], side_y[1] + 1):
            action(d_x, d_y)

        d_y = side_y[1]
        for d_x in range(side_x[0], side_x[1] + 1):
            action(d_x, d_y)

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

    def CreateNewIsland(self):
        """Creating a new island in a suitable empty area"""
        start_x = random.randint(0, (len(self.matrix_cond) - 1))
        start_y = random.randint(0, (len(self.matrix_cond[0]) - 1))

        def Check(dx, dy):
            if self.CreateNewLandHelper(dx, dy):
                raise StopIteration

        try:
            TraverseSquareAlgorithm.TraverseSquareExpandingFromPoint(start_x, start_y, self.matrix_cond,Check)
        except StopIteration:
            return

    def CreateNewLandHelper(self, x, y):
        if 0 <= x < len(self.matrix_cond) and 0 <= y < len(self.matrix_cond[x]):
            if self.matrix_cond[x][y] == 0:
                if self.Counter_Islands(0, x, y) >= self.need_size[0]:
                    max_key = max(self.size_of_land)
                    number_of_land = max_key + 1
                    self.size_of_land[number_of_land] = self.FeelNewLand(number_of_land, x, y)
                    return True
        return False

Для поиска области, куда поместится остров, создана функция Counter_Island. Эта функция принимает на вход индекс клетки и координаты по x и y, с которых будет начинаться отсчет. Эта функция считает размер поля по индексу number_of_land, начиная с координат x и y, по алгоритму, идентичному алгоритму Flood Feel, описанному ранее. Создается стэк, в начале, с координатами, переданными на вход функции, затем создается счетчик. Создается нулевая вспомогательная матрица, где посчитанные клетки будут приравниваться единице, клетки, равные единице повторно считаться не будут. Начинается основной цикл, извлекается клетка из стэка, идет проверка на равенство индекса этой клетки, индексу нашего острова (поданного на вход), равенство нулю во вспомогательной матрице (это означает, что данную клетку еще не рассматривали), с помощью функции Check4CellsAround проверяем, что справа, или слева, или снизу, или сверху есть клетка такого же острова (это нужно для того, чтобы исключить счет угловой клетки), затем, если все 3 условия выполнены, мы помечаем эту клетку, как просмотренную, к счетчику прибавляем единицу и добавляем клетки вокруг этой клетки:

    def Counter_Islands(self, number_of_land, x, y):
        """Counts the number of cells of an island or a void"""
        stack_ = deque([(x, y)])
        counter = 0
        help_matrix = self.np.zeros((len(self.matrix_cond), len(self.matrix_cond[x])))
        while stack_:                    

            r, c = stack_.pop()
            if self.matrix_cond[r][c] == number_of_land and help_matrix[r][c] == 0 and self.Check4CellsAround(number_of_land, r,c):
                if self.CheckAround(r, c, number_of_land):
                    help_matrix[r][c] = 1
                    counter += 1

                    if r + 1 < len(self.matrix_cond):
                        stack_.append((r + 1, c))
                    if r - 1 >= 0:
                        stack_.append((r - 1, c))
                    if c + 1 < len(self.matrix_cond[x]):
                        stack_.append((r, c + 1))
                    if c - 1 >= 0:
                        stack_.append((r, c - 1))

        return counter

В нашем случае, эта функция используется для проверки не размера острова, а размера пустой области, начиная с клетки x, y, т.е. в качестве number_of_land будет передаваться значение 0.

Функция FeelNewLand, это алгоритм заполнения пустой области островом. Алгоритм так-же, как и некоторые описанные алгоритмы до этого, является по своей сути измененным алгоритмом Flood Feel. Создаем в этот раз не стэк, а очередь (FIFO: первым зашел - первым вышел). Создаем счетчик и множество уже рассмотренных клеток (множество: набор уникальных, неупорядоченных элементов, в нашем случае чуть ускорит работу алгоритма, нежели бы использовался вместо него обычный список). Алгоритм проходится по границам расширяющегося квадрата и при условии, что текущая клетка пустая и вокруг нее хотя бы одна из 4 клеток (снизу, сверху, справа, слева) является клеткой текущего острова (при условии, если счетчик не равен нулю, что означает, что у текущего острова еще нет клеток), а также, что вокруг нет клеток чужих островов и эта клетка еще не рассматривалась, то добавляется клетка текущего острова. Алгоритм проходится вначале по 2-м значениям x: минимальный и максимальный и по каждому y: от минимального, до максимального, затем наоборот: по 2-м значениям y и по каждому x, таким образом алгоритм проходится лишь по расширяющимся границам квадрата, не трогая при этом уже рассмотренные клетки внутри квадрата

    def FeelNewLand(self, number_of_land, x, y):
        """function to fill a new land area"""
        stack_ = deque([(x, y)])
        counter = 0
        was_check = set() #set to fast sears

        min_x, max_x = x, x
        min_y, max_y = y, y

        while stack_:   #FloodFeel?
            r, c = stack_.popleft()
            if self.matrix_cond[r][c] == 0 and (self.Check4CellsAround(number_of_land, r, c) or counter == 0):
                if self.CheckAround(r, c, number_of_land):
                    self.matrix_cond[r][c] = number_of_land
                    counter += 1

                    if counter >= self.need_size[0]:
                        return counter

                    min_x, max_x = min(min_x, r), max(max_x, r)
                    min_y, max_y = min(min_y, c), max(max_y, c)

                    for nx in [min_x, max_x]:
                        for ny in range(min_y - 1, max_y + 2):
                            if 0 <= nx < len(self.matrix_cond) and 0 <= ny < len(self.matrix_cond[0]) and (nx, ny) not inwas_check:
                                stack_.append((nx, ny))
                                was_check.add((nx, ny))

                    for ny in [min_y, max_y]:
                        for nx in range(min_x - 1, max_x + 2):
                            if 0 <= nx < len(self.matrix_cond) and 0 <= ny < len(self.matrix_cond[0]) and (nx, ny) not in was_check:
                                stack_.append((nx, ny))
                                was_check.add((nx, ny))

        return counter

Перейдем теперь к ветке, в которую попадает алгоритм, когда остров слишком большой. Рассмотрим ситуацию, когда островов слишком много или достаточно. В таком случае необходимо уменьшить размер текущего острова. Для этой задачи написана функция ReducingSize. Эта функция проходится по границам уменьшающегося квадрата и превращает в воздух клетки текущего острова до тех пор, пока его размер не достигнет подходящего значения

    def ReducingSize(self, number_of_land, sides_x, sides_y):
        """reduces the size of too large islands"""

        while self.size_of_land[number_of_land] > self.need_size[-1]:

            def CheckAndReduce(x, y):
                self.CheckCurCellIsCurIsland(x, y, number_of_land)
                if self.size_of_land[number_of_land] <= self.need_size[-1]:
                    raise StopIteration #interrupting the crawl immediately

            try:
                TraverseSquareAlgorithm.TraverseSquare(sides_x, sides_y, CheckAndReduce)
            except StopIteration:
                return

            sides_x[0] += 1
            sides_x[1] -= 1
            sides_y[0] += 1
            sides_y[1] -= 1

Если же остров слишком большой, а всего островов недостаточно, то необходимо разрезать текущий остров на 2. Для этой задачи создана функция Cut. Здесь в первую очередь вычисляется разница границ острова по x и по y, таким образом узнается, по какой оси остров длиннее и режется вдоль другой оси. Режется остров по ширине 2 клетки по центру, используя для этого координату, вычисляемую в самом начале, которая находится в переменной centr:

    def Cut(self, number_of_land, centr, sides_x, sides_y):
        """cutting the island into 2 parts in the center"""
        if (sides_x[1] - sides_x[0]) >= (sides_y[1] - sides_y[0]):
            for x in range((centr[0]), (centr[0] + 2)):
                for y in range(sides_y[0], sides_y[1] + 1):

                    if self.matrix_cond[x][y] == number_of_land:
                        self.matrix_cond[x][y] = 0
        else:
            for x in range(sides_x[0], sides_x[1] + 1):
                for y in range((centr[1]), (centr[1] + 2)):

                    if self.matrix_cond[x][y] == number_of_land:
                        self.matrix_cond[x][y] = 0

После разрезания острова остается несколько проблем, которые необходимо решить: Во первых, разделенные острова так и остаются считаться за один и тот же остров; Вторая проблема заключается в том, что разрез может пройти так, что останется не 2 острова, а больше; Последняя проблема, это что острова могут получиться все равно слишком большие или даже наоборот слишком маленькие. Итак, для начала необходимо решить первую проблему. Для того, чтобы перенумеровать разрезанные острова, для начала находится максимальный индекс островов из словаря self.size_of_land, прибавляем к этому значению единицу, чтобы получить новый уникальный индекс. Дополнительно создается словарь, в который параллельно словарю self.size_of_land будут добавляться новые острова и их размеры, а нужен он, чтобы затем отследить, какие новые острова были добавлены. Проходимся в цикле по границам разрезанного острова. Острова, у которых все еще старый индекс, присваивается новый. Для этой задачи создан алгоритм (функция FeelForCut), повторяющий алгоритм Flood Feel, но по сравнению с ранее реализованным этим алгоритмом, здесь в качестве условия присваивания нового индекса, проверка, что текущая клетка имеет индекс острова до разрезания. После каждого прохождения по этому алгоритму, к предыдущему индексу добавляется единица и мы снова получаем уникальный индекс для следующего найденного в цикле острова. Таким образом, все разрезанные острова получат новый уникальный индекс. Теперь необходимо удалить лишние острова, чтобы осталось только 2 острова. Для этого используется новый словарь, преобразуется в список списков, где вложенные списки содержат ключ и значения словаря, затем они сортируются по размеру острова. Затем идет проверка, больше ли островов чем 2? Если больше, то удаляем самые маленькие острова, оставив 2 самых больших. Теперь осталось привести к нужному размеру 2 оставшихся острова. Для этого находим новые границы для каждого острова, смотрим их размер и если размер слишком большой, то используем функцию для уменьшения острова ReducingSize, иначе, если остров слишком маленький, то пытаемся его расширить с помощью функции Expansion и если не удается, то удаляем через DeleteIsland и создаем новый остров используя CreateNewIsland:

  elif status_amount_of_lands == "less":
                        self.Cut(key, centr, sides_x, sides_y)

                        max_key = max(self.size_of_land)
                        number_of_matrix = max_key + 1
                        new_size = dict()

                        for x in range(sides_x[0], sides_x[1] + 1):
                            for y in range(sides_y[0], sides_y[1] + 1):
                                if self.matrix_cond[x][y] == key:
                                    self.size_of_land[number_of_matrix] = self.FeelForCut(x, y, key,number_of_matrix)
                                    new_size[number_of_matrix] = size_of_land[number_of_matrix]
                                    number_of_matrix += 1
                        sorted_new_isl = sorted(new_size.items(), key=lambda item: item[1], reverse=True)
                        ###Removing unnecessary islands
                        if len(new_size) > 2:
                            less_islands = sorted_new_isl[2:]
                            for i, _ in less_islands:
                                self.DeleteIsland(i, sides_x, sides_y)
                                del self.size_of_land[i]
                        ###

                        self.amounts_lands += 1
                        status_amount_of_lands = self.SetStatusAmount()
                        del self.size_of_land[key]

                        ###Bringing the islands to a suitable size
                        bigger_island = sorted_new_isl[:2]
                        for i, _ in bigger_island:
                            centr, sides_x, sides_y = SIGCAB.SearcIslGeomCentAndBords(i, self.matrix_cond)
                            if self.size_of_land[i] > self.need_size[1]:
                                self.ReducingSize(i, sides_x, sides_y)
                            elif self.size_of_land[i] < self.need_size[0]:
                                if self.Expansion(i, sides_x,sides_y):
                                    self.DeleteIsland(key, sides_x, sides_y)
                                    del self.size_of_land[key]
                                    self.CreateNewIsland()

                        signal_was_change = True

Может случиться такая ситуация, что все острова приведены к нужным размерам, но количество островов все еще избыточно или недостаточно. Для такого случая реализованы 2 последние ветки в основном цикле. Первая ветка отвечает за ситуацию, когда островов слишком много. Запускаем цикл, который будет выполняться до тех пор, пока статус количества островов не примет значение «equel». Проходимся по всем островам и находим самый маленький из них. Удаляем выбранный остров, используя функцию DeleteIsland, обновляем информацию. Вторая ветка отвечает за ситуацию, когда островов недостаточно. Создаем такой же цикл, что и в предыдущей ветке, но только теперь не удаляем острова, а создаем новые острова, использую функцию CreateNewIsland, обновляем информацию и так до тех пор, пока островов не станет достаточно

            if signal_was_change == False:
                if status_amount_of_lands == "more":
                    key, value = next(iter(self.size_of_land.items()))
                    min = [key, value]
                    while status_amount_of_lands != "equel":
                        for key, value in self.size_of_land.items():
                            if value < min[1]:
                                min = [key, value]

                        centr, sides_x, sides_y = SIGCAB.SearcIslGeomCentAndBords(min[0], self.matrix_cond)
                        self.DeleteIsland(min[0], sides_x, sides_y)
                        del self.size_of_land[min[0]]
                        self.amounts_lands = self.amounts_lands - 1
                        status_amount_of_lands = self.SetStatusAmount()
                        if status_amount_of_lands == "equel":
                            break

                elif status_amount_of_lands == "less":
                    while status_amount_of_lands != "equel":
                        self.CreateNewIsland()
                        self.amounts_lands += 1
                        status_amount_of_lands = self.SetStatusAmount()
                        if status_amount_of_lands == "equel":
                            break

В самом конце проходимся по всем клеткам self.matrix_cond и там, где есть остров, в self.matrix соответствующей клетке присваиваем тип «land», иначе тип «air». Итого весь основной цикл упорядочивания:

        while (not (self.amounts_lands in self.need_lands)) or (any(v not in self.need_size for v in self.size_of_land.values())):
            signal_was_change = False
            size_of_land_helper = self.size_of_land.copy()
            for key, value in size_of_land_helper.items():
                centr, sides_x, sides_y = SIGCAB.SearcIslGeomCentAndBords(key, self.matrix_cond)
                if value < self.need_size[0]:
                    if status_amount_of_lands == "more":
                        self.DeleteIsland(key, sides_x, sides_y)
                        del self.size_of_land[key]
                        self.amounts_lands = self.amounts_lands - 1
                        status_amount_of_lands = self.SetStatusAmount()
                        signal_was_change = True

                    elif status_amount_of_lands == "less" or status_amount_of_lands == "equel":
                        if self.Expansion(key, sides_x, sides_y): #If True -> Something is preventing it from 
                            self.DeleteIsland(key, sides_x, sides_y)
                            del self.size_of_land[key]
                            self.CreateNewIsland()
                        signal_was_change = True

                elif value > self.need_size[-1]:

                    if status_amount_of_lands == "more" or status_amount_of_lands == "equel":
                        self.ReducingSize(key, sides_x, sides_y)
                        signal_was_change = True

                    elif status_amount_of_lands == "less":
                        self.Cut(key, centr, sides_x, sides_y)

                        max_key = max(self.size_of_land)
                        number_of_matrix = max_key + 1
                        new_size = dict()

                        for x in range(sides_x[0], sides_x[1] + 1):
                            for y in range(sides_y[0], sides_y[1] + 1):
                                if self.matrix_cond[x][y] == key:
                                    self.size_of_land[number_of_matrix] = self.FeelForCut(x, y,key,number_of_matrix)
                                    new_size[number_of_matrix] = size_of_land[number_of_matrix]
                                    number_of_matrix += 1
                        sorted_new_isl = sorted(new_size.items(), key=lambda item: item[1], reverse=True)
                        ###Removing unnecessary islands
                        if len(new_size) > 2:
                            less_islands = sorted_new_isl[2:]
                            for i, _ in less_islands:
                                self.DeleteIsland(i, sides_x, sides_y)
                                del self.size_of_land[i]
                        ###

                        self.amounts_lands += 1
                        status_amount_of_lands = self.SetStatusAmount()
                        del self.size_of_land[key]

                        ###Bringing the islands to a suitable size
                        bigger_island = sorted_new_isl[:2]
                        for i, _ in bigger_island:
                            centr, sides_x, sides_y = SIGCAB.SearcIslGeomCentAndBords(i, self.matrix_cond)
                            if self.size_of_land[i] > self.need_size[1]:
                                self.ReducingSize(i, sides_x, sides_y)
                            elif self.size_of_land[i] < self.need_size[0]:
                                if self.Expansion(i, sides_x,sides_y):
                                    self.DeleteIsland(key, sides_x, sides_y)
                                    del self.size_of_land[key]
                                    self.CreateNewIsland()

                        signal_was_change = True

            if signal_was_change == False:
                if status_amount_of_lands == "more":
                    key, value = next(iter(self.size_of_land.items()))
                    min = [key, value]
                    while status_amount_of_lands != "equel":
                        for key, value in self.size_of_land.items():
                            if value < min[1]:
                                min = [key, value]

                        centr, sides_x, sides_y = SIGCAB.SearcIslGeomCentAndBords(min[0], self.matrix_cond)
                        self.DeleteIsland(min[0], sides_x, sides_y)
                        del self.size_of_land[min[0]]
                        self.amounts_lands = self.amounts_lands - 1
                        status_amount_of_lands = self.SetStatusAmount()
                        if status_amount_of_lands == "equel":
                            break

                elif status_amount_of_lands == "less":
                    while status_amount_of_lands != "equel":
                        self.CreateNewIsland()
                        self.amounts_lands += 1
                        status_amount_of_lands = self.SetStatusAmount()
                        if status_amount_of_lands == "equel":
                            break

        for x in range(len(self.matrix_cond)):
            for y in range(len(self.matrix_cond[x])):
                self.matrix[x][0][y] = BiomesType.air_RL if (self.matrix_cond[x][y] == 0) else BiomesType.land_RL

Теперь, запустив программу, можно получить примерно следующий результат:

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

Туннелирование

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

Для этой задачи был создан модуль под названием Tunneling.

Первым шагом создается переменная num_key, которая хранит значение количества островов + 1, таким образом получаем особый ключ для путей. Создается пустой словарь island_centr_sides, который для каждого острова будет хранить его следующие данные: центр, границы по оси x и границы по оси y. Создается список roads, который хранит острова, между которыми проложен путь по следующему правилу: каждый элемент списка roads вложенный список, хранящий первым элементом наименьший ключ, а вторым наибольший, сделано это для того, чтобы исключить прокладку туннеля от острова a к острову b, а затем наоборот туннеля от острова b к острову a.

Проходимся по элементам словаря size_of_land и заполняем словарь island_centr_sides с помощью ранее описанного модуля SearcIslGeomCentAndBords.

Следующим шагом начинается основной цикл, но перед этим создается список островов, от которых уже строили пути (was_key). Берем текущий остров, с помощью алгоритма расширябщегося квадрата, находим ближайший остров и строим путь от текущего острова к ближайшему. Как только первый путь был построен, запускаем счетчик и пробуем найти еще ближайшие острова, к которым удобно построить путь, но здесь уже не важно, найдутся острова или нет, главное, чтобы был построен хотя бы 1 путь от текущего острова.

Реализован этот алгоритм следующим образом: проходимся по всей матрице matrix_cond и если текущая клетка не равна нулю (пустая клетка), не является клеткой уже рассмотренного острова и не является путем, то мы попали на еще не рассмотренный остров. Здесь мы ключ острова сразу же добавляем в was_key, создаем список границ side_x и side_y с уже расширенными границами на 1 клетку если не выходим за границы мира. Начинаем цикл, который идет до тех пор, пока counter меньше 3, при этом сама переменная counter не будет изменяться до тех пор, пока не был построен первый путь, затем она увеличивается на 1 каждый раз, когда расширяются границы. Внутри цикла проходимся алгоритмом расширяющегося квадрата.

На данном этапе действием в алгоритме расширяющегося квадрата является проверка, нашли ли мы клетку другого острова. Для этой задачи создана функция CanBuildTunnel. Работает функция следующим образом: если клетка не является пустым пространством, текущим островом и путем, то это другой остров, в таком случае проверяем, что между текущими островами еще нет пути, используя список roads. Если пути нет, то запускаем функцию Tunnel, которая строит путь между островами. При прокладке туннеля возвращаем True, чтобы запустить счетчик. Если не построили, то возвращаем текущее значение have_road:

    def CanBuildTunnel(self, d_x, d_y, cur_key, have_road):
        """We are checking whether it is possible to build a tunnel. If possible, we are building"""
        if self.matrix_cond[d_x][d_y] != 0 and self.matrix_cond[d_x][d_y] != cur_key and self.matrix_cond[d_x][d_y] != self.num_key:
            sec_key = int(self.matrix_cond[d_x][d_y])
            if [min(cur_key, sec_key), max(cur_key, sec_key)] not in self.roads:
                self.Tunnel(cur_key, sec_key)
                self.roads.append([min(cur_key, sec_key), max(cur_key, sec_key)])
                return True
        return have_road

Функция Tunnel работает следующим образом: вначале проверяем, можно ли проложить путь на одной линии по оси x или y, если нет, то сравниваем центры островов. Сначала по высоте, затем по ширине. Если центры не дальше друг от друга трех клеток, то путь строится от центра. Иначе в зависимости от того, в какую сторону центр какого острова больше 3-х, у одного острова по оси y берется нижняя граница, у другого верхняя и по оси x у одного правая граница, у другого левая. При выборе клетки может произойти ситуация, что выбранная клетка не принадлежит острову, для этого перед прокладкой пути, клетки заносятся в функцию SearchNearestBoundaryCell, которая возвращает ближайшие найденные клетки островов.

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

    def Tunnel(self, key1, key2):
        """laying a path between two islands"""
        sides_key1 = self.island_centr_sides[key1]
        sides_key2 = self.island_centr_sides[key2]

        start_x, end_x = self.DetermineAxisStartEnd(sides_key1[1], sides_key2[1], sides_key1[0][0], sides_key2[0][0]) #X
        start_y, end_y = self.DetermineAxisStartEnd(sides_key1[2], sides_key2[2], sides_key1[0][1], sides_key2[0][1]) #Y

        x, y = self.SearchNearestBoundaryCell(key1, start_x, start_y, sides_key1[0])
        end_x, end_y = self.SearchNearestBoundaryCell(key2, end_x, end_y, sides_key2[0])

        def_x = 1 if end_x > x else -1
        def_y = 1 if end_y > y else - 1

        while True:
            print(f"Tunnel: x = {x}, y = {y}, end_x = {end_x}, end_y = {end_y}")
            if (x, y) == (end_x, end_y):
                print(f"The last point has been reached: x = {x}, y = {y}")
                break

            if x != end_x:
                if 0 <= x + def_x < len(self.matrix_cond):
                    x += def_x
                    if self.matrix_cond[x][y] == 0:
                        self.matrix_cond[x][y] = self.num_key

                else:
                    print(f"going abroad by x, where x = {x + def_x}")

            if y != end_y:
                if 0 <= y + def_y < len(self.matrix_cond[0]):
                    y += def_y
                    if self.matrix_cond[x][y] == 0:
                        self.matrix_cond[x][y] = self.num_key
                else:
                    print(f"going abroad by y, where y = {y + def_y}")

    def RangeInspect(self, a_min, a_max, b_min, b_max):
        return max(a_min, b_min) <= min(a_max, b_max)

    def DetermineAxisStartEnd(self, s1_range, s2_range, s1_center, s2_center):
        if self.RangeInspect(*s1_range, * s2_range):
            coord = max(s1_range[0], s2_range[0])
            start, end = coord, coord
        elif s1_center >= s2_center + 3:
            start = s1_range[0]
            end = s2_range[1]
        elif s1_center + 3 <= s2_center:
            start = s1_range[1]
            end = s2_range[0]
        else:
            start = s1_center
            end = s2_center
        return  start, end

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

    def SearchNearestBoundaryCell(self, key, x, y, center):
        """If there is no island in the corner cell, go up (down) and right (left) and diagonal
        at the same time in search of the first available island cell."""
        if self.matrix_cond[x][y] == key:
            return x, y
        else:
            result = []
            def Check(dx, dy):
                if self.matrix_cond[dx][dy] == key:
                    result.append(dx)
                    result.append(dy)
                    raise StopIteration
            try:
                TraverseSquareAlgorithm.TraverseSquareExpandingFromPoint(x, y, self.matrix_cond, Check)
            except StopIteration:
                return result[0], result[1]

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

Структура программы

Подытоживая проделанную работу, можно уделить внимание структуре классов. Класс Rasterization2D рисует линии и треугольники разных видов, в программе используются каркасные треугольники, метод по их отрисовке использует класс Rasterization3D, который эти треугольники проецирует на трёхмерное пространство.

Класс main запускают всю программу, а именно модуль RougeLikeKA, который связывает все модули по созданию мира и генерирует с их помощью мир.

Модули settings и BiomesType хранят в себе настройки мира и типы поверхности (воздух, остров, путь). SquareAlgorithm и FloodFeelCounter: вспомогательные модули, которые реализуют алгоритм прохождения квадратом и заливки однородной области, которые часто используются в некоторых модулях. WriteExcel: модуль для сохранения матриц островов в Excel. OrderingIsland и Tunneling: модули упорядочивания островов и прокладки туннеля между ними.

CellsAround реализует проверку клеток вокруг (4 или 3); DayAndNight реализует правило "День и ночь" клеточных автоматов; PostProcessingAfterOrdering чистит лишние уровни (если таковые есть) после упорядочивания островов; SearchingIslandGeometricCenterAndBorders метод для поиска границ и центра острова; StartAndEnd случайным образом выбирает начальный и конечный остров, алгоритм работы не сложный, поэтому не стал его описывать в работе.

Процедурная генерация воксельных рогаликовых уровней