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 generavimo metu pasirenkama kita ląstelė. Šiame puslapyje pateiktame įgyvendinime naudojamas pločio principu pagrįstas, eilės principu pagrįstas 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 metodas tobuliems labirintams generuoti. Algoritmas įdomus tuo, kad jis gali imituoti kelių kitų labirintų generavimo algoritmų, tokių kaip Primo algoritmas, rekursinis atgalinis sekimas ir rekursinis dalyba, elgesį, priklausomai nuo to, kaip pasirenkate kitą langelį apdorojimui.

Kaip veikia augančio medžio algoritmas

1 veiksmas: inicijavimas

• Pradėkite nuo neaplankytų langelių tinklelio.
• Pasirinkite atsitiktinį pradinį langelį ir įtraukite jį į sąrašą.

Veiksmas: labirinto generavimo ciklas

• Kol langelių sąrašas nėra tuščias: Pasirinkite langelį iš sąrašo pagal konkrečią strategiją (paaiškinta toliau). Nubrėžkite perėjimą iš pasirinkto langelio į vieną iš jo neaplankytų kaimynų (pasirinktų atsitiktinai). Pridėkite kaimyną prie sąrašo, nes jis dabar yra labirinto dalis. Jei pasirinktas langelis neturi neaplankytų kaimynų, pašalinkite jį iš sąrašo.

3 veiksmas: nutraukimas

• Algoritmas baigia darbą, kai sąraše nebėra langelių, tai reiškia, kad visas labirintas yra iškaltas.

Ląstelių atrankos strategijos (algoritmo lankstumas)

Svarbiausias „Augančio medžio“ algoritmo bruožas yra tai, kaip pasirenkate, kurią ląstelę apdoroti toliau. Šis pasirinkimas smarkiai paveikia labirinto išvaizdą:

Naujausias langelis (steką primenantis elgesys) – rekursinis atgalinis sekimas:

• Visada pasirinkite vėliausiai pridėtą langelį.
• Sukuria ilgus, vingiuotus koridorius su daugybe akligatvių (kaip gylio paieškos labirintas).
• Labirintai paprastai būna ilgi ir lengvai įveikiami.

Atsitiktinė ląstelė (atsitiktinės atrankos Prim algoritmas):

• Kiekvieną kartą iš sąrašo pasirinkite atsitiktinę ląstelę.
• Sukuria tolygiau paskirstytą labirintą su sudėtingais, painiotais takais.
• Mažiau ilgų koridorių ir daugiau išsišakojusių.

Seniausia ląstelė (eilės tipo elgesys):

• Visada pasirinkite seniausią sąrašo langelį.
• Generuoja labirintus su tolygesniu išsidėstymu, pavyzdžiui, paieškos pagal plotį modelį.
• Trumpi, krūmingi praėjimai su tankiomis jungtimis.
• (Tai čia įdiegta versija)

Hibridiniai metodai:

Derinkite strategijas, atsižvelgdami į įvairias labirinto charakteristikas. Pavyzdžiui:

• 90 % naujausi, 10 % atsitiktiniai: Dažniausiai atrodo kaip rekursinis atgalinio sekimo labirintas, bet su retkarčiais pasitaikančiomis šakomis, kurios skaido ilgus koridorius.
• 50 % naujausių, 50 % seniausių: subalansuoja ilgus koridorius su krūminiais augalais.

Papildoma literatūra

Jei jums patiko šis įrašas, jums taip pat gali patikti šie pasiūlymai:

• Medžiok ir žudyk labirinto generatorius
• Kruskal algoritmo labirinto generatorius
• Ellerio algoritmo labirinto generatorius