Модуль 11 · AI/ML в играх

Процедурная генерация: шум, L-системы, данжены

Процедурная генерация — это ограниченная случайность, а не хаос. И рабочие лошадки тут классические, не ML: шум Перлина/Simplex для рельефа, L-системы для растений, BSP для данженов, грамматики для уровней. GAN'ы для контента живут на фронтире и обычно проигрывают — потому что не гарантируют играбельность.

~16 мин🎲 PCG + когда ML не нужен🏠 лаба

Суть за 30 секунд

PCG = ограниченная случайность, не хаос, и её рабочие лошадки классические. Шум (Перлин 1985 / Simplex 2001, патент истёк 2022 → OpenSimplex): непрерывная гладкая фрактальная псевдослучайность — складываешь октавы (fBm) для рельефа, O(1) на сэмпл. L-системы: строковые грамматики-переписывания → фрактальные растения/ветвление. BSP: рекурсивно делишь пространство → гарантированно связанные комнаты данжена. Грамматики: задаёшь грамматику валидного уровня, сэмплируешь + проверяешь ограничения. Ключевой инсайт (Spelunky): ограничения вшиты в саму генерацию (выход всегда достижим, сложность растёт с глубиной) — «генерируй-с-ограничениями» бьёт «сгенерируй-потом-проверь». ML-PCG (GAN'ы для уровней) существует на research-фронтире, но обычно проигрывает: выход часто невалиден (кривые тайлы, непроходимо), трудно наложить ограничения, медленнее. Для большинства контента ручные генеративные правила + шум + ограничения бьют обученный генератор — это контентная версия «классика > ML».

Механизм: гладкая случайность и вшитые ограничения

Шум Перлина/Simplex

Обычный random() даёт «снег» — соседние значения независимы. Для рельефа нужна гладкая случайность: близкие точки — близкие высоты. Шум Перлина: в узлах решётки — случайные градиент-векторы; для точки берём скалярные произведения градиентов на векторы-расстояния до узлов и гладко интерполируем → значение в $[- 1, 1]$ . Одна октава — плавные холмы; детали дают октавы (fBm) — сумма копий шума растущей частоты и падающей амплитуды:

fBm (x) = \sum_{i = 0}^{k - 1} p^{i} \cdot noise (l^{i} x)

( $l$ — lacunarity, множитель частоты; $p$ — persistence, множитель амплитуды, обычно $l = 2$ , $p = 0.5$ ). Крупные октавы задают горы, мелкие — камни и рябь: тот самый фрактальный рельеф Minecraft. Быстро (O(1) на сэмпл, прекомпутируемо), параметризуемо, понятно. Simplex (Перлин, 2001) быстрее и без направленных артефактов; его 3D+-патент истёк 8 янв 2022, а OpenSimplex (Kurt Spencer, 2014) — clean-room патент-фри альтернатива.

L-системы, BSP, грамматики

L-системы — строковые правила переписывания: аксиома F, правило F → F[+F]F[-F]F, итерируешь, интерпретируешь как «черепашью графику» (F — вперёд, [] — стек позиции, ± — поворот). Рекурсия в правилах даёт древовидное ветвление — процедурная растительность.
BSP (Binary Space Partition) — рекурсивно дели прямоугольник, комнаты в листьях, коридоры между соседями. Гарантирует связность (коридор существует), естественная иерархия, O(n). Данжены Rogue/Diablo/рогаликов.
Грамматики уровней — Level → Entrance Room+ Boss Exit: сэмплируешь из грамматики + проверяешь ограничения (выход достижим, сложность сбалансирована).

Главный инсайт: ограничения вшиты в генерацию (Spelunky)

Spelunky (2008) шипнулся с процедурными уровнями, которые ощущаются рукотворными. Секрет — constraint satisfaction на этапе генерации, а не после: генератор гарантирует путь к выходу, рост сложности с глубиной, отсутствие тупиков — потому что ограничения вшиты в процесс, а не проверяются постфактум. «Сгенерируй уровень, потом проверь валидность» проигрывает «генерируй так, чтобы валидность не могла нарушиться». Отсюда определение: PCG — это не «случайно», это ограниченная случайность, где ограничения обеспечивают качество.

А GAN'ы? Фронтир, который обычно проигрывает

ML-augmented PCG существует: обучи GAN на уровнях (Mario-level papers, Volz et al.) — он выучит распределение «хороших» уровней и умеет интерполировать. Но на практике для шипабельного контента он проигрывает классике: выход часто невалиден (несостыкованные тайлы, непроходимо), трудно наложить жёсткие ограничения (уровень обязан быть проходим — а GAN гарантий не даёт), и он медленнее. ML-PCG полезен точечно (блендинг стилей, аугментация, текстуры), но структурный, ограничениями-связанный контент почти всегда дешевле и надёжнее сгенерировать классикой — это та же история, что с RL-агентами, но про контент.

🏠 Лаба — шум и рельеф вживую

Интерактивная лаба без кода: 2D-шум Перлина → карта высот, раскрашенная как рельеф (вода/песок/трава/скалы/снег). Крути частоту, число октав, lacunarity и persistence — и смотри, как из плавных холмов проступают горы и детали (fBm вживую). Меняй seed. Открыть лабу →

Формула fBm и разница Перлин/Simplex/OpenSimplex — в тексте и хардкоре; здесь — увидеть октавы руками.

🕹 Во что поиграть — и что заметить

Minecraft / No Man's Sky шум как рельеф

Мир Minecraft — это шум Перлина/Simplex по высоте (+пещеры 3D-шумом); NMS генерит планеты тем же аппаратом. Крупные формы + мелкие детали = октавы fBm.

🎮 Заметь: в Minecraft взлети повыше и разгляди иерархию масштабов: большие холмы (низкая октава) с наложенными буграми и рябью (высокие октавы). Это буквально сумма октав из формулы. И весь мир — не хранится, а вычисляется из seed'а (храни функцию, а не выход — как в железе).

Spelunky ограниченная случайность

Каждый уровень уникален и при этом всегда проходим: путь к выходу гарантирован генерацией, сложность растёт с глубиной. Ощущается рукотворным, хотя процедурен.

🎮 Заметь: в Spelunky сыграй несколько уровней и убедись — выход всегда достижим, тупиков-ловушек нет. Это не везение генератора, а вшитое ограничение. Сравни с ощущением «рандомного» уровня без ограничений (был бы непроходимый бардак). Вот разница «ограниченная случайность» vs «просто random».

Рогалик BSP-данжен

Классические рогалики (и Diablo) строят подземелья BSP: рекурсивное деление → комнаты в листьях → коридоры между соседями. Всегда связно, дёшево, «выглядит хорошо».

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

Хардкор · value vs gradient noise, октавы, Simplex/OpenSimplexможно пропустить

Value noise vs gradient noise

Value noise: случайные значения в узлах решётки + гладкая интерполяция (smoothstep). Просто, но даёт видимую «блочность» решётки. Gradient noise (Перлин): случайные градиенты в узлах, значение = интерполяция скалярных произведений градиент·(точка−узел); в узлах ноль, между — плавные экстремумы → визуально богаче, меньше осевых артефактов. fBm поверх любого: $\sum_{i = 0}^{k - 1} p^{i} noise (l^{i} x)$ — октавы добавляют детали на убывающих масштабах; при $p < 1$ ряд сходится, спектр степенной (потому и «фрактальный»/природный). Вариации: ridged (|noise|, гребни-хребты), domain warping (шум от координат, искажённых шумом — реки/прожилки).

Simplex, патент и OpenSimplex

Классический Перлин на кубической решётке требует $2^{n}$ углов в $n$ D (в 3D — 8, в 4D — 16) и даёт направленные артефакты по осям. Simplex (Перлин, 2001) кладёт узлы в симплекс-решётку → $n + 1$ углов (в 3D — 4), меньше умножений, лучше масштабируется в высокие размерности, нет осевых артефактов. Загвоздка: 3D+-использование Simplex было запатентовано (US 6,867,776), поэтому многие движки годами обходились Перлином; патент истёк 8 янв 2022. OpenSimplex (Kurt Spencer, 2014) — clean-room свободная альтернатива, тоже gradient noise, без артефактов Перлина. Практика: бери Simplex/OpenSimplex для скорости и изотропности, Перлин — если и так хватает.

Хардкор · почему классика бьёт GAN и связь с constrained-декодингомможно пропустить

Валидность как жёсткое ограничение

Игровой контент почти всегда имеет жёсткие инварианты: уровень обязан быть проходим, тайлы — стыковаться, данжен — связен. Классический PCG вшивает их в генерацию (BSP гарантирует связность конструктивно; Spelunky — путь к выходу; WFC — совместимость соседей). GAN учит мягкое распределение «похоже на хорошие уровни» и легко нарушает жёсткие инварианты — а постфактум-проверка+ресэмпл дорога и не гарантирует сходимости. Плюс контроль: у шума/грамматики есть ручки (частота, правила, seed), у GAN — латент, который трудно связать с «сделай проход шире». Поэтому для структурного контента ручной генератор+ограничения побеждает; ML заходит там, где распределение слишком богато для ручных правил (текстуры, натуральные изображения, диалоги), а жёстких инвариантов мало.

Тот же приём в LLM: constrained decoding

«Генерируй-с-ограничениями > сгенерируй-потом-проверь» — дословно structured/constrained generation в LLM: grammar-constrained decoding, JSON-schema/regex-принуждение, маскирование недопустимых токенов на каждом шаге гарантируют валидный вывод конструктивно, вместо «сгенерируй свободно → распарсь → отвергни → повтори». Это ровно инсайт Spelunky, перенесённый на генерацию токенов: вшей инвариант в процесс. А fBm/октавы ↔ роль структурных приоров и мультимасштабных/частотных разложений в ML (Fourier features, позиционные кодировки, multi-resolution). Мета-урок общий: дешёвый алгоритмический генератор с ограничениями часто бьёт дорогой обученный, когда в домене есть жёсткие правила валидности.

Аналогия

Процедурная генерация — как джазмен, импровизирующий в рамках тональности и гармонии: именно ограничения (тональность, темп, форма) превращают бесконечную вариацию в музыку, а не в шум. Шум Перлина — плавный мелодический контур; октавы — добавленные гармоники для фактуры; L-системы — рекурсивные мотивы; constraint satisfaction Spelunky — то, что музыкант не выходит из тональности и формы, поэтому любая импровизация играбельна. GAN, генерящий уровни, — как ИИ, выучивший имитировать джаз по записям, но иногда берущий неразрешённые ноты или такт в чужом размере: впечатляет, но на концерт без человека, чинящего сломанные такты, не выпустишь. Ограниченная случайность выходит в релиз; необученная генерация нуждается в няньке.

Почему это важно

Это контентная половина главного суждения курса (агентную дал RL): для структурного, связанного жёсткими правилами контента классические генеративные методы + ограничения бьют обученный генератор по валидности, контролю и стоимости. Для тебя как ML-инженера это и практический навык (шум/грамматики/WFC — дёшево и надёжно для твоего Новгорода), и перенос: «генерируй-с-ограничениями» — это constrained decoding в LLM, а «храни функцию, а не выход» — это про память и стоимость. Знать, когда алгоритмический генератор лучше нейросети, — часть той же зрелости.

🔁 Куда это ведёт — связи с твоим ML

Урок — про ограниченную случайность: генерацию, где валидность вшита в процесс, и про то, когда алгоритм бьёт обученный генератор.

ML / AI (твой домен): PCG-vs-GAN — контентная сторона всего тезиса: для структурной генерации с жёсткими инвариантами ручные правила + constraint satisfaction бьют обученный генератор (валидность, контроль, стоимость). Прямой мост — constrained/structured decoding в LLM: grammar/JSON-schema/regex-принуждение и маскирование токенов гарантируют валидный вывод конструктивно — ровно «генерируй-с-ограничениями > сгенерируй-потом-проверь-и-ретрай» (инсайт Spelunky на уровне токенов). Общий паттерн — генеративная модель + жёсткие ограничения (диффузия с guidance, program synthesis с типами, constrained sampling). fBm/октавы ↔ структурные приоры и мультимасштабные/частотные разложения (Fourier features, позиционные кодировки). «Храни функцию, а не выход» (мир из seed'а) ↔ неявные представления/INR и компрессия как генерация. А мета-урок — алгоритмический генератор с ограничениями часто лучше обученного, когда домен структурен, — та же дисциплина «когда ML не ответ», что и в RL-агентах, только про генерацию.

Дизайн/контент: ограниченная случайность = контролируемая вариативность; ручки (частота, правила, seed) важнее «магии» — воспроизводимость и правки.

Системы: «храни функцию, а не выход» — генерация на лету экономит память/полосу (мир из seed'а), детерминированная воспроизводимость по seed.

Принцип: для структурного контента бери алгоритм + ограничения по умолчанию; ML — где распределение слишком богато для правил и мало жёстких инвариантов; вшивай валидность в процесс, а не проверяй постфактум.

🔧 Запусти и поковыряй

🏠 Лаба «шум и рельеф» в браузере

Открой lab-noise.html: крути частоту, октавы, lacunarity, persistence — увидь fBm вживую (одна октава = плавно; много = горы+детали). Смени seed. Поставь 1 октаву и добавляй по одной, наблюдая, как проступает фрактальный рельеф.

🧪 Собери генератор ~40 мин, опц.

Напиши BSP-данжен (рекурсивное деление + коридоры) на Python/JS — десятки строк, всегда связный. Или L-систему для дерева (переписывание строки + turtle). Затем добавь одно жёсткое ограничение (напр., минимальный размер комнаты / гарантия проходимости) прямо в генерацию — прочувствуй «constrained randomness». Сравни с наивным «расставь случайно и надейся».

Чеклист: в лабе увидел октавы/fBm и роль lacunarity/persistence; понял «ограниченную случайность» на Spelunky/BSP; связал constrained-генерацию с constrained-декодингом LLM; сформулировал, где для контента ML НЕ нужен.

Связи

основа

Wave Function Collapse — брат-констрейнт: генерация тайл-миров через удовлетворение ограничений соседства.

параллель

RL-агенты — агентная версия «классика > ML»; здесь — контентная.

итог

Классика vs ML — куда для генерации звать ML, а где алгоритм лучше.

смежное

Железо-ограничения — «храни функцию, а не выход»: мир из seed'а вместо гигабайт.

Вопросы пытливого ума

Перлин, Simplex, OpenSimplex — что брать?

Все три — gradient noise (гладкая случайность через градиенты в узлах), различаются решёткой и историей. Перлин (1985) — на кубической решётке; проще всего, но требует

2^{n}

углов в

n

D и даёт лёгкие направленные (осевые) артефакты — сетка иногда «просвечивает». Simplex (Перлин, 2001) — на симплекс-решётке (

n + 1

углов), быстрее в высоких размерностях, без осевых артефактов; но его 3D+-использование было запатентовано, поэтому многие библиотеки годами избегали его. OpenSimplex (Kurt Spencer, 2014) — clean-room свободная альтернатива Simplex, тоже без артефактов, создана именно чтобы обойти патент. Патент Simplex истёк 8 янв 2022, так что юридически теперь можно и его. Практика: для 2D разница невелика — Перлина хватает; для 3D/4D (объёмные пещеры, анимированный шум во времени) бери Simplex/OpenSimplex ради скорости и изотропности. По качеству картинки Simplex и OpenSimplex взаимозаменяемы; выбор чаще по доступной библиотеке.

Почему PCG называют «не случайной»?

Потому что чистый random() для контента даёт мусор: несвязный рельеф, непроходимые уровни, деревья-кляксы. Работающая PCG — это ограниченная случайность: случайность есть, но она течёт по руслам, заданным структурой и ограничениями. Гладкость шума (близкие точки → близкие высоты) — это ограничение на «случайность» рельефа. Связность BSP (коридор между соседями всегда есть) — жёсткий инвариант. Проходимость Spelunky — вшитое правило. Совместимость соседей в WFC — ограничение. Именно ограничения превращают «шум» в «мир, который ощущается сделанным». Отсюда практический сдвиг мышления: не «сгенерирую случайно и посмотрю», а «какие инварианты обязаны держаться, и как встроить их в генерацию, чтобы они не могли нарушиться». Случайность даёт вариативность; ограничения дают качество; PCG — их произведение.

GAN'ы реально проигрывают классике для уровней?

Для шипабельного структурного контента — да, обычно. Исследования (Mario-level GANs, Volz et al. и др.) показали, что GAN может выучить распределение уровней и генерировать иногда играбельные — но три проблемы бьют по проду: (1) валидность — выход часто невалиден (несостыкованные тайлы, непроходимые участки), а жёсткую гарантию «проходим» GAN не даёт; (2) ограничения — наложить «выход обязан быть достижим» на латентную модель трудно, приходится постфактум-проверять и ресэмплить (дорого, без гарантии сходимости); (3) контроль и стоимость — у грамматики/шума есть понятные ручки и они дёшевы, у GAN — латент и инференс. Поэтому в проде почти всё — классика (шум, грамматики, BSP, WFC, constraint solvers). Где ML-PCG помогает: блендинг/интерполяция стилей, аугментация, генерация текстур и ассетов (там распределение богатое, а жёстких инвариантов мало — идеально для нейросети), style transfer. То есть ML заходит в «мягкую» генерацию (как выглядит), классика держит «жёсткую» (как устроено и играется). Это ровно граница «богатое распределение без жёстких правил → ML; структура с инвариантами → алгоритм».

Как «генерируй-с-ограничениями» переносится на LLM?

Это дословно constrained / structured decoding. Инсайт Spelunky — «вшей валидность в генерацию, а не проверяй постфактум» — на уровне токенов означает: на каждом шаге декодирования маскируй токены, которые нарушили бы грамматику/схему, оставляя модели выбор только среди валидных продолжений. Grammar-constrained decoding (по формальной грамматике), JSON-schema/regex-принуждение (llguidance, Outlines, GBNF в llama.cpp) гарантируют конструктивно валидный вывод — распарсится всегда, ретраи не нужны. Альтернатива «сгенерируй свободно → распарсь → если сломано, повтори» — это ровно «сгенерируй уровень → проверь → отвергни», которое проигрывает и в играх, и в токенах (дорого, без гарантии). Более общий паттерн — генеративная модель + жёсткие ограничения в процессе: диффузия с guidance/проекцией на допустимое множество, program synthesis с проверкой типов на каждом расширении, constrained sampling. Освоив «PCG = ограниченная случайность», ты уже понимаешь, почему constrained decoding надёжнее свободной генерации с постпроверкой: ограничение, встроенное в процесс, не может быть нарушено, а ограничение-постфактум — может и требует дорогого ретрая.

Что почитать

Ken Perlin — «Improving Noise» (2002, Simplex); Stefan Gustavson — «Simplex noise demystified».
«The Book of Shaders» (гл. про noise) + Red Blob Games — интерактивные объяснения шума/fBm.
Przemyslaw Prusinkiewicz — «The Algorithmic Beauty of Plants» (L-системы).
Derek Yu — постмортем генерации Spelunky (constrained randomness); Volz et al. — «Evolving Mario Levels in the Latent Space of a GAN» (2018).
Модуль 11, §4 «Procedural Content Generation» (11-ai-ml-in-games.md).

← назадWave Function Collapse дальше →LLM-NPC

Источник: модуль 11, §4 «Procedural Content Generation» (11-ai-ml-in-games.md). Perlin (1985), Simplex (2001), патент истёк 8 янв 2022, OpenSimplex (Kurt Spencer, 2014) — веб-сверено.