🏰 Процедурний генератор підземель

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

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

Печера починається як сітка, випадково заповнена стінами у вибраному відсотку від 35 до 60. Потім вона згладжується протягом кількох проходів: на кожному проході кожен тайл підраховує, скільки з його 8 навколишніх сусідів є стінами, і сам стає стіною, якщо стінами є 5 або більше сусідів, інакше стає підлогою. Повторення цього кілька разів усуває ізольований шум і перетворює малі скупчення стін на гладкі, органічні стіни печери — той самий принцип, що лежить в основі «Гри в життя» Конвея, застосований до генерації рівнів.

Симуляція використовує лінійний конгруентний генератор, або LCG: просту формулу, яка повторно перетворює внутрішній 32-бітний стан за допомогою множення й додавання з фіксованими константами, створюючи детермінований потік псевдовипадкових чисел. Оскільки генератор скидається до того самого значення сіда щоразу при натисканні «Генерувати», введення того самого сіда з тим самим алгоритмом і параметрами завжди створює ідентичне планування підземелля, тому поле сіда й кнопка «Новий сід» дозволяють зберегти або відтворити конкретну карту.

Після генерації підземелля симуляція запускає пошук у ширину від однієї клітинки підлоги, щоб знайти найвіддаленішу досяжну клітинку, а потім запускає другий пошук у ширину від тієї клітинки, щоб знайти справжній діаметр зв'язної області — класична техніка «подвійного BFS» для знаходження найдовшого найкоротшого шляху в неозваженому графі. Дві кінцеві точки стають маркерами старту й виходу, довжина шляху між ними показується як «Найдовший шлях», а «Зв'язність» повідомляє, який відсоток усіх клітинок підлоги досяжний зі старту, що вказує, чи має печера або підземелля ізольовані, недосяжні кишені.