Kasvavan puun algoritmin sokkelogeneraattori

Kasvava puu -algoritmi on mielenkiintoinen, koska se voi emuloida useiden muiden algoritmien käyttäytymistä riippuen siitä, kuinka seuraava solu valitaan generoinnin aikana. Tämän sivun toteutus käyttää jonomaista lähestymistapaa.

Täydellinen sokkelo on sokkelo, jossa on täsmälleen yksi reitti mistä tahansa sokkelon pisteestä mihin tahansa toiseen pisteeseen. Tämä tarkoittaa, että et voi päätyä kiertämään ympyrää, mutta joudut usein umpikujaan, jolloin sinun on pakko kääntyä ympäri ja palata takaisin.

Tässä luotuihin sokkelokarttoihin sisältyy oletusversio, jossa ei ole alku- ja loppupisteitä, joten voit päättää ne itse: mistä tahansa sokkelon pisteestä mihin tahansa muuhun pisteeseen on olemassa ratkaisu. Jos haluat inspiraatiota, voit ottaa käyttöön ehdotetun alku- ja maalipaikan - ja jopa nähdä ratkaisun näiden kahden välissä.

Tietoja kasvavan puun algoritmista

Kasvava puu -algoritmi on joustava ja tehokas menetelmä täydellisten sokkeloiden luomiseen. Algoritmi on mielenkiintoinen, koska se voi jäljitellä useiden muiden sokkeloiden luontialgoritmien, kuten Primin algoritmin, rekursiivisen taaksepäin ja rekursiivisen jaon, käyttäytymistä riippuen siitä, kuinka valitset seuraavan solun käsiteltäväksi.

Kuinka kasvavan puun algoritmi toimii

Vaihe 1: Alustus

• Aloita vierailemattomien solujen ruudukosta.
• Valitse satunnainen aloitussolu ja lisää se luetteloon.

Vaihe 2: Maze Generation Loop

• Vaikka soluluettelo ei ole tyhjä:
  • Valitse solu luettelosta tietyn strategian perusteella (selitys alla).
  • Piirrä kulku valitusta solusta johonkin sen vierailemattomaan naapuriin (valittu satunnaisesti).
  • Lisää naapuri luetteloon, koska se on nyt osa sokkeloa.
  • Jos valitulla solulla ei ole vierailemattomia naapureita, poista se luettelosta.

Vaihe 3: Lopettaminen

• Algoritmi päättyy, kun luettelossa ei ole enää soluja, mikä tarkoittaa, että koko sokkelo on veistetty.

Solujen valintastrategiat (algoritmin joustavuus)

Kasvava puu -algoritmin määrittävä ominaisuus on se, kuinka valitset, mikä solu käsitellään seuraavaksi. Tämä valinta vaikuttaa dramaattisesti sokkelon ulkonäköön:

Uusin solu (pinomainen käyttäytyminen) – Rekursiivinen backtracker:

• Valitse aina viimeksi lisätty solu.
• Tuottaa pitkiä, mutkaisia ​​käytäviä, joissa on monia umpikuja (kuten syvyyttä hakeva sokkelo).
• Sokkeloissa on yleensä pitkiä kulkuja ja ne on helppo ratkaista.

Satunnainen solu (randomized Prim's Algorithm):

• Valitse joka kerta satunnainen solu luettelosta.
• Luo tasaisemmin jakautuneen sokkelon monimutkaisilla, sotkeutuneilla poluilla.
• Vähemmän pitkiä käytäviä ja enemmän haaroja.

Vanhin solu (jonomainen käyttäytyminen):

• Valitse aina luettelon vanhin solu.
• Luo sokkeloita, joiden leviäminen on tasaisempaa, kuten leveys ensin -hakukuvio.
• Lyhyet, tuuheat käytävät tiheillä yhteyksillä.
• (Tämä on tässä toteutettu versio)

Hybridilähestymistavat:

Yhdistä strategioita erilaisiin sokkeloominaisuuksiin. Esimerkiksi:

• 90 % uusinta, 10 % satunnaista: Näyttää enimmäkseen rekursiiviselta takaisinseuraajan labyrintiltä, ​​mutta satunnaisilla oksilla, jotka rikkovat pitkiä käytäviä.
• 50 % uusin, 50 % vanhin: Tasapainottaa pitkät käytävät pensaaseen kasvuun.