Простая процедурная генерация мира, или Шумы Перлина на Python

u7s6qhmzvtliomcs7_jnrbxoxyy.png


Недавно я выпустил статью, в которой рассказал о библиотеке Ursina Engine и показал, как создать свою трехмерную игру на Python. Между разделами вскользь упомянул про шум Перлина. Это один из базовых алгоритмов процедурной генерации, который можно использовать для создания красивых игровых миров. Хочу рассказать о нем подробнее и показать, как работать с модулем perlin-noise.

Если вам интересно, как просто генерировать реалистичные трехмерные ландшафты на Python, добро пожаловать под кат!

Пояснения внутри кодовых вставок — неотъемлемая часть статьи. Обращайтесь к ним, если что-то непонятно. На более сложные вопросы по работе с модулем могу ответить в комментариях.


Неудачная попытка сгенерировать ландшафт


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

Идея алгоритма была простой: программа случайным образом выбирает координаты и присваивает им значение y, высоту. После рандомно генерирует новые точки со значением y или y-1 вокруг этих возвышенностей. Так должен был получиться плавный горный ландшафт. Но на практике было пару нюансов:

  1. Иногда программа генерировала не горы, а кривые пирамиды и бесконечные китайские стены.
  2. Алгоритм не подходил для генерации больших миров. Нельзя было эффективно записывать и считывать генерацию из памяти компьютера.


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

gfckismr5xgcdhdc2i_6zgfvotc.png

Что такое шум Перлина


Шум Перлина — это алгоритм процедурной генерации псевдослучайным методом. Механика такая: вы подаете на вход число seed, на базе которого генерируется структура ландшафта.


Теперь немного теории. В отличие от обычного белого шума, у Перлина есть плавные «переходы» между случайными локальными максимумами и минимумами. Посмотрите сами: В большем масштабе шум Перлина также может напоминать белый шум.

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

psxjrcmxkdldei4s6df_uh7u2s4.gif


Процесс получения одномерного простого шума Перлина. Синие прямые — наклонные; красная кривая — результат линейной интерполяции, кривая Безье; черная точечная — сглаживания «изломов» после линейной интерполяции.

Сама по себе функция Перлина генерирует довольно простые шумы (кривые) — это видно из графика выше. Чтобы получить более «неоднородные» кривые, которые в трехмерном пространстве больше напоминают горы, обычно суммируют несколько шумов. Главное условие, чтобы у них отличались разрешения и, соответственно, периоды — например, x и 2x. Обычно значения кратны двум и кривые называют октавами: чем их больше, тем неоднородней и реалистичней итоговая поверхность.

zfhz6ltev_a6edqtioah2mf76-q.png


Одномерное представление шума Перлина на базе 4 октав.

Наиболее подробно матаппарат Кена Перлина описан в статье Лекси Монро. Если хотите полностью понять реализацию алгоритма, рекомендую к прочтению.


Генерация шума Перлина и знакомство с модулем perlin-noise


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

import numpy as np
import matplotlib.pyplot as plot

def perlin(x, y, seed=0):
   # создание матрицы для шума и генерация случайного значения seed
   np.random.seed(seed)
   ptable = np.arange(256, dtype=int)

   # разброс пиков по случайным ячейкам матрицы
   np.random.shuffle(ptable)

   # получение свертки матрицы для линейной интерполяции
   ptable = np.stack([ptable, ptable]).flatten()

   # задание координат сетки
   xi, yi = x.astype(int), y.astype(int)

   # вычисление координат расстояний
   xg, yg = x - xi, y - yi

   # применение функции затухания к координатам расстояний
   xf, yf = fade(xg), fade(yg)

   # вычисление градиентов в заданных интервалах
   n00 = gradient(ptable[ptable[xi] + yi], xg, yg)
   n01 = gradient(ptable[ptable[xi] + yi + 1], xg, yg - 1)
   n11 = gradient(ptable[ptable[xi + 1] + yi + 1], xg - 1, yg - 1)
   n10 = gradient(ptable[ptable[xi + 1] + yi], xg - 1, yg)

   # линейная интерполяция градиентов n00, n01, n11, n10
   x1 = lerp(n00, n10, xf)
   x2 = lerp(n01, n11, xf)
   return lerp(x1, x2, yf)

def lerp(a, b, x):
   "функция линейной интерполяции"
   return a + x * (b - a)

# функция сглаживания
def fade(f):
   return 6 * f ** 5 - 15 * f ** 4 + 10 * f ** 3

# вычисление векторов градиента 
def gradient(c, x, y):
   vectors = np.array([[0, 1], [0, -1], [1, 0], [-1, 0]])
   gradient_co = vectors[c % 4]
   return gradient_co[:, :, 0] * x + gradient_co[:, :, 1] * y

# генерация равномерно распределенных координат для функции perlin
lin_array = np.linspace(1, 10, 500, endpoint=False)
x, y = np.meshgrid(lin_array, lin_array)

# вывод графика pyplot
plot.imshow(perlin(x, y, seed=2), origin='upper')
plot.show()


Реализация шума Перлина по версии OpenGenus.

Чтобы не разбираться с составляющими шума Перлина и их сглаживаем, вычислением градиентов и линейными интерполяциями, проще использовать модуль perlin-noise. Он консолидирует сложную математику: разработчику достаточно просто импортировать модуль и «пошаманить» с параметрами ландшафта:

from numpy import floor
from perlin_noise import PerlinNoise
import matplotlib.pyplot as plt

# генерация основного шума и параметризация
noise = PerlinNoise(octaves=2, seed=4522)
amp = 6
period = 24
terrain_width = 300

#генерация матрицы для представления ландшафта 
landscale = [[0 for i in range(terrain_width)] for i in range(terrain_width)]

for position in range(terrain_width**2):
   # вычисление высоты y в координатах (x, z)
   x = floor(position / terrain_width)
   z = floor(position % terrain_width)
   y = floor(noise([x/period, z/period])*amp)
   landscale[int(x)][int(z)] = int(y)

plt.imshow(landscale)
plt.show()


Если запустить этот код и вывести сгенерированную матрицу с шумом Перлина в Matplotlib, вы увидите примерно такую структуру:

wxmbnc0z4qlqqp0glzfo2ntdn3s.png


Готово — тепловая карта ландшафта сгенерирована, ее можно перенести в игру. Возвышенности и горы — это ярко желтые области, низшие уровни обозначены более холодными цветами.

cxisxom4tdu3jkpgkrcv1-bdpyc.png


Параметры perlin-noise


Теперь давайте разберемся подробнее с параметрами, которые доступны в perlin-noise. И посмотрим, как меняется ландшафт при разных значениях.

octaves — это количество кривых Перлина, которые отвечают за неоднородность шума. Чем больше этот параметр, тем «необычней» ландшафт по своей форме.

amp — это коэффициент, который отвечает за итоговую высоту координаты y.period — это периодичность пиков кривой Перлина. При ее увеличении поверхность становится более гладкой.seed — число, которое однозначно описывает вашу генерацию. В играх это число, которое вводит пользователь. Остальные параметры — octaves, amp и period — консолидированы и недоступны «извне».

perlin-noise — непопулярный модуль, у которого нет даже документации с практическими примерами. Поэтому работа с этим модулем может превратиться в танец с бубном, если хотите построить свой мир из The Legend of Zelda.

Главное, чтобы значения параметров не упирались в потолок. Например, если значение period небольшое, а размах amp слишком велик, получится простой белый шум. Вы можете протестировать это сами, код проекта доступен на GitHub. Делайте форк и делитесь своими мирами в комментариях!

Возможно, эти тексты тоже вас заинтересуют:

→ Ремонт игрового ноутбука с прогаром в плате без схемы: возвращаем к жизни «похороненный» сервисными центрами CLEVO P970
→ А потом снизу постучали: продажи жестких дисков продолжают обваливаться. Падают и продажи ПК с ноутбуками
→ Как подключить платежную систему с Payments к Telegram

© Habrahabr.ru