Rekursyvus Backtracker labirinto generatorius

Rekursyvus atgalinio sekimo algoritmas iš tikrųjų yra bendrosios paskirties giluminė paieška. Kai naudojamas labirinto generavimui, jis šiek tiek pakeistas, kad būtų pasirinktas kelias atsitiktinai, o jei naudojamas tikrajai paieškai, paprastai kiekviename lygyje būtų ieškoma tiesine tvarka. Jis linkęs sukurti labirintus su ilgais, vingiuotais koridoriais ir labai ilgu, sukančiu sprendimu.

Tobulasis labirintas - tai labirintas, kuriame iš bet kurio labirinto taško į bet kurį kitą tašką veda lygiai vienas kelias. Tai reiškia, kad negalite eiti ratu, bet dažnai susidursite su aklavietėmis, todėl būsite priversti apsisukti ir grįžti atgal.

Čia sukurtuose labirinto žemėlapiuose yra numatytoji versija be pradžios ir pabaigos pozicijų, todėl jas galite nustatyti patys: iš bet kurio labirinto taško į bet kurį kitą tašką bus rastas sprendimas. Jei norite įkvėpimo, galite įjungti siūlomą pradžios ir pabaigos padėtį ir net pamatyti sprendimą tarp šių dviejų padėčių.

Rekursyvus atgalinio sekimo algoritmas yra pirmiausia gylio paieškos metodas, skirtas sukurti tobulus labirintus (labirintus be kilpų ir vieno kelio tarp bet kurių dviejų taškų). Tai paprasta, efektyvu ir sukuria vizualiai patrauklius labirintus su ilgais vingiuotais koridoriais.

Nepaisant pavadinimo, jis nebūtinai turi būti įgyvendintas naudojant rekursiją. Jis dažnai įgyvendinamas kartotiniu metodu, naudojant LIFO eilę (ty krūvą). Labai dideliems labirintams, naudojant rekursiją, yra didesnė tikimybė, kad skambučių krūvos perpildymas, priklausomai nuo programavimo kalbos ir turimos atminties. LIFO eilę galima lengviau pritaikyti tvarkyti didelius duomenų kiekius, net išlaikant eilę diske arba duomenų bazėje, jei laisvos atminties nepakanka.

Kaip tai veikia

Algoritmas veikia naudodamas stekeliu pagrįstą gylio paieškos metodą. Štai žingsnis po žingsnio suskirstymas:

1. Pasirinkite pradinį langelį ir pažymėkite jį kaip aplankytą.
2. Kol yra nelankytų langelių:
   • Pažvelkite į gretimas kameras, kurios dar nebuvo aplankytos.
   • Jei yra bent vienas nelankytas kaimynas:
     • Atsitiktinai pasirinkite vieną iš nelankytų kaimynų.
     • Pašalinkite sieną tarp dabartinės ląstelės ir pasirinkto kaimyno.
     • Perkelkite į pasirinktą kaimyną ir pažymėkite jį kaip aplankytą.
     • Stumkite esamą langelį į krūvą.
   • Jei nėra nelankytų kaimynų:
     • Grįžkite iškeldami paskutinį langelį iš krūvos.
3. Tęskite šį procesą, kol krūva bus tuščia.

Įdomus faktas apie šį algoritmą yra tai, kad jis veikia ir kaip labirinto generatorius, ir kaip labirintų sprendėjas. Jei paleisite jį jau sugeneruotame labirinte ir tiesiog sustosite, kai pasieksite galutinį tašką, krūvoje bus labirinto sprendimas.

Tiesą sakant, šioje svetainėje turiu dvi šio algoritmo versijas: LIFO eilę, pagrįstą labirintams šiame puslapyje generuoti, ir rekursija pagrįstą labirintų sprendimui, taip pat labirintus, sugeneruotus kitų algoritmų (taip sudaromi žemėlapiai su sprendimais). Dvi skirtingos versijos skirtos tik sportui, nes aš esu vėpla, kuriai tai įdomu, bet kuris galėjo tikti abiem ;-)