Wilsono algoritmo labirinto generatorius
Paskelbta: 2025 m. vasario 16 d. 19:32:22 UTC
Labirinto generatorius, naudojant Wilsono algoritmą tobulam labirintui sukurti. Šis algoritmas sugeneruoja visus galimus tam tikro dydžio labirintus su ta pačia tikimybe, todėl teoriškai jis gali generuoti daugelio mišrių išdėstymų labirintus, tačiau kadangi yra daugiau galimų labirintų su trumpesniais koridoriais nei ilgesniais, juos pamatysite dažniau.Wilson's Algorithm Maze Generator
Wilsono algoritmas yra ištrintas atsitiktinio ėjimo metodas, kuris sukuria vienodus besitęsiančius medžius labirintui kurti. Tai reiškia, kad visi galimi tam tikro dydžio labirintai gali būti sukurti vienodai, todėl tai yra nešališka labirinto generavimo technika. Wilsono algoritmą galima laikyti patobulinta Aldous-Broderio algoritmo versija, nes jis generuoja identiškų charakteristikų labirintus, tačiau veikia daug greičiau, todėl Aldous-Broderio algoritmo čia nesivarginau diegti.
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ą, skirtą sukurti vienodus besitęsiančius medžius naudojant kilpos ištrintą atsitiktinę sieną, sukūrė Davidas Bruce'as Wilsonas.
Wilsonas iš pradžių pristatė šį algoritmą 1996 m., tyrinėdamas atsitiktinai besitęsiančius medžius ir Markovo grandines tikimybių teorijoje. Nors jo darbas daugiausia buvo matematikos ir statistinės fizikos srityse, nuo to laiko algoritmas buvo plačiai pritaikytas labirintų generavimui, nes jis gali sukurti visiškai vienodus labirintus.
Kaip Wilsono algoritmas veikia labirinto generavimui
Wilsono algoritmas užtikrina, kad galutinis labirintas būtų visiškai sujungtas be jokių kilpų, kartotiškai iškirpdamas kelius iš neaplankytų langelių atsitiktiniais pasivaikščiojimais.
1 veiksmas: inicijuokite
- Pradėkite nuo tinklelio, užpildyto sienomis.
- Apibrėžkite visų galimų perėjimo langelių sąrašą.
2 veiksmas: pasirinkite atsitiktinę pradžios langelį
- Pasirinkite bet kurį atsitiktinį langelį ir pažymėkite jį kaip aplankytą. Tai yra labirinto pradžios taškas kartos metu.
3 veiksmas: atsitiktinis ėjimas su kilpos trynimu
- Pasirinkite nelankytą langelį ir pradėkite atsitiktinį pasivaikščiojimą (judėdami atsitiktinėmis kryptimis).
- Jei ėjimas pasiekia jau aplankytą langelį, ištrinkite visas kelio kilpas.
- Kai pasivaikščiojimas susijungs su aplankytu regionu, pažymėkite visus kelio langelius kaip aplankytus.
4 veiksmas: kartokite, kol aplankysite visas ląsteles :
- Tęskite nelankytų langelių pasirinkimą ir atsitiktinius pasivaikščiojimus, kol kiekviena ląstelė taps labirinto dalimi.