Rekursyvus Backtracker labirinto generatorius

Rekursinis atgalinio sekimo algoritmas iš tiesų yra bendrosios paskirties paieška gylyje. Kai naudojamas labirintui generuoti, jis yra šiek tiek modifikuotas, kad kelias būtų pasirinktas atsitiktinai, o jei naudojamas faktinės paieškos tikslais, paprastai kiekviename lygyje būtų ieškoma tiesine tvarka. Jis paprastai sukuria labirintus su ilgais, vingiuotais koridoriais ir labai ilgu, vingiuotu 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ų.

Rekursinis atgalinio sekimo algoritmas yra gylio paieškos metodas, skirtas tobuliems labirintams (labirintams be kilpų ir vienam keliui tarp bet kurių dviejų taškų) generuoti. Jis yra paprastas, efektyvus ir sukuria vizualiai patrauklius labirintus su ilgais, vingiuotais koridoriais.

Nepaisant pavadinimo, jis nebūtinai turi būti įgyvendinamas naudojant rekursiją. Jis dažnai įgyvendinamas iteraciniu metodu, naudojant LIFO eilę (t. y. steko struktūrą). Labai dideliems labirintams, naudojant rekursiją, yra didesnė tikimybė, kad iškvietimų stekas bus perpildytas, priklausomai nuo programavimo kalbos ir laisvos atminties. LIFO eilę galima lengviau pritaikyti dideliems duomenų kiekiams tvarkyti, netgi išlaikant eilę diske arba duomenų bazėje, jei nepakanka laisvos atminties.

Kaip tai veikia

Algoritmas veikia naudodamas steku pagrįstą giluminės paieškos metodą. Štai nuoseklus aprašymas:

1. Pasirinkite pradinę ląstelę ir pažymėkite ją kaip aplankytą.
2. Kol yra neaplankytų langelių: pažiūrėkite į kaimynines langelius, kurie dar nebuvo aplankyti. Jei yra bent vienas neaplankytas kaimynas: atsitiktinai pasirinkite vieną iš neaplankytų kaimynų. pašalinkite sieną tarp dabartinės ir pasirinktos langelių. pereikite prie pasirinktos kaimyninės vietos ir pažymėkite ją kaip aplankytą. įstumkite dabartinę langelį į krūvą. Jei neaplankytų kaimynų nėra: grįžkite atgal, išimdami paskutinę langelį iš krūvos.
3. Tęskite šį procesą, kol krūva bus tuščia.

Įdomus šio algoritmo faktas yra tai, kad jis veikia ir kaip labirinto generatorius, ir kaip labirinto sprendėjas. Jei jį paleisite jau sugeneruotame labirinte ir tiesiog sustabdysite, kai pasieksite nustatytą galinį tašką, steke bus labirinto sprendimas.

Šioje svetainėje iš tikrųjų turiu dvi šio algoritmo versijas: LIFO eile pagrįstą, skirtą labirintų generavimui šiame puslapyje, ir rekursinę, skirtą labirintų sprendimui, taip pat labirintų, generuojamų kitų algoritmų (taip sudaromi žemėlapiai su sprendimais). Dvi skirtingos versijos skirtos tik sportui, nes esu mėgėjas, kuriam tai įdomu, bet kuri galėjo tikti abiem ;-)

Papildoma literatūra

Jei jums patiko šis įrašas, jums taip pat gali patikti šie pasiūlymai:

• Medžiok ir žudyk labirinto generatorius
• Wilsono algoritmo labirinto generatorius
• Ellerio algoritmo labirinto generatorius