Generator Labirinta Lov i Ubijanje
Objavljeno: 16. veljače 2025. u 21:01:12 UTC
Generator labirinta koji koristi algoritam Hunt and Kill za stvaranje savršenog labirinta. Ovaj je algoritam sličan Recursive Backtrackeru, ali nastoji generirati labirinte s nešto kraćim, vijugavim hodnicima.Hunt and Kill Maze Generator
Algoritam Hunt and Kill zapravo je modificirana verzija Recursive Backtrackera. Modifikacija se sastoji od sustavnog skeniranja (ili "lova") za novom ćelijom od koje se nastavlja kada ne može ići dalje, za razliku od pravog rekurzivnog pretraživanja, koje će se uvijek vratiti na prethodnu ćeliju na stogu.
Zbog toga se ovaj algoritam može lako prilagoditi za generiranje labirinta s različitim izgledom i osjećajem, samo češćim odabirom ulaska u način "lova" ili prema određenim pravilima. Ovdje implementirana verzija ulazi samo u "lov" način kada ne može ići dalje od trenutne ćelije.
Savršen labirint je labirint u kojem postoji točno jedan put od bilo koje točke u labirintu do bilo koje druge točke. To znači da se ne možete vrtjeti u krug, ali ćete često naići na slijepe ulice, zbog čega ćete se morati okrenuti i vratiti.
Ovdje generirane karte labirinta 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 labirintu do bilo koje druge točke. Ako želite inspiraciju, možete omogućiti predloženu početnu i ciljnu poziciju - pa čak i vidjeti rješenje između ta dva.
O algoritmu lov i ubij
Algoritam Hunt and Kill jednostavna je, ali učinkovita metoda za stvaranje labirinta. Donekle je sličan pretrazi u dubinu (tj. algoritmu Recursive Backtracker), osim kada ne može ići dalje od trenutne pozicije, sustavno skenira (ili "lovi") labirint kako bi pronašao novu ćeliju iz koje bi mogao nastaviti. Algoritam se sastoji od dvije glavne faze: hodanja i lova.
Kako algoritam lov i ubij radi za Maze Generation
Korak 1: Počnite od nasumične ćelije
- Pronađite slučajnu ćeliju u mreži i označite je kao posjećenu.
Korak 2: Faza hodanja (nasumično hodanje)
- Odaberite nasumično neposjećenog susjeda.
- Pomaknite se do tog susjeda, označite ga kao posjećenog i iscrtajte put između prethodne i nove ćelije.
- Ponavljajte sve dok ne ostanu neposjećeni susjedi.
Korak 3: Faza traženja (povratak putem skeniranja)
- Skenirajte mrežu red po red (ili stupac po stupac).
- Pronađite prvu neposjećenu ćeliju koja ima barem jednog posjećenog susjeda.
- Povežite tu ćeliju s posjećenim susjedom kako biste nastavili fazu hodanja.
- Ponavljajte dok se ne posjete sve ćelije.