Augošu koku algoritma labirinta ģenerators

Augošā koka algoritms 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. Šajā lapā aprakstītajā ieviešanā tiek izmantota platuma, rindas veida 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šā koka algoritmu

Augošā 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, piemēram, Prima algoritma, rekursīvās atpakaļizsekošanas un rekursīvās dalīšanas, darbību atkarībā no tā, kā tiek atlasīta nākamā apstrādājamā šūna.

Kā darbojas augošā koka 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. solis: Labirinta ģenerēšanas cilpa

• Kamēr šūnu saraksts nav tukšs: atlasiet šūnu no saraksta, pamatojoties uz noteiktu stratēģiju (paskaidrojums sniegts tālāk). izveidojiet pāreju no atlasītās šūnas uz vienu no tās neapmeklētajām kaimiņvalstīm (izvēlētām nejauši). pievienojiet kaimiņu sarakstam, jo tā tagad ir daļa no labirinta. ja atlasītajai šūnai nav neapmeklētu kaimiņvalstu, noņemiet to no saraksta.

3. solis: Līguma izbeigšana

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

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

Augošā koka algoritma raksturīgā iezīme ir tas, kā jūs izvēlaties, kuru šūnu apstrādāt tālāk. Šī izvēle būtiski ietekmē labirinta izskatu:

Jaunākā šūna (steka tipa uzvedība) — rekursīvs atpakaļizsekošanas rīks:

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

Nejauša šūna (nejauši izvēlēts Prim algoritms):

• Katru reizi izvēlieties nejaušu šūnu no saraksta.
• Izveido vienmērīgāku labirintu ar sarežģītām, sapinušām takām.
• Mazāk garu koridoru un vairāk atzarojumu.

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

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

Hibrīda pieejas:

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

• 90 % jaunākie, 10 % nejauši: Izskatās pārsvarā pēc rekursīva atpakaļejoša labirinta, bet ar neregulāriem atzariem, kas sadala garus koridorus.
• 50% jaunākie, 50% vecākie: līdzsvaro garus koridorus ar kupliem kokiem.

Papildu lasāmviela

Ja jums patika šī ziņa, jums varētu patikt arī šie ieteikumi:

• Medīt un nogalināt labirinta ģenerators
• Ellera algoritma labirinta ģenerators
• Rekursīvs Backtracker labirinta ģenerators