Miklix

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

Публикувано: 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: Фаза на лов (връщане назад чрез сканиране)

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

Споделете в BlueskyСподелете във FacebookСподелете в LinkedInСподелете в TumblrСподелете в XСподелете в LinkedInЗакачи в Пинтерест

Микел Банг Кристенсен

За автора

Микел Банг Кристенсен
Микел е създател и собственик на сайта miklix.com. Той има над 20 години опит като професионален компютърен програмист/разработчик на софтуер и в момента работи на пълен работен ден в голяма европейска ИТ корпорация. Когато не пише в блога, той прекарва свободното си време в широк спектър от интереси, хобита и дейности, които до известна степен могат да бъдат отразени в разнообразието от теми, обхванати в този уебсайт.