Kasvava puu algoritmi labürindigeneraator

Kasvava puu algoritm on huvitav, kuna see suudab jäljendada mitmete teiste algoritmide käitumist, olenevalt sellest, kuidas järgmine lahter genereerimise ajal valitakse. Sellel lehel olev implementatsioon kasutab laiuspõhist, 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ürintide genereerimiseks. Algoritm on huvitav, kuna see suudab jäljendada mitmete teiste labürindi genereerimise algoritmide käitumist, näiteks Primi algoritmi, rekursiivse tagasijälgimise ja rekursiivse jagamise, olenevalt sellest, kuidas järgmise töötlemiseks mõeldud lahtri valite.

Kuidas kasvava puu algoritm töötab

1. samm: initsialiseerimine

• Alusta külastamata lahtrite ruudustikuga.
• Valige suvaline alguslahter ja lisage see loendisse.

2. samm: labürindi genereerimise tsükkel

• Kuni lahtrite loend pole tühi: vali loendist lahter kindla strateegia põhjal (selgitatud allpool). loo valitud lahtrist läbipääs ühte selle külastamata naabritesse (valitud juhuslikult). lisa naaber loendisse, kuna see on nüüd labürindi osa. kui valitud lahtril pole külastamata naabreid, eemalda see loendist.

3. samm: Lõpetamine

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

Rakkude valiku strateegiad (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 (virnalaadne käitumine) – rekursiivne tagasijälgija:

• Vali alati viimati lisatud lahter.
• Tekitab pikki ja käänulisi koridore paljude tupikutega (nagu sügavusotsingu labürint).
• Labürintidel on tavaliselt pikad lõigud ja neid on lihtne lahendada.

Juhuslik lahter (juhuslik Prim'i algoritm):

• Vali iga kord loendist suvaline lahter.
• Loob ühtlasemalt jaotatud labürindi keerukate ja sassis radadega.
• Vähem pikki koridore ja rohkem hargnevaid teid.

Vanim lahter (järjekorralaadne käitumine):

• Vali alati loendist vanim lahter.
• Genereerib ühtlasema jaotusega labürinte, näiteks laiuskeskse otsingu mustrit.
• Lühikesed, võsastunud käigud tihedate ühendustega.
• (See on siin rakendatud versioon)

Hübriidsed lähenemisviisid:

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

• 90% uusim, 10% juhuslik: Näeb välja nagu rekursiivne tagasitee labürint, aga kohati hargneb pikki koridore.
• 50% uusim, 50% vanim: tasakaalustab pikki koridore põõsastikuga.

Lisalugemist

Kui see postitus teile meeldis, võivad teile meeldida ka need soovitused:

• Kruskali algoritmi labürindi generaator
• Wilsoni algoritmi labürindi generaator
• Jahti ja Tappa Labürindi Loodur