Генератор на лабиринт за лов и убиване

Алгоритъмът „Лов и убийство“ всъщност е модифицирана версия на рекурсивния метод за връщане назад. Модификацията се състои в систематично сканиране (или „лов“) за нова клетка, от която да се продължи, когато не може да се продължи по-нататък, за разлика от истинското рекурсивно търсене, което винаги ще се връща към предишната клетка в стека.

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

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

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

Относно алгоритъма „Лов и убийство“

Алгоритъмът „Лов и убийство“ е прост, но ефективен метод за генериране на лабиринти. Той е донякъде подобен на търсене в дълбочина (т.е. алгоритъма Recursive Backtracker), с изключение на това, че когато не може да се придвижи по-далеч от текущата позиция, той систематично сканира (или „ловува“) лабиринта, за да намери нова клетка, от която да продължи. Алгоритъмът се състои от две основни фази: ходене и търсене.

Как работи алгоритъмът „Лов и убийство“ за генериране на лабиринти

Стъпка 1: Започнете от произволна клетка

• Намерете произволна клетка в мрежата и я маркирайте като посетена.

Стъпка 2: Фаза на ходене (Случайно ходене)

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

Стъпка 3: Фаза на лов (връщане назад чрез сканиране)

• Сканирайте мрежата ред по ред (или колона по колона).
• Намерете първата непосетена клетка, която има поне един посетен съсед.
• Свържете тази клетка с посетен съсед, за да възобновите фазата на ходене.
• Повтаряйте, докато не бъдат посетени всички клетки.

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

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

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