Generator labirinta algoritama za uzgoj drveća

Algoritam Growing Tree je zanimljiv, jer može oponašati ponašanje nekoliko drugih algoritama, ovisno o tome kako je sljedeća ćelija odabrana tokom generacije. Implementacija na ovoj stranici koristi pristup nalik na širinu, poput reda.

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 uzgoja stabla

Algoritam Growing Tree je fleksibilan i moćan metod za generisanje savršenih labirinta. Algoritam je zanimljiv jer može oponašati ponašanje nekoliko drugih algoritama za generiranje labirinta, kao što su Primov algoritam, rekurzivno vraćanje unazad i rekurzivna podjela, u zavisnosti od toga kako odaberete sljedeću ćeliju za obradu.

Kako radi algoritam rastućeg stabla

Korak 1: Inicijalizacija

• Počni sa mrežom neposjećenih ćelija.
• Odaberite nasumičnu početnu ćeliju i dodajte je na listu.

Korak 2: Petlja stvaranja labirinta

• Dok lista ćelija nije prazna:
  • Izaberite ćeliju sa liste na osnovu specifične strategije (objašnjeno u nastavku).
  • Izrežite prolaz iz odabrane ćelije do jednog od njenih neposjećenih susjeda (odabranih nasumično).
  • Dodajte susjeda na popis jer je sada dio labirinta.
  • Ako odabrana ćelija nema neposjećenih susjeda, uklonite je sa liste.

Korak 3: Raskid

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

Strategije odabira ćelija (fleksibilnost algoritma)

Definirajuća karakteristika algoritma Growing Tree je kako birate koju ćeliju ćete obraditi sljedeću. Ovaj izbor dramatično utiče na izgled labirinta:

Newest Cell (Stack-like Behavior) – Rekurzivni Backtracker:

• Uvijek odaberite posljednju dodanu ćeliju.
• Stvara dugačke, zavojite hodnike s mnogo slijepih ulica (poput labirinta za pretraživanje dubine).
• Labirinti imaju tendenciju da imaju duge prolaze i lako ih je riješiti.

Slučajna ćelija (Randomizirani Primov algoritam):

• Svaki put izaberi nasumičnu ćeliju sa liste.
• Stvara ravnomjernije raspoređen labirint sa složenim, zamršenim stazama.
• Manje dugih hodnika i više grananja.

Najstarija ćelija (ponašanje poput reda):

• Uvijek odaberite najstariju ćeliju na listi.
• Generira labirinte sa ujednačenijim širenjem, kao širina prvog obrasca pretraživanja.
• Kratki, žbunasti prolazi sa gustim vezama.
• (Ovo je verzija implementirana ovdje)

Hibridni pristupi:

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

• 90% najnoviji, 10% nasumično: Izgleda uglavnom kao rekurzivni labirint backtrackera, ali s povremenim granama koje razbijaju dugačke hodnike.
• 50% najnoviji, 50% najstariji: Uravnotežuje duge hodnike sa grmolikim rastom.