Рекурсивен генератор на лабиринт за обратно проследяване

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

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

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

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

Въпреки името си, не е задължително да се реализира чрез рекурсия. Често се реализира чрез итеративен подход, използващ LIFO опашка (т.е. стек). За много големи лабиринти, използването на рекурсия е по-вероятно да доведе до препълване на стека от повиквания, в зависимост от езика за програмиране и наличната памет. LIFO опашката може по-лесно да се адаптира за обработка на големи количества данни, дори да се запази опашката на диск или в база данни, ако наличната памет е недостатъчна.

Как работи

Алгоритъмът работи, използвайки подход за търсене в дълбочина, базиран на стек. Ето подробно описание:

1. Изберете начална клетка и я маркирайте като посетена.
2. Докато има непосетени клетки: Разгледайте съседните клетки, които все още не са посетени. Ако съществува поне един непосетен съсед: Изберете произволно един от непосетените съседи. Премахнете стената между текущата клетка и избрания съсед. Преместете се до избрания съсед и го маркирайте като посетен. Преместете текущата клетка в стека. Ако няма непосетени съседи: Върнете се назад, като извадите последната клетка от стека.
3. Продължете този процес, докато стекът се изпразни.

Интересен факт за този алгоритъм е, че той работи както като генератор на лабиринти, така и като решавач на лабиринти. Ако го стартирате върху вече генериран лабиринт и просто спрете, когато достигнете определената крайна точка, стекът ще съдържа решението на лабиринта.

Всъщност имам две версии на този алгоритъм, които се използват на този сайт: базирана на LIFO опашка за генериране на лабиринти на тази страница и базирана на рекурсия за решаване на лабиринти, както и лабиринти, генерирани от други алгоритми (така се правят картите с решенията). Наличието на две различни версии е просто за спорт, защото съм зубър, който го намира за интересно, всяка от тях би могла да работи и за двете ;-)

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

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

• Генератор на лабиринт за алгоритъм за отглеждане на дървета
• Генератор на лабиринт за лов и убиване
• Генератор на лабиринти с алгоритъм на Eller