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

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

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

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

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

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

Как работи

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

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

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

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