Medžiok ir žudyk labirinto generatorius
Paskelbta: 2025 m. vasario 16 d. 20:54:43 UTC
Labirinto generatorius, naudojant „Hunt and Kill“ algoritmą, kad sukurtų tobulą labirintą. Šis algoritmas yra panašus į Recursive Backtracker, bet yra linkęs generuoti labirintus su šiek tiek trumpesniais, vingiuotais koridoriais.Hunt and Kill Maze Generator
„Hunt and Kill“ algoritmas iš tikrųjų yra modifikuota „Recursive Backtracker“ versija. Modifikacija susideda iš sistemingo naujo langelio nuskaitymo (arba „medžiojimo“), kad būtų galima tęsti nuo tada, kai jis negali eiti toliau, o ne tikra rekursinė paieška, kuri visada grįš į ankstesnę dėklo langelį.
Dėl šios priežasties šis algoritmas gali būti lengvai pritaikytas generuoti skirtingos išvaizdos labirintus, tiesiog pasirenkant dažniau įjungti „medžioklės“ režimą arba pagal konkrečias taisykles. Čia įdiegta versija įjungia „medžioklės“ režimą tik tada, kai negali eiti toliau nuo dabartinio langelio.
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 medžioklės ir žudymo algoritmą
„Hunt and Kill“ algoritmas yra paprastas, bet efektyvus būdas sukurti labirintus. Tai šiek tiek panaši į paiešką pagal gylį (ty Rekursyvaus atgalinio sekimo algoritmą), išskyrus atvejus, kai negali eiti toliau nuo dabartinės padėties, sistemingai nuskaito (arba „medžioja“) labirintą, kad surastų naują langelį, iš kurio būtų galima tęsti. Algoritmą sudaro dvi pagrindinės fazės: ėjimas ir medžioklė.
Kaip medžioklės ir žudymo algoritmas veikia labirinto generavimui
1 veiksmas: pradėkite nuo atsitiktinės ląstelės
- Raskite atsitiktinį langelį tinklelyje ir pažymėkite jį kaip aplankytą.
2 veiksmas: ėjimo fazė (atsitiktinis ėjimas)
- Pasirinkite atsitiktinį nelankymą kaimyną.
- Pereikite prie to kaimyno, pažymėkite jį kaip aplankytą ir nubrėžkite kelią tarp ankstesnės ir naujos ląstelės.
- Kartokite tol, kol neliks neaplankytų kaimynų.
3 veiksmas: medžioklės etapas (atgalinis sekimas nuskaitant)
- Nuskaitykite tinklelį eilutę po eilutės (arba stulpelio po stulpelio).
- Raskite pirmą nelankytą langelį, kuriame yra bent vienas aplankytas kaimynas.
- Prijunkite tą langelį prie aplankyto kaimyno, kad atnaujintumėte vaikščiojimo fazę.
- Kartokite tol, kol bus aplankytos visos ląstelės.