Augančio medžio algoritmo labirinto generatorius

Augančio medžio algoritmas yra įdomus, nes jis gali imituoti kelių kitų algoritmų elgesį, priklausomai nuo to, kaip generuojant parenkamas kitas langelis. Diegiant šiame puslapyje naudojamas į eilę panašus metodas.

Tobulasis labirintas - tai labirintas, kuriame iš bet kurio labirinto taško į bet kurį kitą tašką veda lygiai vienas kelias. Tai reiškia, kad negalite eiti ratu, bet dažnai susidursite su aklavietėmis, todėl būsite priversti apsisukti ir grįžti atgal.

Čia sukurtuose labirinto žemėlapiuose yra numatytoji versija be pradžios ir pabaigos pozicijų, todėl jas galite nustatyti patys: iš bet kurio labirinto taško į bet kurį kitą tašką bus rastas sprendimas. Jei norite įkvėpimo, galite įjungti siūlomą pradžios ir pabaigos padėtį ir net pamatyti sprendimą tarp šių dviejų padėčių.

Apie augančio medžio algoritmą

Augančio medžio algoritmas yra lankstus ir galingas būdas sukurti tobulus labirintus. Algoritmas yra įdomus, nes jis gali imituoti kelių kitų labirinto generavimo algoritmų, tokių kaip Prim algoritmas, rekursyvus grįžimas atgal ir rekursinis padalijimas, veikimą, priklausomai nuo to, kaip pasirenkate kitą apdoroti langelį.

Kaip veikia augančio medžio algoritmas

1 veiksmas: inicijavimas

• Pradėkite nuo nelankytų langelių tinklelio.
• Pasirinkite atsitiktinį pradžios langelį ir įtraukite jį į sąrašą.

2 veiksmas: labirinto generavimo kilpa

• Kol langelių sąrašas nėra tuščias:
  • Pasirinkite langelį iš sąrašo pagal konkrečią strategiją (paaiškinta toliau).
  • Iškirpkite ištrauką iš pasirinkto langelio į vieną iš jo nelankomų kaimynų (parinktą atsitiktinai).
  • Įtraukite kaimyną į sąrašą, nes dabar jis yra labirinto dalis.
  • Jei pasirinktame langelyje nėra nelankytų kaimynų, pašalinkite jį iš sąrašo.

3 veiksmas: nutraukimas

• Algoritmas baigiamas, kai sąraše nebėra langelių, o tai reiškia, kad visas labirintas buvo iškirptas.

Ląstelių atrankos strategijos (algoritmo lankstumas)

Pagrindinis augančio medžio algoritmo bruožas yra tai, kaip pasirenkate, kurį langelį apdoroti toliau. Šis pasirinkimas labai paveikia labirinto išvaizdą:

Naujausia ląstelė (į krūvą panašus elgesys) – rekursyvus atgalinis stebėjimo įrankis:

• Visada pasirinkite naujausią pridėtą langelį.
• Sukuria ilgus, vingiuotus koridorius su daugybe aklagatvių (pavyzdžiui, paieškos labirintas, nukreiptas į gylį).
• Labirintai paprastai turi ilgus praėjimus ir juos lengva išspręsti.

Atsitiktinė ląstelė (Randomized Prim algoritmas):

• Kiekvieną kartą iš sąrašo pasirinkite atsitiktinį langelį.
• Sukuria tolygiau paskirstytą labirintą su sudėtingais, susivėlusiais takais.
• Mažiau ilgų koridorių ir daugiau šakų.

Seniausia ląstelė (elgesys panašus į eilę):

• Visada pasirinkite seniausią sąrašo langelį.
• Sukuria vienodesnio išsidėstymo labirintus, pavyzdžiui, paieškos pagal plotį šabloną.
• Trumpi, krūminiai praėjimai su tankiomis jungtimis.
• (Tai čia įdiegta versija)

Hibridiniai metodai:

Sujunkite įvairių labirinto savybių strategijas. Pavyzdžiui:

• 90 % naujausių, 10 % atsitiktinių: dažniausiai atrodo kaip rekursyvus atbulinės eigos labirintas, bet kartais su šakomis, kurios išardo ilgus koridorius.
• 50 % naujausių, 50 % seniausių: subalansuoja ilgus koridorius su krūmais.