Generator labirinta algoritama za uzgoj drveća

Algoritam "Rastući stablo" je zanimljiv jer može emulirati ponašanje nekoliko drugih algoritama, ovisno o tome kako se sljedeća ćelija bira tokom 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 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 rastućeg drveta

Algoritam "Growing Tree" je fleksibilna i moćna metoda za generiranje savršenih labirinta. Algoritam je zanimljiv jer može emulirati ponašanje nekoliko drugih algoritama za generiranje labirinta, 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 drveta

Korak 1: Inicijalizacija

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

Korak 2: Petlja generiranja labirinta

• Dok lista ćelija nije prazna: Odaberite ćeliju s liste na osnovu određene strategije (objašnjene u nastavku). Izrežite prolaz od odabrane ćelije do jednog od njenih neposjećenih susjeda (odabranih nasumično). Dodajte susjeda na listu jer je sada dio lavirinta. Ako odabrana ćelija nema neposjećenih susjeda, uklonite je s liste.

Korak 3: Prekid

• Algoritam završava kada na listi više nema ćelija, što znači da je cijeli lavirint isklesan.

Strategije odabira ćelija (fleksibilnost algoritma)

Ključna karakteristika algoritma Rastućeg stabla je način na koji birate koju će ćeliju sljedeće obraditi. Ovaj izbor dramatično utiče na izgled labirinta:

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

• Uvijek odaberite najnoviju dodanu ćeliju.
• Proizvodi duge, vijugave hodnike s mnogo slijepih ulica (poput lavirinta 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 liste.
• Stvara ravnomjernije raspoređen labirint sa složenim, zamršenim stazama.
• Manje dugih hodnika i više grananja.

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

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

Hibridni pristupi:

Kombinujte strategije za različite karakteristike lavirinta. Na primjer:

• 90% najnovije, 10% nasumično: Uglavnom izgleda kao rekurzivni labirint unatrag, 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 za lov i ubijanje
• Rekurzivni Backtracker Maze Generator
• Generator Labirinta Algoritma Eller