Процедурні Підземелля: Дерева BSP, Клітинні Печери та Насінний Хаос

Чому випадкові рівні потребують насіння

Кожна процедурна підземель починається з числа. Це число, насіння, живить псевдослучайний генератор чисел — швидкий, детерміновальний алгоритм, такий як mulberry32 або xorshift32, який генерує довгий ряд чисел, що здаються випадковими, але повністю відтворювані з одного й того ж початкового стану. Генератори не звертаються до справжнього джерела ентропії операційної системи, оскільки справжня випадковість зіпсувала б мету: введіть одне й те саме насіння двічі і ви повинні отримати точну саму підземель, коридор за коридором, кімната за кімнатою.

Ця відтворюваність дозволяє обмінюватися насінням між гравцями, дозволяє щоденному виклику дати кожному однакову мапу та дозволяє розробнику відтворити звіт про помилку, просто попросивши насіння, яке спричинило її. Кожне рішення подальшого — як ділиться регіон, де опиниться кімната, який номер сусідів перевертає клітину на підлогу — насправді лише кілька наступних чисел, витягнутих з цього одного детермінованого потоку.

Двовимірне просторове розділення: кімнати з дерева

Двовимірне просторове розділення, або ДПР, починається з одного великого прямокутника, що представляє всю карту, і рекурсивно ділиться на дві частини випадковою віссю, іноді вертикальною, іноді горизонтальною, у випадково визначеній позиції. Кожен шматок ділиться ще раз, і ще раз, поки область не стає занадто маленькою, щоб її розділити, або досягнуто фіксованої глибини рекурсії. Результатом є двовидове дерево з вкладених прямокутників, і кожна листова частина цього дерева стає кімнатою: зазвичай неправильний прямокутник, вирізаний дещо менше, ніж його листова область, щоб кімнати не торкалися межі розділення точно.

Зв’язність виникає з тієї ж структури дерева безкоштовно. Проходження назад від будь-якої пари листових частин до їх спільного батьківського вузла дає пару кімнат, які потрібно з’єднати, тому коридор вирізається з центру однієї кімнати до центру іншої — зазвичай проста форма L, одна пряма лінія горизонтально та одна вертикально. Оскільки кожна листова частина доступна від кореня завдяки конструкції, ДПР-підземелля гарантовано повністю з’єднане і ніколи не має перекритих кімнат, без необхідності перевіряти будь-яке з них.

Випадкові кімнати та розгалужена структура

Більш невимушений підхід розкидає фіксовану кількість прямокутних кімнат безпосередньо на карті різними розмірами та позиціями, відхиляючи та повторно намагаючись будь-яку кімнату, яка перетинається з вже існуючою. Після створення достатньої кількості кімнат вони все ще потребують коридорів, тому генератор розглядає центр кожної кімнати як вузол графа та будує структуру зв’язків над ними — це може бути Delaunay триангуляція центрів або просто мінімальне покриваюче дерево між усіма парами відстаней, а потім вирізається L-подібний коридор вздовж кожного виживання краю.

Чисте розгалужене дерево з'єднує все найменшою кількістю коридорів, що також означає, що підземелля є єдильним деревом без циклів — кожен шлях є тупиком або прямою дорогою без альтернатив. Генератори часто додають кілька додаткових ребер з триангуляції, які відкинули розгалужене дерево, створюючи періодичні цикли, щоб гравці не були загнані по одній лінійній колії протягом усього рівня.

Автомати слауки: печери, що ростуть як у житті

Автомати слауки печер починаються з чистого шуму: кожна клітинка на сітці незалежно позначається як підлогу з деякою початковою ймовірністю, зазвичай близько 45%, і як стіна в іншому випадку. Потім застосовується правило вирівнювання до всієї сітки одночасно, один раз на покоління, протягом кількох поколінь поспіль — структурно такий самий принцип, як у грі Conway's Game of Life, але налаштований з порогом, який змушує сітку сходитися до гладких крапель замість нескінченного коливання.

для покоління в 1..N: для кожної клітинки (x, y) у сітці: рахунок = кількість клітинок підлоги серед 8 сусідів клітинки (x, y) якщо рахунок > 4: newGrid[x][y] = підлога інакше якщо рахунок < 4: newGrid[x][y] = стіна інакше: newGrid[x][y] = grid[x][y] // незмінне в разі нічиєї grid = newGrid Після чотирьох або п’яти поколінь шум усаджується в округлі, органічно виглядаючі печери. Правило само по собі не гарантує, що результат буде одним з’єднаним простором — воно часто залишає кілька невеликих відключених ділянок — тому після цього запускається заповнення потоком, щоб знайти кожну зв'язану область, залишити лише найбільшу та заповнити решту стінами.

for generation in 1..N:
  for each cell (x, y) in grid:
    count = number of FLOOR cells among the 8 neighbours of (x, y)
    if count > 4:
      newGrid[x][y] = FLOOR
    else if count < 4:
      newGrid[x][y] = WALL
    else:
      newGrid[x][y] = grid[x][y]   // unchanged on a tie
  grid = newGrid

Вибір методу: контроль проти хаосу

Жодного з трьох методів не є строго кращим – вони обмінюють контроль на природність у різній мірі. BSP гарантує зв’язність і виробляє прямолінійні, архітектурно логічні кімнати, що підходить для підземель, будівель та космічних станцій, де прямі стіни мають сенс. Клеточна автоматика повністю відмовляється від цього архітектурного контролю в обмін на органічні, печерні форми, які ніхто не спроектував би вручну, але потребує додаткового пропуску зв’язності після цього. Випадкові кімнати з каркасною структурою знаходяться між ними: неправильні форми та розташування кімнат, як у печері, але з гарантією зв’язності графа, як BSP-дерево – розумний за замовчуванням варіант, коли ні геометрія чи ні шум не відповідають точно тому, що потрібне рівню.

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте the simulation і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.