Алгоритм вирощування дерева Генератор лабіринтів

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

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

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

Про алгоритм вирощування дерева

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

Як працює алгоритм вирощування дерева

Крок 1: Ініціалізація

• Почніть з сітки невідвіданих клітинок.
• Виберіть випадкову початкову клітинку та додайте її до списку.

Крок 2: Петля генерації лабіринту

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

Крок 3: Припинення

• Алгоритм завершується, коли в списку більше немає клітинок, тобто весь лабіринт вирізаний.

Стратегії вибору клітин (гнучкість алгоритму)

Визначальною особливістю алгоритму «Зростаюче дерево» є те, як ви вибираєте, яку клітинку обробляти далі. Такий вибір кардинально впливає на зовнішній вигляд лабіринту:

Найновіша комірка (поведінка, схожа на стек) – рекурсивний зворотний трекер:

• Завжди виділяйте останню додану клітинку.
• Утворює довгі, звивисті коридори з безліччю глухих кутів (як лабіринт пошуку на глибині).
• Лабіринти, як правило, мають довгі проходи і їх легко вирішити.

Випадкова клітинка (рандомізований алгоритм Пріма):

• Щоразу вибирайте випадкову клітинку зі списку.
• Створює більш рівномірно розподілений лабіринт зі складними, заплутаними стежками.
• Менше довгих коридорів і більше розгалуженості.

Найстаріша клітинка (поведінка, схожа на чергу):

• Завжди вибирайте найстарішу клітинку у списку.
• Генерує лабіринти з більш рівномірним розподілом, як за схемою пошуку по ширині.
• Короткі, кущисті ходи з щільними з'єднаннями.
• (Ця версія реалізована тут)

Гібридні підходи:

Комбінуйте стратегії для різних характеристик лабіринту. Наприклад:

• 90% найновіші, 10% випадкові: В основному виглядає як рекурсивний лабіринт зворотного трекера, але з випадковими гілками, які розбивають довгі коридори.
• 50% найновіші, 50% найстаріші: Врівноважує довгі коридори з кущистою порослю.