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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ако ви е харесала тази публикация, може да ви харесат и тези предложения:

• Генератор на лабиринт на алгоритъма на Уилсън
• Рекурсивен генератор на лабиринт за обратно проследяване
• Генератор на лабиринти с алгоритъм на Eller