Medžiok ir žudyk labirinto generatorius

„Medžiok ir žudyk“ algoritmas iš tiesų yra modifikuota rekursinio atgalinio sekimo versija. Modifikacija susideda iš sistemingo naujo langelio, iš kurio būtų galima tęsti paiešką, kai jis nebegali tęsti, skenavimo (arba „medžioklės“), o ne tikros rekursinės paieškos, kurios metu visada grįžtama į ankstesnį langelį steke.

Dėl šios priežasties šį algoritmą galima lengvai pritaikyti skirtingos išvaizdos ir pojūčio labirintams generuoti, tiesiog dažniau arba pagal konkrečias taisykles pasirenkant įjungti „medžioklės“ režimą. Čia įdiegta versija „medžioklės“ režimą perjungia tik tada, kai nebegalima išeiti toliau nuo dabartinės 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ą

„Medžiok ir žudyk“ algoritmas yra paprastas, bet efektyvus labirintų generavimo metodas. Jis šiek tiek panašus į paiešką gylyje (t. y. rekursinį atgalinio sekimo algoritmą), išskyrus tai, kad kai negalima eiti toliau nuo dabartinės padėties, jis sistemingai skenuoja (arba „medžioja“) labirintą, ieškodamas naujos ląstelės, iš kurios būtų galima tęsti. Algoritmas susideda iš dviejų pagrindinių etapų: ėjimo ir paieškos.

Kaip veikia medžioklės ir žudymo algoritmas labirinto generavimui

1 veiksmas: pradėkite nuo atsitiktinės ląstelės

• Tinklelyje raskite atsitiktinę langelį ir pažymėkite jį kaip aplankytą.

2 žingsnis: ėjimo fazė (atsitiktinis ėjimas)

• Pasirinkite atsitiktinį, nelankytą kaimyną.
• Pereikite prie to kaimyno, pažymėkite jį kaip aplankytą ir nubrėžkite kelią tarp ankstesnės ir naujos langelių.
• Kartokite tol, kol neliks neaplankytų kaimynų.

3 veiksmas: medžioklės etapas (atgalinis sekimas skenuojant)

• Peržiūrėkite tinklelį eilutė po eilutės (arba stulpelis po stulpelio).
• Raskite pirmąją neaplankytą ląstelę, kuri turi bent vieną aplankytą kaimyną.
• Prijunkite tą langelį prie aplankyto kaimyno, kad atnaujintumėte ėjimo fazę.
• Kartokite, kol aplankytos visos ląstelės.

Papildoma literatūra

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

• Wilsono algoritmo labirinto generatorius
• Kruskal algoritmo labirinto generatorius
• Augančio medžio algoritmo labirinto generatorius