Генератор на лабиринт за лов и убиване
Публикувано: 16 февруари 2025 г. в 20:51:21 ч. UTC
Генератор на лабиринт, използващ алгоритъма Hunt and Kill, за да създаде перфектен лабиринт. Този алгоритъм е подобен на Recursive Backtracker, но има тенденция да генерира лабиринти с малко по-малко дълги, криволичещи коридори.Hunt and Kill Maze Generator
Алгоритъмът Hunt and Kill всъщност е модифицирана версия на Recursive Backtracker. Модификацията се състои в систематично сканиране (или "лов") за нова клетка, която да продължи, когато не може да продължи по-нататък, за разлика от истинското рекурсивно търсене, което винаги ще се връща към предишната клетка в стека.
Поради това този алгоритъм може лесно да бъде адаптиран за генериране на лабиринти с различен външен вид и усещане, само като изберете да влизате в режим "лов" по-често или според определени правила. Версията, имплементирана тук, влиза в режим "лов" само когато не може да отиде по-далеч от текущата клетка.
Перфектен лабиринт е лабиринт, в който има точно един път от всяка точка в лабиринта до всяка друга точка. Това означава, че не можете да се въртите в кръг, но често ще срещате задънени улици, което ще ви принуди да се обърнете и да се върнете обратно.
Генерираните тук карти на лабиринта включват версия по подразбиране без начални и крайни позиции, така че можете да ги определите сами: ще има решение от всяка точка в лабиринта до всяка друга точка. Ако искате да получите вдъхновение, можете да активирате предложена начална и крайна позиция - и дори да видите решението между двете.
За алгоритъма "Лов и убивай"
Алгоритъмът Hunt and Kill е прост, но ефективен метод за генериране на лабиринти. Той е донякъде подобен на търсенето в дълбочина (т.е. алгоритъма Recursive Backtracker), с изключение на това, че когато не може да отиде по-далеч от текущата позиция, той систематично сканира (или "ловува") над лабиринта, за да намери нова клетка, от която да продължи. Алгоритъмът се състои от две основни фази: ходене и лов.
Как работи алгоритъмът за лов и убиване за генериране на лабиринти
Стъпка 1: Започнете от произволна клетка
- Намерете произволна клетка в мрежата и я маркирайте като посетена.
Стъпка 2: Фаза на ходене (Random Walk)
- Изберете случаен непосетен съсед.
- Преместете се при съседа, маркирайте го като посетен и издълбайте път между предишната и новата клетка.
- Повторете, докато не останат непосетени съседи.
Стъпка 3: Фаза на лов (връщане назад чрез сканиране)
- Сканирайте мрежата ред по ред (или колона по колона).
- Намерете първата непосетена клетка, в която има поне един посетен съсед.
- Свържете тази клетка с посетен съсед, за да възобновите фазата на ходене.
- Повторете, докато всички клетки бъдат посетени.