Всем привет! На написание этой статьи меня вдохновил автор YouTube канала PeaAshMeter. В своем видео автор показывает простейший генератор 2D мира, который основан на простейшем правиле клеточного автомата. Что такое клеточный автомат? Какие клеточные автоматы бывают? На эти и многие другие вопросы я попробую ответить.

Проект я решил написать на Python, но поскольку не являюсь экспертом в этой области, то любые замечания, предложения по улучшению кода или проекта — приветствуются!

Последовательность генерации 2D мира.
Последовательность генерации 2D мира.

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. Рекомендованные материалы

Комментарии (2)


  1. domix32
    00.00.0000 00:00

    Прикольно. Ещё бы логику для гор придумать.

    Чтобы не писать копипаст, можно сделать цикл по сдвигам от текущей ячейки

    offsets = [
      (-1,-1),(0,-1),(1,-1),
      (-1, 0),(0, 0),(1, 0),
      (-1, 1),(0, 1),(1, 1),
    ]
    # y current and x current
    for yc in range(height):
      for xc in range(width):
        # x offset and y offset
        for (xo, yo) in offsets:
          x = xc + xo
          y = yc + yo
          # проверяем границы
          if x < 0 or x >= width: continue
          if y < 0 or y >= height: continue
          
          # для текущей ячейки своя логика
          if x == xc and y == yc:
            if self.matrix[x][y] == BiomesType.SEA:
                if counter_land in (3, 6, 7, 8):
                  self.matrix[x][y] = BiomesType.LAND
                  self.paint_pixel_element(self.matrix[x][y], x, y)
                  # в вашем коде земля перетирала воду, 
                  # поэтому проще сразу на неё проверить
                  continue;
            if self.matrix[x][y] == BiomesType.LAND:
              if counter_sea in (3, 6, 7, 8):
                self.matrix[x][y] = BiomesType.SEA
                self.paint_pixel_element(self.matrix[x][y], x, y)
                
          # логика для окружающих ячеек
          else:
            if self.matrix[x][y] == BiomesType.SEA:
              counter_sea += 1
            else:
              counter_land += 1


    1. kooo9058 Автор
      00.00.0000 00:00

      Да, вы правы. Спасибо за комментарий!