Разработка игр

Procedural Generation

Цели урока

Генерировать terrain через фракционный Perlin Noise с несколькими октавами
Реализовать базовый Wave Function Collapse с propagation
Построить L-систему для процедурных деревьев и растений
Сгенерировать связное подземелье через BSP алгоритм

No Man's Sky содержит 18 квинтиллионов планет. Ни один человек их не рисовал - все созданы алгоритмами. Procedural generation - это не случайность: это система правил, которая создаёт бесконечное разнообразие из небольшого набора параметров.

**Minecraft:** Perlin Noise для terrain, структуры через шаблоны + WFC
**No Man's Sky:** многоуровневый noise для планет, флора, фауна
**Spelunky / Hades:** BSP + template rooms для roguelike подземелий
**SpeedTree:** L-системы для деревьев в AAA играх (Unreal Engine, Unity)

Perlin Noise и Simplex

Карта высот в Minecraft выглядит естественно: холмы плавно переходят в долины, нет резких скачков. Если взять случайные числа для каждой ячейки - получится «соль и перец», не природа. **Perlin Noise** решает это: функция, которая возвращает гладкое псевдослучайное значение [-1, 1] для любой точки (x, y, z), где соседние точки дают близкие значения.

**Domain warping:** подавать в noise(x, y) не прямые координаты, а `noise(x + noise(x, y) * warp, y + noise(x+5, y+5) * warp)`. Это создаёт «скрученный» шум - идеально для пещер, облаков, огня.

Зачем суммировать несколько октав Perlin Noise вместо одного?

Wave Function Collapse

Дизайнер нарисовал небольшой sample-тайлсет: трава, дорожка, вода - с правилами, какие тайлы могут стоять рядом. **Wave Function Collapse (WFC)** генерирует произвольно большую карту, соблюдая все эти правила. Название - из квантовой механики: каждая клетка начинает в суперпозиции всех возможных тайлов и коллапсирует к одному.

**Contradiction:** иногда WFC заходит в тупик - клетка теряет все возможные тайлы из-за конфликтующих ограничений. Решение: backtracking (откат к последнему коллапсу) или restart с другим seed. В большинстве практических реализаций достаточно restart.

WFC выбирает для коллапса клетку с минимальной энтропией (меньше всего вариантов). Зачем?

L-системы для растений

Дерево в игре выглядит как дерево, потому что ветви ветвятся рекурсивно - так же, как в природе. **L-система (Lindenmayer system)** формализует это: начальная строка (аксиома) переписывается по правилам несколько раз, результат интерпретируется как команды для «черепашки» (turtle graphics).

**Stochastic L-системы:** правило перезаписи выбирается случайно из нескольких вариантов с заданными вероятностями. Это даёт вариативность: каждое дерево уникально, но узнаваемо как дерево одного вида.

L-система после 4 итераций дала очень длинную строку и слишком детализированное дерево. Что изменить?

Dungeon Generation алгоритмы

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

Алгоритм	Результат	Применение
BSP	Прямоугольные комнаты с коридорами, все связаны	Roguelikes (Dungeon Crawl)
Cellular Automata	Органические пещеры, нет гарантии связности	Minecraft пещеры, биомы
Drunkard's Walk	Одна связная извилистая зона	Простые roguelikes
Delaunay + MST	Комнаты с гарантией min spanning tree + циклы	Advanced roguelikes

**Cellular Automata для пещер:** заполнить карту случайным образом (45% floor), затем N итераций: клетка становится стеной, если у неё >= 5 соседей-стен (правило B5678/S45678). Результат - органические пещеры. Добавить flood fill для выбора только связной части.

Cellular Automata генерация пещер не гарантирует связность. Как это исправить?