Algoritam rastućeg stabla Generator labirinta

Algoritam rastućeg stabla je zanimljiv jer može oponašati ponašanje nekoliko drugih algoritama, ovisno o tome kako je sljedeća ćelija odabrana tijekom generiranja. Implementacija na ovoj stranici koristi pristup u širinu, nalik na red č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 Growing Tree je fleksibilna i moćna metoda za stvaranje savršenih labirinta. Algoritam je zanimljiv jer može oponašati ponašanje nekoliko drugih algoritama za generiranje labirinta, kao što je Primov algoritam, rekurzivno praćenje unatrag i rekurzivno dijeljenje, ovisno o tome kako odaberete sljedeću ćeliju za obradu.

Kako radi algoritam rastućeg stabla

Korak 1: Inicijalizacija

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

Korak 2: Petlja generiranja labirinta

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

Korak 3: Raskid

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

Strategije odabira ćelija (fleksibilnost algoritma)

Definirajuća značajka algoritma rastućeg stabla je način na koji birate koju ćete ćeliju sljedeću obraditi. Ovaj izbor dramatično utječe na izgled labirinta:

Najnovija ćelija (ponašanje poput niza) – rekurzivno praćenje unatrag:

• Uvijek odaberite posljednju dodanu ćeliju.
• Stvara duge, vijugave hodnike s mnogo slijepih ulica (poput labirinta za pretragu u dubinu).
• Labirinti imaju duge prolaze i lako ih je riješiti.

Slučajna ćelija (randomizirani Primov algoritam):

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

Najstarija ćelija (ponašanje poput čekanja):

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

Hibridni pristupi:

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

• 90% najnovije, 10% nasumično: uglavnom izgleda kao rekurzivni labirint za praćenje unazad, ali s povremenim granama koje prekidaju duge hodnike.
• 50% najnoviji, 50% najstariji: Uravnotežuje duge hodnike s grmolikim rastom.