Процедурная генерация: три алгоритма для миров и данжей

Вы когда-нибудь задумывались, как Minecraft, No Man's Sky или рогалики создают бесконечные миры без ручной прорисовки каждого блока? Ответ — процедурная генерация. Сегодня разберём три семейства алгоритмов, на которых держится почти вся генерация контента: шумовые функции, dungeon-алгоритмы и Wave Function Collapse.

Шумовые функции: основа рельефа

Шум Перлина и симплекс-шум дают плавную случайность — идеально для ландшафтов. Достаточно наложить шум на карту высот, добавить карту влажности и пороги — и вы получите биомы.

import noise
import numpy as np

# Генерация карты высот с помощью шума Перлина
shape = (100, 100)
scale = 10.0
heightmap = np.zeros(shape)
for y in range(shape[0]):
    for x in range(shape[1]):
        heightmap[y][x] = noise.pnoise2(x / scale, y / scale, octaves=6)

# Преобразуем в биомы по высоте и влажности (упрощённо)
biome_map = np.where(heightmap > 0.2, 'лес', 'пустыня')
print(biome_map[:5, :5])

Этот код создаёт простую карту биомов. В реальных проектах добавляют слои температуры, влажности и шум более высокого разрешения.

Алгоритмы для подземелий: BSP и клеточные автоматы

Binary Space Partitioning (BSP) делит прямоугольную область на непересекающиеся комнаты. Клеточные автоматы превращают случайный шум в пещеры. Случайные блуждания создают извилистые коридоры.

import random

# Простой BSP: рекурсивно делим область на комнаты
def bsp_split(x, y, w, h, depth):
    if depth <= 0 or w < 10 or h < 10:
        return [(x, y, w, h)]  # комната
    rooms = []
    if w > h:
        split_x = random.randint(x + 5, x + w - 5)
        rooms += bsp_split(x, y, split_x - x, h, depth-1)
        rooms += bsp_split(split_x, y, x + w - split_x, h, depth-1)
    else:
        split_y = random.randint(y + 5, y + h - 5)
        rooms += bsp_split(x, y, w, split_y - y, depth-1)
        rooms += bsp_split(x, split_y, w, y + h - split_y, depth-1)
    return rooms

# Пример: генерируем 4 уровня вложенности
rooms = bsp_split(0, 0, 100, 100, 4)
print(f'Сгенерировано {len(rooms)} комнат')
for r in rooms:
    print(f'Комната: x={r[0]}, y={r[1]}, w={r[2]}, h={r[3]}')

Этот код создаёт список непересекающихся прямоугольных комнат. Для соединения их коридорами можно использовать A* или случайные блуждания.

Wave Function Collapse: магия ограничений

Wave Function Collapse (WFC) — новейший метод. Вы даёте ему маленький пример (например, 3x3 тайла), и он генерирует большой мир, где каждый локальный паттерн соответствует примеру. Это как судоку: каждая ячейка получает список возможных вариантов, которые сужаются по правилам соседства.

from wfc import WaveFunctionCollapse  # пример библиотеки

# Задаём пример 3x3 (0 - трава, 1 - стена)
example = [
    [0, 0, 0],
    [0, 1, 0],
    [0, 0, 0]
]

# Создаём генератор и запускаем
wfc = WaveFunctionCollapse(example, width=10, height=10)
result = wfc.run()

for row in result:
    print(' '.join(str(c) for c in row))

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

Детерминизм: одна цифра — один мир

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

import random

# Фиксируем зерно
seed = 42
random.seed(seed)
# Теперь все случайные вызовы воспроизводимы
print(random.randint(0, 100))  # всегда 81 при seed=42

Практический вывод

Попробуйте прямо сейчас: возьмите любой из трёх алгоритмов и напишите генератор на Python. Начните с шума Перлина для карты высот, добавьте BSP для комнат или попробуйте WFC с простым паттерном. Детерминизм — ваш друг: всегда передавайте seed. Через час у вас будет работающий прототип процедурного мира.

Если хотите углубиться, изучите поддержку в Unity, Godot или веб-стеке. А что вы построили с помощью процедурной генерации? Делитесь идеями в комментариях!