Лови и убиј генератор на лавиринт

Алгоритмот „Hunt and Kill“ е всушност модифицирана верзија на Recursive Backtracker. Модификацијата се состои во систематско скенирање (или „барање“) на нова ќелија за да продолжи од кога не може да оди понатаму, за разлика од вистинското рекурзивно пребарување, кое секогаш ќе се враќа на претходната ќелија на стекот.

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

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

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

За алгоритмот „Лов и убиј“

Алгоритмот „Лов и убиј“ е едноставен, но ефикасен метод за генерирање лавиринти. Тој е донекаде сличен на пребарувањето „прво во длабочина“ (т.е. алгоритмот „Рекурзивен вратен тракер“), освен кога не може да оди подалеку од тековната позиција, тој систематски скенира (или „лови“) низ лавиринтот за да пронајде нова ќелија од која ќе продолжи. Алгоритмот се состои од две главни фази: одење и лов.

Како функционира алгоритмот „Лов и убиј“ за генерирање лавиринт

Чекор 1: Започнете од случајна ќелија

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

Чекор 2: Фаза на одење (случајно одење)

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

Чекор 3: Фаза на лов (Враќање назад преку скенирање)

• Скенирајте ја мрежата ред по ред (или колона по колона).
• Пронајдете ја првата непосетена ќелија што има барем еден посетен сосед.
• Поврзете ја таа ќелија со посетен сосед за да ја продолжите фазата на одење.
• Повторете додека не се посетат сите ќелии.

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

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

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