Algoritam za uzgoj drveta Lavirint generator

Algoritam Groving Tree je zanimljiv, jer može oponašati ponašanje nekoliko drugih algoritama, u zavisnosti od toga kako je sledeća ćelija izabrana tokom generacije. Implementacija na ovoj stranici koristi pristup nalik na širinu.

Savršen lavirint je lavirint u kojem postoji tačno jedan put od bilo koje tačke u lavirintu do bilo koje druge tačke. To znači da ne možete završiti u krugovima, ali ćete često naići na ćorsokak, prisiljavajući vas da se okrenete i vratite.

Mape lavirinta generisane ovde uključuju podrazumevanu verziju bez ikakvih početnih i završnih pozicija, tako da možete sami da odlučite o njima: biće rešenje od bilo koje tačke u lavirintu do bilo koje druge tačke. Ako želite inspiraciju, možete da omogućite predloženu početnu i završnu poziciju - pa čak i da vidite rešenje između ova dva.

O algoritmu Rastućeg Drveta

Algoritam Rastućeg Drveta je fleksibilna i moćna metoda za generisanje savršenih lavirinta. Algoritam je zanimljiv jer može emulirati ponašanje nekoliko drugih algoritama za generisanje lavirinata, kao što su Primov algoritam, rekurzivno vraćanje unazad i rekurzivna podela, zavisno od toga kako odaberete sledeću ćeliju koju treba obraditi.

Kako funkcioniše algoritam Rastućeg Drveta

Korak 1: Inicijalizacija

• Počnite sa mrežom neposećenih ćelija.
• Izaberite slučajnu početnu ćeliju i dodajte je na listu.

Korak 2: Petlja generisanja lavirinta

• Dok lista ćelija nije prazna:
  • Izaberite ćeliju sa liste prema specifičnoj strategiji (objašnjeno u nastavku).
  • Isečite prolaz od izabrane ćelije do jednog od njenih neposećenih suseda (izabran slučajno).
  • Dodajte suseda na listu jer je sada deo lavirinta.
  • Ako izabrana ćelija nema neposećene susede, uklonite je sa liste.

Korak 3: Zatvaranje

• Algoritam se završava kada nema više ćelija na listi, što znači da je ceo lavirint isečen.

Strategije izbora ćelija (Fleksibilnost algoritma)

Osobina koja definiše algoritam Rastućeg Drveta je način na koji birate koju ćeliju da obradite sledeću. Ovaj izbor drastično utiče na izgled lavirinta:

Najnovija ćelija (ponašanje slično steku) – Rekurzivni vraćalac unazad:

• Uvek izaberite poslednju dodatu ćeliju.
• Proizvodi dugačke, krivudave hodnike sa mnogim slepim ulicama (kao lavirint pretrage dubine).
• Lavirinti imaju tendenciju da imaju duge prolaze i lako se rešavaju.

Slučajna ćelija (Slučajni Primov algoritam):

• Svaki put izaberite slučajnu ćeliju sa liste.
• Stvara ravnomernije raspoređeni lavirint sa složenim, zapetljanim putem.
• Manje dugih hodnika i više grananja.

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

• Uvek izaberite najstariju ćeliju na listi.
• Generiše lavirinte sa ravnomernijim rasporedom, kao obrazac pretrage širine.
• Kratki, gusti prolazi sa gustom povezanošću.
• (Ovo je verzija implementirana ovde)

Hibridni pristupi:

Spajanjem strategija mogu se postići različite karakteristike lavirinta. Na primer:

• 90% najnovijih, 10% slučajnih: Izgleda uglavnom kao lavirint sa rekurzivnim vraćanjem unazad, ali sa povremenim granama koje razbijaju duge hodnike.
• 50% najnovijih, 50% najstarijih: Balansira duge hodnike sa bujnim rastom.