Ellerio algoritmo labirinto generatorius

Ellerio algoritmas yra labirintų generavimo algoritmas, kuris efektyviai sukuria tobulus labirintus (labirintus be kilpų ir vienu keliu tarp bet kurių dviejų taškų), naudodamas eilutė po eilutės metodą. Jis sukuria labirintus, panašius į Kruskalo algoritmą, tačiau tai daro generuodamas tik po vieną eilutę, nereikalaujant viso labirinto saugoti atmintyje. Tai daro jį naudingą generuojant labai didelius labirintus labai ribotose sistemose ir procedūriniam turiniui generuoti.

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 Ellerio algoritmą

Ellerio algoritmą pristatė Davidas Elleris.

Šis algoritmas pasižymi efektyviu eilutė po eilutės labirintų generavimo metodu, todėl idealiai tinka begaliniams labirintams arba realiuoju laiku generuojamiems labirintams. Jis dažnai cituojamas procedūrinio turinio generavimo ir labirintų generavimo literatūroje, tačiau man nepavyko rasti pirminių šaltinių, kuriuose būtų išsamiai aprašytas jo originalus publikavimas.

Kaip Ellerio algoritmas veikia labirinto generavimui

Ellerio algoritmas apdoroja po vieną eilutę, išlaikydamas ir keisdamas sujungtų langelių rinkinius. Jis užtikrina sujungiamumą, vengdamas ciklų, ir efektyviai plečia labirintą žemyn.

Teoriškai tai galima naudoti begaliniams labirintams generuoti, tačiau norint užtikrinti, kad sugeneruotas labirintas iš tikrųjų būtų išsprendžiamas, tam tikru momentu reikia pereiti prie „paskutinės eilutės“ logikos, kad labirintas būtų baigtas.

1 veiksmas: inicijuokite pirmąją eilutę

• Kiekvienam eilutės langeliui priskirkite unikalų rinkinio ID.

2 veiksmas: horizontaliai sujunkite kelias gretimas ląsteles

• Atsitiktinai sujungti gretimus langelius, nustatant jiems tą patį rinkinio ID. Tai užtikrina horizontalių ištraukų buvimą.

3 veiksmas: sukurkite vertikalius ryšius su kita eilute

• Kiekvienam eilutėje rodomam rinkiniui bent viena ląstelė turi būti prijungta žemyn (kad būtų užtikrintas ryšys).
• Atsitiktinai pasirinkite vieną ar daugiau langelių iš kiekvieno rinkinio, kad sujungtumėte juos su kita eilute.

4 veiksmas: pereikite prie kitos eilutės

• Perkelkite vertikalius ryšius, priskirdami tą patį rinkinio ID atitinkamoms langeliams žemiau.
• Priskirkite naujus rinkinio ID visoms nepriskirtoms ląstelėms.

5 veiksmas: kartokite 2–4 veiksmus, kol bus pasiekta paskutinė eilutė

• Tęskite apdorojimą eilutė po eilutės.

6 veiksmas: apdorokite paskutinę eilutę

• Sujungdami visus likusius atskirus rinkinius, užtikrinkite, kad visi paskutinės eilutės langeliai priklausytų tam pačiam rinkiniui.

Papildoma literatūra

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

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