Алгоритми генерації лабіринтів — DFS, Прима, Вілсона та інші

1. Лабіринти як кістякові дерева

Змоделюйте ґратку W×H як граф, де кожна клітинка — вершина, а суміжні клітинки мають спільне ребро. Досконалий лабіринт вимагає:

• Усі W×H клітинок зв’язані (рівно один шлях між будь-якими двома клітинками).
• Немає циклів (немає петель, немає кількох шляхів).

Це саме кістякове дерево — зв’язний ациклічний підграф, що відвідує кожну вершину. Ґратка W×H має W×H вершин та W(H−1) + H(W−1) = 2WH−W−H ребер; кістякове дерево використовує рівно W×H − 1 ребер. Кожен алгоритм обирає різні ребра для включення, утворюючи різні кістякові дерева з різними статистичними властивостями.

2. Рекурсивний пошук із поверненням (DFS)

Найпростіший і найпопулярніший алгоритм лабіринтів. Почніть із випадкової клітинки, позначте її відвіданою, потім багаторазово:

1. Оберіть випадкового невідвіданого сусіда.
2. Зруйнуйте стіну між поточною клітинкою та обраним сусідом.
3. Перейдіть до обраної клітинки та повторіть.
4. Якщо невідвіданих сусідів немає, поверніться до попередньої клітинки.

function generateDFS(grid, start) {
  const visited = new Set([start]);
  const stack = [start];
  while (stack.length) {
    const cell = stack[stack.length - 1];
    const unvisited = neighbours(cell).filter(n => !visited.has(n));
    if (unvisited.length === 0) { stack.pop(); continue; }
    const next = unvisited[randInt(0, unvisited.length)];
    removeWall(cell, next);
    visited.add(next);
    stack.push(next);
  }
}

Складність: O(W×H). Характер: довгі звивисті коридори з небагатьма перехрестями. Легко розв’язується інтуїтивно, прямуючи головним шляхом. Використання пам’яті: глибина стека O(W×H) у найгіршому випадку.

3. Алгоритм Прима

Будує кістякове дерево, завжди розширюючи «найдешевше» ребро межі. Для випадкових лабіринтів усі ребра мають однакову вагу — тож ми вибираємо рівноймовірно випадково з поточної межі:

1. Почніть з однієї випадкової клітинки в множині лабіринту; додайте всі її стіни до списку межі.
2. Виберіть випадкову стіну з межі. Якщо сусіда по той бік ще немає в лабіринті: видаліть стіну, додайте сусіда до лабіринту, додайте його нові стіни до межі.
3. Повторюйте, доки межа не спорожніє.

Алгоритм Прима породжує лабіринти з рівномірним деревоподібним розгалуженням. Лабіринт поширюється назовні від початку, наче кристал, що росте, з багатьма короткими тупиковими «щупальцями» в усіх напрямках одночасно — візуально дуже відмінний від довгих коридорів DFS.

4. Блукання зі стиранням петель Вілсона

Алгоритм Вілсона (1996) — єдиний простий алгоритм, що генерує рівномірно випадкове кістякове дерево — кожен можливий досконалий лабіринт для заданої ґратки рівноймовірний.

1. Додайте одну довільну клітинку до множини лабіринту.
2. Оберіть будь-яку невідвідану клітинку як початкову точку блукача.
3. Виконуйте випадкове блукання, доки воно не натрапить на будь-яку клітинку, що вже є в лабіринті.
4. Зітріть усі петлі зі шляху блукання (роблячи його простим шляхом).
5. Додайте весь шлях зі стертими петлями до лабіринту.
6. Повторюйте з кроку 2, доки всі клітинки не опиняться в лабіринті.

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

5. Алдуса–Бродера

Найпростіший неупереджений алгоритм рівномірного кістякового дерева — але також найповільніший:

1. Почніть з випадкової клітинки. Позначте її відвіданою.
2. Перейдіть до випадкового сусіда. Якщо сусіда ще не відвідано, видаліть стіну й позначте його відвіданим.
3. Повторюйте, доки всі клітинки не відвідано.

Стирання петель не потрібне — будь-яке випадкове блукання зрештою за означенням відвідує всі клітинки. Останнє ребро, що веде до кожної щойно відвіданої клітинки, утворює кістякове дерево. Як і алгоритм Вілсона, цей породжує рівномірні випадкові кістякові дерева, але потребує O(N log N) очікуваних кроків (задача «збирача купонів») — зазвичай у 5–10 разів повільніше за DFS для великих ґраток.

6. Краскала та Еллера

Алгоритм Краскала

Призначте випадкові ваги всім ребрам ґратки, потім додавайте ребра в порядку зростання ваги, поки ребро з’єднує дві різні компоненти (використовуючи структуру «об’єднання-пошук», Union-Find). Результат — рівномірно випадкове кістякове дерево. Час роботи O(E log E) = O(N log N) за ефективної реалізації Union-Find.

Алгоритм Еллера

Унікальний порядковий алгоритм лабіринтів: генерує лабіринти в O(W) пам’яті незалежно від висоти, що робить його єдиним алгоритмом, придатним для генерації як завгодно високих лабіринтів із дуже малою пам’яттю:

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

7. Порівняння та упередженість

Вибір алгоритму є водночас естетичним і математичним. Геймдизайнери зазвичай надають перевагу DFS для приємних ігрових лабіринтів; дослідникам, що вивчають дифузійно-обмежену агрегацію чи просторові моделі, можуть знадобитися неупереджені дерева Вілсона. Симуляція лабіринтів на цьому сайті дозволяє вам генерувати й порівнювати всі п’ять родин поруч.