Wilsono algoritmo labirinto generatorius

Wilsono algoritmas yra ciklų ištrinimu pagrįstas atsitiktinio klaidžiojimo metodas, kuris generuoja vienodus besidriekiančius medžius labirintų kūrimui. Tai reiškia, kad visi galimi tam tikro dydžio labirintai turi vienodą tikimybę būti sugeneruoti, todėl tai yra nešališkas labirintų generavimo metodas. Wilsono algoritmą galima laikyti patobulinta Aldouso-Broderio algoritmo versija, nes jis generuoja labirintus su identiškomis charakteristikomis, bet veikia daug greičiau, todėl čia nesivarginau įgyvendinti Aldouso-Broderio algoritmo.

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ų.

Apie Wilsono algoritmą

Wilsono algoritmą vienodiems besidriekiantiems medžiams generuoti naudojant kilpomis ištrintą atsitiktinę sieną sukūrė Davidas Bruce'as Wilsonas.

Wilsonas šį algoritmą pirmą kartą pristatė 1996 m., tyrinėdamas atsitiktinius besidriekiančius medžius ir Markovo grandines tikimybių teorijoje. Nors jo darbai daugiausia buvo skirti matematikai ir statistinei fizikai, vėliau algoritmas buvo plačiai pritaikytas labirintų generavimui dėl jo gebėjimo sukurti idealiai vienodus labirintus.

Kaip Wilsono algoritmas veikia labirinto generavimui

Wilsono algoritmas užtikrina, kad galutinis labirintas būtų visiškai sujungtas be jokių ciklų, iteratyviai iškirsdamas kelius iš neaplankytų langelių, naudodamas atsitiktinius ėjimus.

1 veiksmas: inicijavimas

• Pradėkite nuo tinklelio, užpildyto sienomis.
• Apibrėžkite visų galimų pasažo ląstelių sąrašą.

Veiksmas: pasirinkite atsitiktinę pradinę ląstelę

• Pasirinkite bet kurią atsitiktinę ląstelę ir pažymėkite ją kaip aplankytą. Tai bus labirinto pradžios taškas generavimo metu.

3 veiksmas: atsitiktinis pasivaikščiojimas su ciklo trynimu

• Pasirinkite neaplankytą ląstelę ir pradėkite atsitiktinį ėjimą (judėjimą atsitiktinėmis kryptimis).
• Jei pasivaikščiojimas pasiekia jau aplankytą langelį, ištrinkite visas kilpas kelyje.
• Kai pasivaikščiojimas susijungs su aplankyta sritimi, pažymėkite visas kelio langelius kaip aplankytas.

4 veiksmas: kartokite, kol aplankytos visos ląstelės:

• Toliau pasirinkite neaplankytas ląsteles ir atlikite atsitiktinius ėjimus, kol kiekviena ląstelė taps labirinto dalimi.

Papildoma literatūra

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

• Rekursyvus Backtracker labirinto generatorius
• Medžiok ir žudyk labirinto generatorius
• Kruskal algoritmo labirinto generatorius