Generator labirinta za lov i ubijanje

Algoritam "Lov i ubijanje" je zapravo modificirana verzija rekurzivnog algoritma "Potraga za novom ćelijom". Modifikacija se sastoji od sistematskog skeniranja (ili "lovljenja") za novom ćelijom od koje se nastavlja od trenutka kada se ne može dalje, za razliku od pravog rekurzivnog pretraživanja, koje će se uvijek vratiti na prethodnu ćeliju na steku.

Zbog toga se ovaj algoritam može lako prilagoditi za generiranje lavirina s različitim izgledom i osjećajem, jednostavnim odabirom češćeg ulaska u "lovni" način rada ili prema određenim pravilima. Verzija implementirana ovdje ulazi u "lovni" način rada 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 za lov i ubijanje

Algoritam "Lov i ubijanje" je jednostavna, ali efikasna metoda za generiranje labirinta. 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, sistematski 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" funkcioniše za generisanje lavirinta

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)

• Izaberite nasumičnog 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 (povratak putem skeniranja)

• Skenirajte mrežu red po red (ili kolonu po kolonu).
• Pronađite 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.

Dodatno čitanje

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

• Rekurzivni Backtracker Maze Generator
• Generator Labirinta Algoritma Eller
• Generator labirinta algoritama za uzgoj drveća