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

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

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

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

За алгоритмот за растење на дрво

Алгоритмот „Растечко дрво“ е флексибилен и моќен метод за генерирање совршени лавиринти. Алгоритмот е интересен бидејќи може да го емулира однесувањето на неколку други алгоритми за генерирање лавиринти, како што се Примовиот алгоритам, рекурзивното враќање назад и рекурзивното делење, во зависност од тоа како ќе ја изберете следната ќелија за обработка.

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

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

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

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

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

Чекор 3: Прекинување

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

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

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

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

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

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

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

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

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

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

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

• 90% најново, 10% случајно: Изгледа претежно како рекурзивен лавиринт за враќање назад, но со повремени гранки што прекинуваат долги ходници.
• 50% најнови, 50% најстари: Ги балансира долгите коридори со грмушест раст.

Дополнително читање

Ако ви се допадна овој пост, можеби ќе ви се допаднат и овие предлози:

• Лови и убиј генератор на лавиринт
• Вилсоновиот алгоритам генератор на лавиринт
• Генератор на лавиринт на алгоритам на Елер