Lov i ubijte lavirint generator
Objavio: 19. mart 2025. 20:44:41 UTC
Generator lavirinta koji koristi algoritam Hunt and Kill da stvori savršen lavirint. Ovaj algoritam je sličan Rekurzivnom Backtracker-u, ali ima tendenciju da generiše lavirinte sa nešto manje dugim, krivudavim koridorima.Hunt and Kill Maze Generator
Algoritam Hunt and Kill je zaista modifikovana verzija Rekurzivnog Backtracker-a. Modifikacija se sastoji od sistematskog skeniranja (ili "lova") za novu ćeliju koja će se nastaviti od kada ne može ići dalje, za razliku od istinske rekurzivne pretrage, koja će se uvek vratiti na prethodnu ćeliju na steku.
Zbog toga, ovaj algoritam se lako može prilagoditi za generisanje lavirinta sa različitim izgledom i osećajem, samo odabirom da uđete u režim "lova" češće ili prema određenim pravilima. Verzija koja je ovde implementirana ulazi u režim "lova" samo kada ne može ići dalje od trenutne ćelije.
Savršen lavirint je lavirint u kojem postoji tačno jedan put od bilo koje tačke u lavirintu do bilo koje druge tačke. To znači da ne možete završiti u krugovima, ali ćete često naići na ćorsokak, prisiljavajući vas da se okrenete i vratite.
Mape lavirinta generisane ovde uključuju podrazumevanu verziju bez ikakvih početnih i završnih pozicija, tako da možete sami da odlučite o njima: biće rešenje od bilo koje tačke u lavirintu do bilo koje druge tačke. Ako želite inspiraciju, možete da omogućite predloženu početnu i završnu poziciju - pa čak i da vidite rešenje između ova dva.
O algoritmu Lov i Ubistvo
Algoritam Lov i Ubistvo je jednostavna, ali efikasna metoda za generisanje lavirinta. Pomalo je sličan algoritmu pretrage u dubinu (tj. algoritmu Rekurzivnog Povratka), osim što, kada ne može da ide dalje od trenutne pozicije, sistematski skenira (ili "lova") lavirint kako bi pronašao novu ćeliju sa koje će nastaviti. Algoritam se sastoji od dve glavne faze: hodanje i lov.
Kako algoritam Lov i Ubistvo funkcioniše za generisanje lavirinata
Korak 1: Početak na slučajnoj ćeliji
- Pronađite slučajnu ćeliju u mreži i označite je kao posećenu.
Korak 2: Faza hodanja (Slučajna šetnja)
- Izaberite slučajnog neposećenog suseda.
- Premestite se na tog suseda, označite ga kao posećenog i izrežite put između prethodne i nove ćelije.
- Ponovite dok ne ostanu nijedni neposećeni susedi.
Korak 3: Faza lova (Povratak putem skeniranja)
- Skenirajte mrežu red po red (ili kolonu po kolonu).
- Pronađite prvu neposećenu ćeliju koja ima barem jednog posećenog suseda.
- Povežite tu ćeliju sa posećenim susedom da biste nastavili fazu hodanja.
- Ponovite dok sve ćelije ne budu posećene.