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

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

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

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

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

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

Как работает алгоритм растущего дерева

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

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

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

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

Шаг 3: Расторжение

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

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

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

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

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

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

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

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

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

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

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

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