Ellerio algoritmo labirinto generatorius
Paskelbta: 2025 m. vasario 16 d. 19:59:54 UTC
Labirinto generatorius naudojant Ellerio algoritmą tobulam labirintui sukurti. Šis algoritmas yra įdomus, nes atmintyje reikia išsaugoti tik dabartinę eilutę (ne visą labirintą), todėl jį galima naudoti kuriant labai, labai didelius labirintus net ir labai ribotose sistemose.Eller's Algorithm Maze Generator
Ellerio algoritmas yra labirintų generavimo algoritmas, kuris efektyviai sukuria tobulus labirintus (labirintus be kilpų ir vieno kelio tarp bet kurių dviejų taškų), naudojant eilučių metodą. Jis sukuria labirintus, panašius į Kruskal algoritmą, bet tai daro generuodamas tik vieną eilutę vienu metu ir nereikia saugoti viso labirinto atmintyje. Tai naudinga kuriant labai didelius labirintus labai ribotose sistemose ir kuriant procedūrinį turinį.
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 Elerio algoritmą
Ellerio algoritmą pristatė Davidas Elleris.
Algoritmas pasižymi efektyviu eilučių metodu kuriant labirintą, todėl jis idealiai tinka begaliniams labirintams arba labirintams, generuojamiems realiuoju laiku. Jis dažnai cituojamas procedūrinio turinio generavimo ir labirinto generavimo literatūroje, bet man nepavyko rasti pirminių šaltinių, kuriuose būtų išsamiai aprašyta jo originali publikacija.
Kaip Ellerio algoritmas veikia labirinto generavimui
Ellerio algoritmas apdoroja vieną eilutę vienu metu, palaikydamas ir modifikuodamas prijungtų langelių rinkinius. Tai užtikrina ryšį, išvengiant kilpų, ir efektyviai išplečia labirintą žemyn.
Teoriškai jis gali būti naudojamas generuoti begalinius labirintus, tačiau norint užtikrinti, kad sukurtas 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: sujunkite kai kurias gretimas ląsteles horizontaliai
- Atsitiktinai sujunkite gretimus langelius, nustatydami jiems tą patį rinkinio ID. Taip užtikrinama, kad būtų horizontalūs praėjimai.
3 veiksmas: sukurkite vertikalius ryšius su kita eilute
- Kiekviename eilutėje rodomame rinkinyje bent vienas langelis turi būti prijungtas žemyn (siekiant užtikrinti ryšį).
- Atsitiktinai pasirinkite vieną ar daugiau langelių iš kiekvieno rinkinio, kad prisijungtumėte prie kitos eilutės.
4 veiksmas: pereikite prie kitos eilutės
- Perkelkite vertikalius ryšius, priskirdami tą patį rinkinio ID atitinkamiems langeliams žemiau.
- Priskirkite naujus rinkinio ID visoms nepriskirtoms ląstelėms.
5 veiksmas: kartokite 2–4 veiksmus, kol pasieksite paskutinę eilutę
- Tęskite apdorojimą eilė po eilutės.
6 veiksmas: apdorokite paskutinę eilutę
- Įsitikinkite, kad visi paskutinės eilutės langeliai priklauso tam pačiam rinkiniui, sujungdami visus likusius atskirus rinkinius.