Generator Labirinta Lov in Ubij
Objavljeno: 16. februar 2025 ob 8:57:10 pop. UTC
Generator labirintov z uporabo algoritma Hunt and Kill za ustvarjanje popolnega labirinta. Ta algoritem je podoben recursive Backtrackerju, vendar se nagiba k ustvarjanju labirintov z nekoliko manj dolgimi vijugastimi koridorji.Hunt and Kill Maze Generator
Algoritem Hunt and Kill je v resnici spremenjena različica Recursive Backtrackerja. Sprememba je sestavljena iz sistematičnega skeniranja (ali "lova") za novo celico, od katere bi nadaljevali, ko ne more iti dlje, v nasprotju s pravim rekurzivnim iskanjem, ki se vedno vrne na prejšnjo celico v skladu.
Zaradi tega je mogoče ta algoritem zlahka prilagoditi za ustvarjanje labirintov z drugačnim videzom in občutkom, samo tako, da se pogosteje odločite za vstop v način "lov" ali v skladu s posebnimi pravili. Različica, ki je implementirana tukaj, vstopi v način "lov" le, ko ne more iti dlje od trenutne celice.
Popoln labirint je labirint, v katerem obstaja natanko ena pot od katere koli točke v labirintu do katere koli druge točke. To pomeni, da se ne morete vrteti v krogu, vendar boste pogosto naleteli na slepe ulice, zaradi česar se boste morali obrniti in vrniti nazaj.
Tukaj ustvarjeni zemljevidi labirintov vključujejo privzeto različico brez začetnih in končnih položajev, tako da jih lahko določite sami: iz katere koli točke v labirintu do katere koli druge točke obstaja rešitev. Če želite navdih, lahko omogočite predlagana začetni in končni položaj - in si celo ogledate rešitev med njima.
O algoritmu Hunt and Kill
Algoritem Hunt and Kill je preprosta, a učinkovita metoda za ustvarjanje labirintov. Nekako je podoben iskanju najprej v globino (tj. algoritmu Recursive Backtracker), razen kadar ne more iti dlje od trenutnega položaja, sistematično skenira (ali "lovi") labirint, da bi našel novo celico, iz katere bi nadaljeval. Algoritem je sestavljen iz dveh glavnih faz: hoje in lova.
Kako deluje algoritem lov in ubijanje za ustvarjanje labirintov
1. korak: Začnite pri naključni celici
- Poiščite naključno celico v mreži in jo označite kot obiskano.
2. korak: Faza hoje (naključna hoja)
- Izberite naključnega neobiskanega soseda.
- Premaknite se do tega soseda, ga označite kot obiskanega in naredite pot med prejšnjo in novo celico.
- Ponavljajte, dokler ne ostane nobenih neobiskanih sosedov.
3. korak: Faza lova (sledenje nazaj prek skeniranja)
- Preglejte mrežo vrstico za vrstico (ali stolpec za stolpcem).
- Poiščite prvo neobiskano celico, ki ima vsaj enega obiskanega soseda.
- Povežite to celico z obiskanim sosedom, da nadaljujete s fazo hoje.
- Ponavljajte, dokler niso obiskane vse celice.