Генератор на лавиринт со алгоритам на растечки дрвја

Алгоритмот Растечко дрво е интересен, бидејќи може да го емулира однесувањето на неколку други алгоритми, во зависност од тоа како е избрана следната ќелија за време на генерирањето. Имплементацијата на оваа страница користи пристап на прво место, сличен на редица.

Совршен лавиринт е лавиринт во кој има точно една патека од која било точка во лавиринтот до која било друга точка. Тоа значи дека не можете да завршите да одите наоколу во кругови, но често ќе наидете на ќорсокак, што ќе ве принуди да се свртите и да се вратите назад.

Мапите на лавиринтот генерирани овде вклучуваат стандардна верзија без никакви позиции за почеток и крај, така што можете сами да ги решите тие: ќе има решение од која било точка во лавиринтот до која било друга точка. Ако сакате инспирација, можете да овозможите предложена почетна и завршна позиција - па дури и да го видите решението помеѓу двете.

За алгоритмот на растечко дрво

Алгоритмот Growing Tree е флексибилен и моќен метод за генерирање совршени лавиринти. Алгоритмот е интересен затоа што може да го емулира однесувањето на неколку други алгоритми за генерирање на лавиринтот, како што е алгоритмот на Прим, рекурзивно враќање назад и рекурзивна поделба, во зависност од тоа како ќе ја изберете следната ќелија за обработка.

Како функционира алгоритмот на растечко дрво

Чекор 1: Иницијализација

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

Чекор 2: Јамка за генерација на лавиринт

• Додека списокот со ќелии не е празен:
  • Изберете ќелија од списокот врз основа на одредена стратегија (објаснето подолу).
  • Издлаби премин од избраната ќелија до еден од нејзините непосетени соседи (избран по случаен избор).
  • Додадете го соседот на списокот бидејќи сега е дел од лавиринтот.
  • Ако избраната ќелија нема непосетени соседи, отстранете ја од списокот.

Чекор 3: Престанок

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

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

Дефинитивната карактеристика на алгоритмот Растечко дрво е како да изберете која ќелија да ја обработувате следната. Овој избор драматично влијае на изгледот на лавиринтот:

Најновата ќелија (однесување налик на оџак) – Рекурзивен повратник:

• Секогаш избирајте ја неодамна додадената ќелија.
• Произведува долги, извртени коридори со многу мртви краеви (како лавиринт за пребарување во длабочина).
• Лавиринтите имаат тенденција да имаат долги премини и лесно се решаваат.

Случајна ќелија (рандомизиран прим алгоритам):

• Изберете случајна ќелија од списокот секој пат.
• Создава порамномерно распореден лавиринт со сложени, заплеткани патеки.
• Помалку долги коридори и повеќе разгранување.

Најстарата ќелија (однесување како редица):

• Секогаш избирајте ја најстарата ќелија во списокот.
• Генерира лавиринти со порамномерно ширење, како шема за пребарување во прв план.
• Кратки, грмушки премини со густи врски.
• (Ова е верзијата имплементирана овде)

Хибридни пристапи:

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

• 90% најново, 10% случајно: Изгледа главно како рекурзивен лавиринт за назад, но со повремени гранки кои ги кршат долгите коридори.
• 50% најнов, 50% најстар: Балансира долги коридори со грмушки раст.