Процедурная генерация подземелий: BSP-деревья, клеточные автоматы и проверка связности

Коротко

Подземелье для 2D-игры чаще всего генерируют одним из двух способов. BSP-дерево делит карту на прямоугольники, ставит в каждый лист комнату и соединяет соседние комнаты коридорами; клеточный автомат превращает случайный шум (около 45% стен) в пещеры за 4–5 итераций правила «стена, если рядом не меньше 5 стен». Любой результат проверяют заливкой на связность и игровыми метриками, а генератор запускают от явного зерна, чтобы уровень можно было воспроизвести при отладке.

Содержание

1. С чего всё началось: сетка комнат Rogue
2. BSP-дерево: комнаты и коридоры
3. Клеточный автомат: пещеры
4. Связность: заливка и перегенерация
5. Зерно генератора и воспроизводимость
6. Сравнение подходов
7. Игровые проверки уровня
8. Когда вам это не подойдёт

С чего всё началось: сетка комнат Rogue

Процедурные подземелья в играх пошли от Rogue — игры Майкла Тоя и Гленна Уичмана примерно 1980 года, к которой позже присоединился Кен Арнольд (Wikipedia, проверено: ноябрь 2026). По Wikipedia, уровень Rogue строится на сетке 3×3, как поле для крестиков-ноликов: в каждой ячейке может стоять комната, комнаты соединены коридорами. Авторы перешли к этой схеме потому, что чисто случайная генерация давала уровни, где лестница вниз оказывалась недоступной. Отсюда главный урок, который действует до сих пор: генератор должен гарантировать проходимость, а не надеяться на неё.

BSP-дерево: комнаты и коридоры

BSP-генерация рекурсивно делит прямоугольник карты на два, пока части не станут достаточно маленькими, а затем ставит в каждый лист по комнате. Алгоритм на RogueBasin (статья Basic BSP Dungeon generation, проверено: ноябрь 2026) устроен так:

1. Выбрать направление разреза (горизонтально или вертикально) и позицию разреза случайно.
2. Повторять для каждой половины, пока части не достигнут минимального размера.
3. В каждом листе дерева поставить комнату случайного размера внутри его прямоугольника — комнаты никогда не пересекаются, потому что не пересекаются листья.
4. Соединить коридором комнаты двух «сестёр» (листьев с общим родителем), затем подняться по дереву и так же соединить соседние поддеревья.

Позиция разреза управляет характером уровня. По RogueBasin, разрез в диапазоне от 0,45 до 0,55 длины даёт части близкого размера, а диапазон от 0,1 до 0,9 — заметно разнородные.

function split(rect, minSize, rnd, leaves) {
  const canH = rect.h >= minSize * 2, canV = rect.w >= minSize * 2;
  if (!canH && !canV) { leaves.push(rect); return; }
  const vertical = canV && (!canH || rnd() < 0.5);
  const ratio = 0.45 + rnd() * 0.1;                 // однородные части
  if (vertical) {
    const w = Math.floor(rect.w * ratio);
    split({ x: rect.x, y: rect.y, w: w, h: rect.h }, minSize, rnd, leaves);
    split({ x: rect.x + w, y: rect.y, w: rect.w - w, h: rect.h }, minSize, rnd, leaves);
  } else {
    const h = Math.floor(rect.h * ratio);
    split({ x: rect.x, y: rect.y, w: rect.w, h: h }, minSize, rnd, leaves);
    split({ x: rect.x, y: rect.y + h, w: rect.w, h: rect.h - h }, minSize, rnd, leaves);
  }
}

Коридоры, по RogueBasin, бывают прямыми или Z-образными (с одним изломом). Чтобы их соединять, удобнее хранить дерево, а не только список листьев: тогда пары «сестёр» и соседних поддеревьев берутся напрямую.

Клеточный автомат: пещеры

Клеточный автомат превращает случайный шум в пещеры, многократно применяя одно локальное правило к каждой клетке. Базовый рецепт RogueBasin (статья Cellular Automata Method for Generating Random Cave-Like Levels, проверено: ноябрь 2026): заполнить карту стенами с вероятностью 45% и пять раз применить правило 4-5.

R1 = число стен в квадрате 3×3 вокруг клетки (включая её саму)
R2 = число стен в квадрате 5×5 вокруг клетки

правило 4-5:            стена, если R1 ≥ 5, иначе пол
улучшенный рецепт:      заполнение 40%
                        4 итерации: стена, если R1 ≥ 5 или R2 ≤ 2
                        3 итерации: стена, если R1 ≥ 5

Смысл улучшенного рецепта виден из самого правила: условие R2 ≤ 2 ставит стену посреди почти пустого квадрата 5×5, поэтому в больших залах появляются отдельные колонны, а последние итерации без этого условия сглаживают края.

function caveStep(map, W, H, useR2) {
  const out = new Uint8Array(W * H);
  const wall = (x, y) => (x < 0 || y < 0 || x >= W || y >= H) ? 1 : map[y * W + x];
  for (let y = 0; y < H; y++) for (let x = 0; x < W; x++) {
    let r1 = 0, r2 = 0;
    for (let dy = -2; dy <= 2; dy++) for (let dx = -2; dx <= 2; dx++) {
      const w = wall(x + dx, y + dy);
      r2 += w;
      if (Math.abs(dx) <= 1 && Math.abs(dy) <= 1) r1 += w;
    }
    out[y * W + x] = (r1 >= 5 || (useR2 && r2 <= 2)) ? 1 : 0;
  }
  return out;
}

Клетки за краем карты здесь считаются стенами — так пещера не «вытекает» за границу.

Связность: заливка и перегенерация

Клеточный автомат не гарантирует, что все пещеры соединены, поэтому результат проверяют заливкой. RogueBasin предлагает такой порядок: залить открытую область от случайной точки пола, всё, что не попало в заливку, превратить в стену, и если открытой осталось слишком мало (в статье — меньше примерно 45% карты), сгенерировать уровень заново.

1. найти все связные области пола заливкой
2. оставить самую большую, остальные закрасить стеной
3. открытая площадь ≥ порога? да → дальше; нет → новое зерно, заново

Для BSP-подземелья связность обеспечивается построением: каждый шаг подъёма по дереву соединяет два поддерева, поэтому в итоге связаны все комнаты. Проверить заливкой всё равно полезно — она ловит ошибки в коде коридоров.

Зерно генератора и воспроизводимость

Генератор уровней должен работать от явного зерна, иначе баг на конкретном уровне невозможно повторить. Встроенный Math.random для этого не подходит: по MDN зерно выбирает сама реализация, и пользователь не может его задать или сбросить (проверено: ноябрь 2026). Поэтому в генерацию передают собственную функцию случайных чисел:

function makeRng(seed) {
  let s = seed >>> 0;
  return function () {                       // простой линейный конгруэнтный генератор
    s = (Math.imul(s, 1664525) + 1013904223) >>> 0;
    return s / 4294967296;                    // число от 0 до 1
  };
}

const rnd = makeRng(20261102);               // зерно можно показать игроку

Такой генератор не годится для криптографии, но для уровней достаточен. Зерно стоит выводить в отладочной информации и сохранять вместе с отчётом об ошибке.

Сравнение подходов

Выбор алгоритма определяется тем, какое пространство нужно игре.

Подходы совмещают: например, BSP для общего плана и клеточный автомат внутри отдельных листов, чтобы часть комнат стала пещерами. Готовая реализация пещерного клеточного автомата на JavaScript есть в библиотеке rot.js, на которую ссылается RogueBasin.

Игровые проверки уровня

Связный уровень ещё не значит интересный, поэтому после генерации нужны игровые проверки. Пример для рогалика на карте 80×45; проверяемый результат — из 1000 зёрен подряд ни одно не даёт уровень, проваливший проверки, или каждое такое зерно отбраковано и перегенерировано.

1. Расстояние от входа до выхода — поиск в ширину по клеткам; например, не меньше половины ширины карты, иначе выход слишком близко.
2. Доля открытой площади — в выбранном диапазоне, например от 35% до 60%.
3. Нет тупиков у входа: из стартовой комнаты ведёт не меньше одного коридора.
4. Расстановка предметов — только в клетках, достижимых от входа, и не на кратчайшем пути, если предмет должен вознаграждать исследование.
5. Время генерации — замерить через performance.now() на слабом телефоне.
6. Логирование зерна — каждое отбракованное зерно с причиной.

Числа в проверках — отправная точка, а не стандарт: их подбирают по ощущениям от игры на десятках уровней.

Когда вам это не подойдёт

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

• Платформер с точными прыжками. Генератор комнат не знает высоту и дальность прыжка; уровни получаются непроходимыми или скучными. Компромисс — собирать уровень из нарисованных вручную фрагментов.
• Головоломка или сюжетная сцена. Решение головоломки и подача сюжета требуют авторской расстановки.
• Обучающие уровни. Первые минуты игры должны учить механикам в заданном порядке.
• Мало времени на настройку. Хороший генератор требует десятков итераций настройки параметров и проверок; для игры на 5 уровней проще нарисовать их.

Мы разрабатываем J2DRU — браузерный 2D игровой движок; он в разработке и публично пока не открыт, заявку можно оставить на странице раннего доступа (подача заявки не гарантирует приглашение).

Источники (проверено: ноябрь 2026): Wikipedia — Rogue (video game) (авторы, около 1980 года, сетка комнат 3×3, недоступные лестницы при чисто случайной генерации); RogueBasin — Basic BSP Dungeon generation (деление, диапазоны разреза, комнаты в листьях, коридоры); RogueBasin — Cellular Automata Method for Generating Random Cave-Like Levels (45%, правило 4-5, улучшенный рецепт, заливка и порог около 45%, ссылка на rot.js); MDN — Math.random() (зерно не задаётся). Код и числа игровых проверок — наш пример.

Читайте также:

• Тайловые сетки и устройство 2D-миров
• Поиск пути A* на тайловой сетке
• История ключевых механик 2D-игр