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

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

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

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

Про алгоритм зростаючого дерева

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

Як працює алгоритм зростаючого дерева

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

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

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

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

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

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

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

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

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

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

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

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

Найстаріша комірка (поведінка, подібна до черги):

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

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

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

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

Додаткова література

Якщо вам сподобався цей пост, вам також можуть сподобатися ці пропозиції:

• Генератор рекурсивних лабіринтів Backtracker
• Генератор лабіринтів алгоритму Вільсона
• Генератор лабіринтів алгоритму Крускала