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

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

Идеальный лабиринт - это лабиринт, в котором есть ровно один путь из любой точки лабиринта в любую другую точку. Это значит, что вы не сможете ходить по кругу, но часто будете сталкиваться с тупиками, вынужденными разворачиваться и идти обратно.

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

О алгоритме построения дерева

Алгоритм «Растущее дерево» — это гибкий и мощный метод генерации идеальных лабиринтов. Интерес к этому алгоритму заключается в том, что он может имитировать поведение нескольких других алгоритмов генерации лабиринтов, таких как алгоритм Прима, рекурсивный поиск с возвратом и рекурсивное деление, в зависимости от того, как вы выбираете следующую ячейку для обработки.

Как работает алгоритм построения дерева

Шаг 1: Инициализация

• Начните с сетки из непосещенных ячеек.
• Выберите случайную начальную ячейку и добавьте её в список.

Шаг 2: Цикл генерации лабиринта

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

Шаг 3: Завершение

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

Стратегии выбора клеток (гибкость алгоритма)

Отличительной особенностью алгоритма «Растущее дерево» является способ выбора клетки для дальнейшей обработки. Этот выбор существенно влияет на внешний вид лабиринта:

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

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

Случайная ячейка (алгоритм рандомизации Прима):

• Каждый раз выбирайте случайную ячейку из списка.
• Создает более равномерно распределенный лабиринт со сложными, запутанными путями.
• Меньше длинных коридоров и больше разветвлений.

Самая старая клетка (поведение, подобное очереди):

• Всегда выбирайте самую старую ячейку в списке.
• Создает лабиринты с более равномерным распределением объектов, подобно алгоритму поиска в ширину.
• Короткие, заросшие кустарником проходы с густыми связями.
• (Здесь реализована именно эта версия)

Гибридные подходы:

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

• 90% новых элементов, 10% случайных: в основном напоминает рекурсивный лабиринт с возвратом назад, но с occasional разветвлениями, которые прерывают длинные коридоры.
• 50% новых, 50% старых: сбалансированное сочетание длинных коридоров и густой растительности.

Дополнительное чтение

Если вам понравился этот пост, вам также могут понравиться эти предложения:

• Генератор лабиринтов на основе алгоритма Уилсона
• Рекурсивный генератор лабиринтов с обратным отслеживанием
• Генератор лабиринта алгоритма Эллера