Лови и убиј генератор на лавиринт
Објавено: 5 март 2025, во 19:51:26 UTC
Генератор на лавиринт кој го користи алгоритмот Hunt and Kill за да создаде совршен лавиринт. Овој алгоритам е сличен на Recursive Backtracker, но има тенденција да генерира лавиринти со нешто помалку долги, кривулести коридори.Hunt and Kill Maze Generator
Алгоритмот Hunt and Kill е навистина изменета верзија на Recursive Backtracker. Модификацијата се состои од систематско скенирање (или „лов“) за нова ќелија да продолжи од кога не може да оди понатаму, за разлика од вистинското рекурзивно пребарување, кое секогаш ќе се враќа во претходната ќелија на оџакот.
Поради ова, овој алгоритам лесно може да се прилагоди за да генерира лавиринти со различен изглед и чувство, само со избирање почесто да влегувате во режим на „лов“ или според специфични правила. Верзијата имплементирана овде влегува во режим на „лов“ само кога не може да оди подалеку од тековната ќелија.
Совршен лавиринт е лавиринт во кој има точно една патека од која било точка во лавиринтот до која било друга точка. Тоа значи дека не можете да завршите да одите наоколу во кругови, но често ќе наидете на ќорсокак, што ќе ве принуди да се свртите и да се вратите назад.
Мапите на лавиринтот генерирани овде вклучуваат стандардна верзија без никакви позиции за почеток и крај, така што можете сами да ги решите тие: ќе има решение од која било точка во лавиринтот до која било друга точка. Ако сакате инспирација, можете да овозможите предложена почетна и завршна позиција - па дури и да го видите решението помеѓу двете.
За алгоритмот Хант и убиј
Алгоритмот Hunt and Kill е едноставен, но ефикасен метод за генерирање на лавиринти. Тоа е нешто слично на пребарувањето по длабочина (т.е. алгоритам Recursive Backtracker), освен кога не може да оди подалеку од моменталната позиција, систематски скенира (или „лови“) над лавиринтот за да најде нова ќелија од која ќе продолжи. Алгоритмот се состои од две главни фази: одење и лов.
Како функционира алгоритмот „Лов и убиј“ за генерацијата на лавиринтот
Чекор 1: Започнете во случајна ќелија
- Најдете случајна ќелија во мрежата и означете ја како посетена.
Чекор 2: Фаза на одење (случајно одење)
- Изберете случаен непосетен сосед.
- Одете кај тој сосед, означете го како посетен и издлабете патека помеѓу претходната и новата ќелија.
- Повторете додека не останат непосетени соседи.
Чекор 3: Фаза на лов (назад преку скенирање)
- Скенирајте ја решетката ред по ред (или колона по колона).
- Најдете ја првата непосетена ќелија која има барем еден посетен сосед.
- Поврзете ја таа ќелија со посетениот сосед за да продолжите со фазата на одење.
- Повторете додека не се посетат сите ќелии.