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.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.
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.