Kasvava puu algoritmi labürindigeneraator

Kasvava puu algoritm on huvitav, kuna see võib jäljendada mitme teise algoritmi käitumist, olenevalt sellest, kuidas genereerimisel järgmine lahter valitakse. Sellel lehel olev juurutamine kasutab laius-esimest järjekorralaadset lähenemist.

Täiuslik labürint on labürint, kus on täpselt üks tee labürindi mis tahes punktist mis tahes teise punkti. See tähendab, et te ei saa sattuda ringiratastesse, kuid sageli satute ummikteedesse, mis sunnib teid ümber pöörama ja tagasi minema.

Siin genereeritud labürindi kaardid sisaldavad vaikimisi versiooni ilma algus- ja lõpp-punktideta, nii et saate need ise otsustada: labürindi mis tahes punktist mis tahes teise punkti on olemas lahendus. Kui soovite inspiratsiooni, saate lubada soovitatud algus- ja lõpupositsiooni - ja isegi näha lahendust nende kahe vahel.

Kasvava puu algoritmi kohta

Kasvava puu algoritm on paindlik ja võimas meetod täiuslike labürindi loomiseks. Algoritm on huvitav, kuna see võib jäljendada mitme teise labürindi genereerimise algoritmi, näiteks Primi algoritmi, rekursiivset tagasiteed ja rekursiivset jagamist, olenevalt sellest, kuidas valite järgmise lahtri töötlemiseks.

Kasvava puu algoritmi toimimine

1. samm: lähtestamine

• Alustage külastamata lahtrite ruudustikuga.
• Valige juhuslik alguslahter ja lisage see loendisse.

2. samm: labürindi genereerimise silmus

• Kui lahtriloend pole tühi:
  • Valige loendist lahter konkreetse strateegia alusel (selgitatud allpool).
  • Lõika valitud lahtrist lõik ühele selle külastamata naabrile (valitud juhuslikult).
  • Lisage naaber loendisse, kuna see on nüüd osa labürindist.
  • Kui valitud lahtril pole külastamata naabreid, eemaldage see loendist.

3. samm: lõpetamine

• Algoritm lõpeb, kui loendis pole enam lahtreid, mis tähendab, et kogu labürint on nikerdatud.

Lahtrite valikustrateegiad (algoritmi paindlikkus)

Kasvava puu algoritmi määravaks tunnuseks on see, kuidas valite, millist lahtrit järgmisena töödelda. See valik mõjutab labürindi välimust dramaatiliselt:

Uusim lahter (virnataoline käitumine) – rekursiivne tagasijälgija:

• Valige alati viimati lisatud lahter.
• Toodab pikki, käänulisi koridore, millel on palju tupikteid (nagu sügavus-esimese otsingulabürint).
• Labürintidel on tavaliselt pikad lõigud ja neid on lihtne lahendada.

Juhuslik rakk (juhusliku primi algoritm):

• Valige loendist iga kord juhuslik lahter.
• Loob ühtlasemalt jaotatud labürindi keerukate, sassis radadega.
• Vähem pikki koridore ja rohkem hargnemist.

Vanim lahter (järjekorrataoline käitumine):

• Valige loendist alati vanim lahter.
• Loob ühtlasema levikuga labürindid, nagu laius-esiteks otsingumuster.
• Tiheda ühendustega lühikesed põõsastikuga läbikäigud.
• (See on siin rakendatud versioon)

Hübriidsed lähenemisviisid:

Kombineerige strateegiaid erinevate labürindi omaduste jaoks. Näiteks:

• 90% uusim, 10% juhuslik: näeb enamasti välja nagu rekursiivne tagasijälgijate rägastik, kuid aeg-ajalt harudega, mis lõhuvad pikki koridore.
• 50% uusim, 50% vanim: tasakaalustab pikki koridore põõsaste kasvuga.