Miklix

Generator labirinta za lov i ubijanje

Objavljeno: 16. februar 2025. u 21:00:13 UTC

Generator labirinta koji koristi algoritam Hunt and Kill za stvaranje savršenog labirinta. Ovaj algoritam je sličan Rekurzivnom Backtrackeru, ali ima tendenciju da generiše labirinte sa nešto manje dugim, krivudavim hodnicima.

Ova stranica je mašinski prevedena sa engleskog kako bi bila dostupna što većem broju ljudi. Nažalost, mašinsko prevođenje još nije usavršena tehnologija, pa može doći do grešaka. Ako želite, možete pogledati originalnu englesku verziju ovdje:

Hunt and Kill Maze Generator

Algoritam Hunt and Kill je zapravo modificirana verzija Rekurzivnog Backtrackera. Modifikacija se sastoji od sistematskog skeniranja (ili "lova") za novu ćeliju koja će nastaviti kada ne može ići dalje, za razliku od istinske rekurzivne pretrage, koja će se uvijek vraćati na prethodnu ćeliju na steku.

Zbog toga, ovaj algoritam se može lako prilagoditi za generisanje labirinta sa drugačijim izgledom i osjećajem, samo odabirom da se uđe u "lov" mod češće ili prema određenim pravilima. Verzija implementirana ovdje ulazi u "lovni" mod samo kada ne može ići dalje od trenutne ćelije.

Savršen labirint je labirint u kojem postoji tačno jedan put od bilo koje tačke u labirintu do bilo koje druge tačke. To znači da ne možete završiti u krugu, ali ćete često nailaziti na slijepe ulice, prisiljavajući vas da se okrenete i vratite.

Mape lavirinta koje se ovdje generiraju uključuju zadanu verziju bez ikakvih početnih i završnih pozicija, tako da ih možete sami odlučiti: postojat će rješenje od bilo koje točke u lavirintu do bilo koje druge točke. Ako želite inspiraciju, možete omogućiti predloženi početni i ciljni položaj - pa čak i vidjeti rješenje između njih.


Stvorite novi labirint








O algoritmu lova i ubijanja

Algoritam Hunt and Kill je jednostavan, ali efikasan metod za generisanje labirinta. Donekle je sličan pretraživanju dubine (tj. algoritmu Recursive Backtracker), osim kada ne može ići dalje od trenutne pozicije, sistematski skenira (ili "lovi") preko labirinta kako bi pronašao novu ćeliju iz koje će krenuti. Algoritam se sastoji od dvije glavne faze: hodanje i lov.

Kako algoritam za lov i ubijanje radi za stvaranje labirinta

Korak 1: Počnite od slučajne ćelije

  • Nađi nasumičnu ćeliju u mreži i označi je kao posjećenu.

Korak 2: Faza hodanja (nasumični hod)

  • Izaberi nasumičnog neposjećenog susjeda.
  • Pomaknite se do tog susjeda, označite ga kao posjećenog i izrežite put između prethodne i nove ćelije.
  • Ponavljajte sve dok ne ostane neposjećenih susjeda.

Korak 3: Faza lova (vraćanje putem skeniranja)

  • Skenirajte mrežu red po red (ili kolonu po kolonu).
  • Pronađi prvu neposjećenu ćeliju koja ima barem jednog posjećenog susjeda.
  • Povežite tu ćeliju sa posjećenim susjedom kako biste nastavili fazu hodanja.
  • Ponavljajte dok se ne posjete sve ćelije.

Podijelite na BlueskyPodijelite na FacebookuPodijelite na LinkedIn-uPodijelite na Tumblr-uPodijeli na XPodijelite na LinkedIn-uPrikači na Pinterest

Mikkel Bang Christensen

O autoru

Mikkel Bang Christensen
Mikkel je kreator i vlasnik miklix.com. Ima preko 20 godina iskustva kao profesionalni kompjuterski programer/programer softvera i trenutno je zaposlen sa punim radnim vremenom u velikoj evropskoj IT korporaciji. Kada ne piše blog, svoje slobodno vrijeme provodi na širokom spektru interesovanja, hobija i aktivnosti, što se u određenoj mjeri može odraziti na različite teme koje se obrađuju na ovoj web stranici.