Rekurzivno Backtracker lavirint generator

Rekurzivni backtracker algoritam je zaista opšte namene dubina pretraga. Kada se koristi za generisanje lavirinta, to je malo modifikovan da izabere put nasumično, dok ako se koristi za stvarne svrhe pretraživanja, obično bi samo pretraživati svaki nivo u linearnom redosledu. Ima tendenciju da proizvede lavirinte sa dugim, krivudavim hodnicima i veoma dugim, uvijanim rešenjem.

Savršen lavirint je lavirint u kojem postoji tačno jedan put od bilo koje tačke u lavirintu do bilo koje druge tačke. To znači da ne možete završiti u krugovima, ali ćete često naići na ćorsokak, prisiljavajući vas da se okrenete i vratite.

Mape lavirinta generisane ovde uključuju podrazumevanu verziju bez ikakvih početnih i završnih pozicija, tako da možete sami da odlučite o njima: biće rešenje od bilo koje tačke u lavirintu do bilo koje druge tačke. Ako želite inspiraciju, možete da omogućite predloženu početnu i završnu poziciju - pa čak i da vidite rešenje između ova dva.

Rekurzivni algoritam za vraćanje je metoda pretrage u dubinu za generisanje savršenih lavirinta (lavirinti bez petlji i sa jedinstvenim putem između svaka dva mesta). On je jednostavan, efikasan i proizvodi vizuelno privlačne lavirinte sa dugim, vijugavim hodnicima.

Bez obzira na ime, ne mora nužno biti implementiran korišćenjem rekurzije. Često se implementira iterativnim pristupom korišćenjem LIFO reda (tj. steka). Za veoma velike lavirinte, korišćenje rekurzije je verovatnije da će dovesti do prepunjenja steka poziva, u zavisnosti od programskog jezika i dostupne memorije. LIFO red se lakše može prilagoditi za rukovanje velikim količinama podataka, čak i držanjem reda na disku ili u bazi podataka ako dostupna memorija nije dovoljna.

Kako funkcioniše

Algoritam funkcioniše korišćenjem pristupa pretrage u dubinu zasnovanog na steku. Evo kako to funkcioniše, korak po korak:

1. Izaberite početnu ćeliju i označite je kao posetu.
2. Dok postoje nepregledane ćelije:
   • Pogledajte susedne ćelije koje još nisu bile pregledane.
   • Ako postoji bar jedan nepregledani sused:
     • Nasumično izaberite jednog od nepregledanih suseda.
     • Uklonite zid između trenutne ćelije i izabranog suseda.
     • Pređite na izabranog suseda i označite ga kao posetu.
     • Stavite trenutnu ćeliju na stek.
   • Ako ne postoji nepregledani sused:
     • Vratite se unazad uklanjanjem poslednje ćelije sa steka.
3. Nastavite ovaj proces dok stek ne bude prazan.

Zanimljivost u vezi ovog algoritma je da on funkcioniše i kao generator lavirinata i kao rešavač lavirinata. Ako ga pokrenete na već generisanom lavirintu i samo stanete kada dostignete odlučenu tačku na kraju, stek će sadržati rešenje lavirinta.

Zapravo imam dve verzije ovog algoritma na ovom sajtu: jednu zasnovanu na LIFO redu za generisanje lavirinata na ovoj stranici i jednu zasnovanu na rekurziji za rešavanje lavirinata, takođe lavirinata generisanih drugim algoritmima (tako se prave mape sa rešenjima). Imati dve različite verzije je samo zbog zabave, jer sam nerd koji smatra da je to interesantno, bilo koja od njih bi mogla da radi za obe ;-)