Generator Labirinta Lov i Ubijanje

Algoritam "Lov i ubijanje" zapravo je modificirana verzija rekurzivnog algoritma "Potraga za povratnim tragom". Modifikacija se sastoji od sustavnog skeniranja (ili "lova") za novom ćelijom od koje se nastavlja od trenutka kada se više 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 labirinata s različitim izgledom i dojmom, jednostavnim odabirom češćeg ulaska u način "lova" ili prema određenim pravilima. Verzija implementirana ovdje ulazi u način "lova" samo 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 lova i ubijanja

Algoritam "Hunt and Kill" je jednostavna, ali učinkovita metoda za generiranje labirinata. Donekle je sličan pretraživanju u dubinu (tj. algoritmu rekurzivnog praćenja unatrag), osim što kada ne može ići dalje od trenutne pozicije, sustavno skenira (ili "lovi") labirint kako bi pronašao novu ćeliju iz koje će nastaviti. Algoritam se sastoji od dvije glavne faze: hodanja i lova.

Kako algoritam "Lov i ubijanje" funkcionira za generiranje labirinta

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

• Pronađite slučajnu ćeliju u mreži i označite je kao posjećenu.

Korak 2: Faza hodanja (Nasumično hodanje)

• Odaberite slučajnog neposjećenog susjeda.
• Pomaknite se do tog susjeda, označite ga kao posjećenog i isklešite put između prethodne i nove ćelije.
• Ponavljajte dok ne ostane nijednog neposjećenog susjeda.

Korak 3: Faza lova (povratno praćenje putem skeniranja)

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

Dodatno čitanje

Ako vam se svidio ovaj post, možda će vam se svidjeti i ovi prijedlozi:

• Generator labirinta Ellerovog algoritma
• Kruskalov algoritam generator labirinta
• Algoritam rastućeg stabla Generator labirinta