Miklix
Prva stran / Blodnjaki / Generatorji labirintov / Generator Labirinta Lov in Ubij

Generator Labirinta Lov in Ubij

Objavljeno: 16. februar 2025 ob 8:57:10 pop. UTC
Nazadnje posodobljeno: 12. januar 2026 ob 9:05:05 dop. UTC

Generator labirintov z algoritmom Hunt and Kill za ustvarjanje popolnega labirinta. Ta algoritem je podoben rekurzivnemu Backtrackerju, vendar ponavadi ustvarja labirinte z nekoliko krajšimi, vijugastimi hodniki.

Ta stran je bila strojno prevedena iz angleščine, da bi bila dostopna čim večjemu številu ljudi. Žal strojno prevajanje še ni popolna tehnologija, zato lahko pride do napak. Če želite, si lahko izvirno angleško različico ogledate tukaj:

Hunt and Kill Maze Generator

Algoritem Hunt and Kill je v resnici spremenjena različica rekurzivnega sledenja nazaj. Sprememba je sestavljena iz sistematičnega skeniranja (ali "lova") za novo celico, od koder se nadaljuje, ko ne more več iti naprej, v nasprotju s pravim rekurzivnim iskanjem, ki se vedno vrne na prejšnjo celico na skladu.

Zaradi tega je mogoče ta algoritem enostavno prilagoditi za ustvarjanje labirintov z različnim videzom in občutkom, preprosto tako, da se pogosteje ali v skladu z določenimi pravili preklopi v način "lova". Različica, ki je implementirana tukaj, preklopi v način "lova" 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.


Ustvarjanje novega labirinta








O algoritmu lova in ubijanja

Algoritem Hunt and Kill je preprosta, a učinkovita metoda za ustvarjanje labirintov. Nekoliko je podoben iskanju v globino (tj. algoritmu Rekurzivnega sledenja nazaj), le da ko ne more iti dlje od trenutnega položaja, sistematično skenira (ali "lovi") labirint, da bi našel novo celico, iz katere lahko nadaljuje. Algoritem je sestavljen iz dveh glavnih faz: hoje in lova.

Kako deluje algoritem lova in ubijanja za ustvarjanje labirinta

1. korak: Začnite v naključni celici

  • V mreži poiščite naključno celico in jo označite kot obiskano.

2. korak: Faza hoje (naključna hoja)

  • Izberite naključnega neobiskanega soseda.
  • Premaknite se do sosednje celice, jo označite kot obiskano in začrtajte pot med prejšnjo in novo celico.
  • Ponavljajte, dokler ne ostane nobenega neobiskanega soseda.

3. korak: Faza lova (povratno sledenje s skeniranjem)

  • Skenirajte 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 fazo hoje.
  • Ponavljajte, dokler niso obiskane vse celice.

Nadaljnje branje

Če vam je bila ta objava všeč, vam bodo morda všeč tudi ti predlogi:


Delite na BlueskyDelite na FacebookuDelite na LinkedInuDelite na TumblrDelite na XDelite na LinkedInuPripni na Pinterest

Mikkel Christensen

O avtorju

Mikkel Christensen
Mikkel je avtor in lastnik spletne strani miklix.com. Ima več kot 20 let izkušenj kot profesionalni računalniški programer/razvijalec programske opreme in je trenutno za polni delovni čas zaposlen v veliki evropski IT korporaciji. Kadar ne piše bloga, svoj prosti čas posveča številnim interesom, hobijem in dejavnostim, kar se do neke mere odraža v raznolikosti tem na tem spletnem mestu.