Augošu koku algoritma labirinta ģenerators

Algoritms Growing Tree ir interesants, jo tas var atdarināt vairāku citu algoritmu uzvedību atkarībā no tā, kā ģenerēšanas laikā tiek izvēlēta nākamā šūna. Šīs lapas ieviešanai tiek izmantota rindai līdzīga pieeja.

Ideāls labirints ir labirints, kurā ir tieši viens ceļš no jebkura labirinta punkta uz jebkuru citu punktu. Tas nozīmē, ka jūs nevarat nonākt apļveida ceļos, bet bieži sastapsieties ar strupceļiem, kas liks jums apgriezties un atgriezties atpakaļ.

Šeit ģenerētajās labirinta kartēs ir noklusējuma versija bez sākuma un beigu pozīcijām, lai jūs paši varētu tās noteikt: būs risinājums no jebkura labirinta punkta uz jebkuru citu punktu. Ja vēlaties iedvesmu, varat ieslēgt ieteikto sākuma un beigu pozīciju un pat apskatīt risinājumu starp šīm divām pozīcijām.

Par augošo koku algoritmu

Augoša koka algoritms ir elastīga un jaudīga metode perfektu labirintu ģenerēšanai. Algoritms ir interesants, jo tas var atdarināt vairāku citu labirintu ģenerēšanas algoritmu darbību, piemēram, Prima algoritmu, rekursīvo atpakaļsekošanu un rekursīvo dalīšanu atkarībā no tā, kā atlasāt nākamo apstrādājamo šūnu.

Kā darbojas augošu koku algoritms

1. darbība: inicializācija

• Sāciet ar neapmeklētu šūnu režģi.
• Izvēlieties nejaušu sākuma šūnu un pievienojiet to sarakstam.

2. darbība: labirinta ģenerēšanas cilpa

• Kamēr šūnu saraksts nav tukšs:
  • Sarakstā atlasiet šūnu, pamatojoties uz noteiktu stratēģiju (skaidrots tālāk).
  • Izveidojiet fragmentu no atlasītās šūnas uz kādu no tās neapmeklētajiem kaimiņiem (izvēlēts nejauši).
  • Pievienojiet sarakstam kaimiņu, jo tas tagad ir daļa no labirinta.
  • Ja atlasītajai šūnai nav neapmeklētu kaimiņu, noņemiet to no saraksta.

3. darbība. Pārtraukšana

• Algoritms beidzas, kad sarakstā vairs nav nevienas šūnas, kas nozīmē, ka viss labirints ir izgriezts.

Šūnu atlases stratēģijas (algoritma elastība)

Augoša koka algoritma noteicošā iezīme ir veids, kā jūs izvēlaties, kuru šūnu apstrādāt nākamo. Šī izvēle dramatiski ietekmē labirinta izskatu:

Jaunākā šūna (kopai līdzīga uzvedība) — rekursīvais atpakaļsekošanas līdzeklis:

• Vienmēr atlasiet pēdējo pievienoto šūnu.
• Izveido garus, līkumotus koridorus ar daudziem strupceļiem (piemēram, dziļuma meklēšanas labirints).
• Labirintiem parasti ir garas ejas, un tos ir viegli atrisināt.

Izlases šūna (Randomizēts Prim algoritms):

• Katru reizi izvēlieties nejaušu šūnu no saraksta.
• Izveido vienmērīgāk sadalītu labirintu ar sarežģītiem, samezglotiem celiņiem.
• Mazāk garu koridoru un vairāk sazarojumu.

Vecākā šūna (rindai līdzīga darbība):

• Vienmēr izvēlieties vecāko šūnu sarakstā.
• Ģenerē labirintus ar vienmērīgāku izplatību, piemēram, meklēšanas modeli pēc platuma.
• Īsas, kuplas ejas ar blīviem savienojumiem.
• (Šī ir šeit ieviestā versija)

Hibrīdās pieejas:

Apvienojiet stratēģijas dažādām labirinta īpašībām. Piemēram:

• 90% jaunākie, 10% nejauši: lielākoties izskatās pēc rekursīva atpalicēju labirinta, taču ar gadījuma atzariem, kas sadala garus koridorus.
• 50% jaunākie, 50% vecākie: līdzsvaro garus koridorus ar kuplu augšanu.