Kasvavan puun algoritmin sokkelogeneraattori

Kasvavan puun algoritmi on mielenkiintoinen, koska se voi jäljitellä useiden muiden algoritmien toimintaa riippuen siitä, miten seuraava solu valitaan generoinnin aikana. Tämän sivun toteutus käyttää leveyslähtöistä, 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

Kasvavan puun 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 takaisinjäljityksen ja rekursiivisen jakolaskun, toimintaa riippuen siitä, miten valitset seuraavan käsiteltävän solun.

Kuinka kasvavan puun algoritmi toimii

Vaihe 1: Alustaminen

• Aloita ruudukolla, jossa on vierailemattomia soluja.
• Valitse satunnainen aloitussolu ja lisää se luetteloon.

Vaihe 2: Sokkelon luontisilmukka

• Kun soluluettelo ei ole tyhjä: Valitse solu luettelosta tietyn strategian perusteella (selitetty alla). Kaiverra käytävä valitusta solusta yhteen sen vierailemattomista naapureista (valittu satunnaisesti). Lisää naapuri luetteloon, koska se on nyt osa sokkeloa. Jos valitulla solulla ei ole vierailemattomia naapureita, poista se luettelosta.

Vaihe 3: Päättäminen

• Algoritmi päättyy, kun listassa ei ole enää soluja, eli koko sokkelo on kaiverrettu.

Solujen valintastrategiat (algoritmin joustavuus)

Kasvavan puun algoritmin määrittelevä ominaisuus on se, miten valitset seuraavaksi käsiteltävän solun. Tämä valinta vaikuttaa dramaattisesti sokkelon ulkonäköön:

Uusin solu (pinomainen toiminta) – Rekursiivinen paluutoiminto:

• Valitse aina viimeksi lisätty solu.
• Tuottaa pitkiä, mutkittelevia käytäviä, joissa on paljon umpikujia (kuten syvyyssuuntainen etsintälabyrintti).
• Sokkelot ovat yleensä pitkiä ja helppoja ratkaista.

Satunnainen solu (satunnaistettu Primin algoritmi):

• Valitse joka kerta satunnainen solu listasta.
• Luo tasaisemmin jakautuneen sokkelon, jossa on monimutkaisia ja mutkikkaita polkuja.
• Vähemmän pitkiä käytäviä ja enemmän haarautumia.

Vanhin solu (jonomainen toiminta):

• Valitse aina listan vanhin solu.
• Luo sokkeloita, joilla on tasaisempi levinneisyys, kuten leveyssuuntainen hakukuvio.
• Lyhyitä, pensaita käytäviä tiheillä yhteyksillä.
• (Tämä on tässä toteutettu versio)

Hybridimenetelmät:

Yhdistä strategioita vaihteleville sokkelo-ominaisuuksille. Esimerkiksi:

• 90 % uusimpia, 10 % satunnaisia: Näyttää enimmäkseen rekursiiviselta paluuradan sokkelolta, mutta satunnaisilla haaroilla, jotka katkaisevat pitkiä käytäviä.
• 50 % uusinta, 50 % vanhinta: Tasapainottaa pitkiä käytäviä tuuhealla kasvustolla.

Lisälukemista

Jos pidit tästä postauksesta, saatat pitää myös näistä ehdotuksista:

• Ellerin algoritmin sokkelogeneraattori
• Kruskalin algoritmi sokkelogeneraattori
• Jahtaa ja Tappaa Labyrintin Generaattori