Генератор на лабиринт за алгоритъм за отглеждане на дървета

Алгоритъмът Growing Tree е интересен, защото може да емулира поведението на няколко други алгоритъма, в зависимост от това как е избрана следващата клетка по време на генерирането. Реализацията на тази страница използва подход, подобен на опашка.

Перфектен лабиринт е лабиринт, в който има точно един път от всяка точка в лабиринта до всяка друга точка. Това означава, че не можете да се въртите в кръг, но често ще срещате задънени улици, което ще ви принуди да се обърнете и да се върнете обратно.

Генерираните тук карти на лабиринта включват версия по подразбиране без начални и крайни позиции, така че можете да ги определите сами: ще има решение от всяка точка в лабиринта до всяка друга точка. Ако искате да получите вдъхновение, можете да активирате предложена начална и крайна позиция - и дори да видите решението между двете.

За алгоритъма за растящо дърво

Алгоритъмът Growing Tree е гъвкав и мощен метод за генериране на перфектни лабиринти. Алгоритъмът е интересен, защото може да емулира поведението на няколко други алгоритъма за генериране на лабиринти, като алгоритъма на Прим, рекурсивно връщане назад и рекурсивно делене, в зависимост от това как избирате следващата клетка за обработка.

Как работи алгоритъмът за растящо дърво

Стъпка 1: Инициализация

• Започнете с мрежа от непосетени клетки.
• Изберете произволна начална клетка и я добавете към списък.

Стъпка 2: Цикъл за генериране на лабиринт

• Докато списъкът с клетки не е празен:
  • Изберете клетка от списъка въз основа на конкретна стратегия (обяснена по-долу).
  • Издълбайте проход от избраната клетка до един от нейните непосетени съседи (избран на случаен принцип).
  • Добавете съседа към списъка, тъй като вече е част от лабиринта.
  • Ако избраната клетка няма непосетени съседи, премахнете я от списъка.

Стъпка 3: Прекратяване

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

Стратегии за избор на клетки (гъвкавост на алгоритъма)

Определящата характеристика на алгоритъма Growing Tree е как избирате коя клетка да обработите следващата. Този избор драматично влияе на външния вид на лабиринта:

Най-нова клетка (подобно на стек поведение) – Рекурсивен обратен тракер:

• Винаги избирайте последната добавена клетка.
• Създава дълги, криволичещи коридори с много задънени улици (като лабиринт за търсене на дълбочина).
• Лабиринтите обикновено имат дълги пасажи и са лесни за решаване.

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

• Избирайте произволна клетка от списъка всеки път.
• Създава по-равномерно разпределен лабиринт със сложни, заплетени пътеки.
• По-малко дълги коридори и повече разклонения.

Най-старата клетка (поведение, подобно на опашка):

• Винаги избирайте най-старата клетка в списъка.
• Генерира лабиринти с по-равномерно разпространение, като модел на търсене в ширина.
• Къси, храстовидни проходи с плътни връзки.
• (Това е версията, реализирана тук)

Хибридни подходи:

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

• 90% най-новите, 10% случайни: Прилича най-вече на рекурсивен лабиринт за проследяване, но с редки разклонения, които разбиват дълги коридори.
• 50% най-нови, 50% най-стари: Балансира дълги коридори с храстовиден растеж.