Algoritam rastućeg stabla Generator labirinta

Algoritam Rastućeg stabla je zanimljiv jer može emulirati ponašanje nekoliko drugih algoritama, ovisno o tome kako se sljedeća ćelija odabire tijekom generiranja. Implementacija na ovoj stranici koristi pristup koji prvo prelazi u širinu i sličan je redu čekanja.

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 rastućeg stabla

Algoritam Rastućeg stabla je fleksibilna i moćna metoda za generiranje savršenih labirinata. Algoritam je zanimljiv jer može emulirati ponašanje nekoliko drugih algoritama za generiranje labirinata, kao što su Primov algoritam, rekurzivno vraćanje unatrag i rekurzivno dijeljenje, ovisno o tome kako odaberete sljedeću ćeliju za obradu.

Kako funkcionira algoritam rastućeg stabla

Korak 1: Inicijalizacija

• Započnite s mrežom neposjećenih ćelija.
• Odaberite slučajnu početnu ćeliju i dodajte je na popis.

Korak 2: Petlja generiranja labirinta

• Dok popis ćelija nije prazan: Odaberite ćeliju s popisa na temelju određene strategije (objašnjene u nastavku). Izrežite prolaz od odabrane ćelije do jednog od njezinih neposjećenih susjeda (odabranih nasumično). Dodajte susjeda na popis jer je sada dio labirinta. Ako odabrana ćelija nema neposjećenih susjeda, uklonite je s popisa.

Korak 3: Prekid

• Algoritam završava kada na popisu više nema ćelija, što znači da je cijeli labirint izrezbaren.

Strategije odabira ćelija (fleksibilnost algoritma)

Ključna značajka algoritma Rastuće stablo je način na koji birate koju će ćeliju sljedeće obraditi. Ovaj izbor dramatično utječe na izgled labirinta:

Najnovija ćelija (ponašanje slično stogu) – Rekurzivni Backtracker:

• Uvijek odaberite najnoviju dodanu ćeliju.
• Stvara duge, vijugave hodnike s mnogo slijepih ulica (poput labirinta za pretraživanje u dubinu).
• Labirinti obično imaju duge prolaze i lako ih je riješiti.

Slučajna ćelija (randomizirani Primov algoritam):

• Svaki put odaberite slučajnu ćeliju s popisa.
• Stvara ravnomjernije raspoređen labirint sa složenim, zapetljanim stazama.
• Manje dugih hodnika i više grananja.

Najstarija ćelija (ponašanje slično redu čekanja):

• Uvijek odaberite najstariju ćeliju na popisu.
• Generira labirinte s ravnomjernijim širenjem, poput uzorka pretraživanja u širinu.
• Kratki, grmoliki prolazi s gustim vezama.
• (Ovo je ovdje implementirana verzija)

Hibridni pristupi:

Kombinirajte strategije za različite karakteristike labirinta. Na primjer:

• 90% najnovije, 10% nasumično: Izgleda uglavnom kao rekurzivni labirint s povratnim tragom, ali s povremenim granama koje prekidaju duge hodnike.
• 50% najnovije, 50% najstarije: Uravnotežuje duge hodnike s grmolikim rastom.

Dodatno čitanje

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

• Generator labirinta Ellerovog algoritma
• Generator Labirinta Lov i Ubijanje
• Kruskalov algoritam generator labirinta