Kruskal algoritmo labirinto generatorius
Paskelbta: 2025 m. vasario 16 d. 17:58:02 UTC
Labirinto generatorius naudojant Kruskal algoritmą tobulam labirintui sukurti. Šis algoritmas linkęs sukurti labirintus su vidutinio ilgio koridoriais ir daugybe aklagatvių, taip pat gana tiesiu sprendimu.Kruskal's Algorithm Maze Generator
Kruskal algoritmas yra minimalaus apimančio medžio algoritmas, kurį galima pritaikyti labirinto generavimui. Tai ypač efektyvu kuriant tobulus labirintus. Alternatyva Kruskal algoritmui yra Prim algoritmas, kuris taip pat yra minimalaus apimančio medžio algoritmas, bet kadangi jie generuoja identiškus labirintus, o Kruskal veikia greičiau, aš nesivarginau diegti Prim's.
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 Kruskal algoritmą
Kruskalio algoritmą sukūrė Džozefas Bernardas Kruskalis, jaunesnysis, amerikiečių matematikas, statistikas ir kompiuterių mokslininkas. Pirmą kartą jis aprašė algoritmą 1956 m. savo darbe „Apie trumpiausią grafiko pomedį ir keliaujančio pardavėjo problemą“.
Algoritmas sukurtas taip, kad būtų galima rasti minimalų grafiko aprėpties medį (MST), užtikrinant, kad visos viršūnės būtų sujungtos su minimaliu galimu bendru briaunų svoriu, išvengiant ciklų.
Kaip Kruskal algoritmas veikia labirinto generavimui
1 veiksmas: inicijuokite
- Kiekvieną labirinto ląstelę laikykite atskiru rinkiniu (unikaliu komponentu).
- Išvardykite visas sienas tarp gretimų langelių kaip galimus kraštus.
2 veiksmas: rūšiuokite sienas
- Maišykite arba atsitiktinai užsakykite sienas. Jei tai įgyvendinate kaip tikrą Kruskal algoritmą, rūšiuokite sienas atsitiktine tvarka (nes labirinto generavimui nereikia svorių).
3 žingsnis: apdorokite sienas
- Kartokite per sumaišytas sienas.
- Jei dvi ląstelės, padalintos iš sienos, priklauso skirtingiems rinkiniams (ty jie dar nėra sujungti labirinte), pašalinkite sieną ir sujunkite rinkinius.
- Jei jie jau yra tame pačiame rinkinyje, praleiskite sieną (kad išvengtumėte ciklų).
4 veiksmas: tęskite, kol baigsite
- Kartokite šį procesą, kol visos ląstelės bus sujungtos ir sudarys vieną besitęsiantį medį.
- Pabaigoje kiekviena ląstelė yra prijungta prie kitų be kilpų ar izoliuotų sekcijų.
Kadangi Kruskal algoritmas remiasi rinkinių sujungimu, jį galima optimizuoti naudojant Union-Find algoritmą, kuris yra efektyvus būdas sekti sujungtas ląsteles generuojant labirintą. Galite pamatyti mano PHP „Union-Fid“ algoritmo įgyvendinimą čia: Disjoint Set (Union-Find Algorithm) PHP