Kruskal algoritmo labirinto generatorius

Kruskalo algoritmas yra minimalaus besidriekiančio medžio algoritmas, kurį galima pritaikyti labirintų generavimui. Jis ypač efektyvus kuriant tobulus labirintus. Alternatyva Kruskalo algoritmui yra Primo algoritmas, kuris taip pat yra minimalaus besidriekiančio medžio algoritmas, tačiau kadangi jie generuoja identiškus labirintus, o Kruskalo algoritmas veikia greičiau, aš nesivarginau įgyvendinti Primo algoritmo.

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

Kruskalo algoritmą sukūrė amerikiečių matematikas, statistikas ir kompiuterių mokslininkas Josephas Bernardas Kruskalas jaunesnysis. Pirmą kartą algoritmą jis aprašė 1956 m. savo straipsnyje „Apie trumpiausią grafo besidriekiantį submedį ir keliaujančio pardavėjo problemą“.

Algoritmas sukurtas taip, kad rastų grafo minimalų besidriekiantį medį (MST), užtikrinant, kad visos viršūnės būtų sujungtos su kuo mažesniu bendru briaunų svoriu, vengiant ciklų.

Kaip Kruskalo algoritmas veikia labirinto generavimui

1 veiksmas: inicijavimas

• Kiekvieną labirinto ląstelę traktuokite kaip atskirą rinkinį (unikalių komponentų).
• Išvardykite visas sienas tarp gretimų langelių kaip galimas briaunas.

2 veiksmas: rūšiuokite sienas

• Sumaišykite arba atsitiktine tvarka išdėliokite sienas. Jei įgyvendinate kaip tikrą Kruskalo algoritmą, rūšiuokite sienas atsitiktine tvarka (nes labirinto generavimui nereikia svorių).

3 žingsnis: Proceso sienos

• Kartok per iškraipytas sienas.
• Jei dvi siena atskirtos ląstelės priklauso skirtingiems rinkiniams (t. y. jos dar nėra sujungtos 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 iki pabaigos

• Kartokite šį procesą, kol visos ląstelės bus sujungtos ir sudarys vieną besidriekiantį medį.
• Galiausiai kiekviena ląstelė yra sujungta su kitomis be kilpų ar izoliuotų sekcijų.

Kadangi Kruskalo algoritmas remiasi aibių suliejimu, jį galima optimizuoti naudojant „Union-Find“ algoritmą, kuris suteikia efektyvų būdą sekti sujungtas ląsteles labirinto generavimo metu. Mano PHP „Union-Find“ algoritmo įgyvendinimą galite pamatyti čia: Nuoroda

Papildoma literatūra

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

• Wilsono algoritmo labirinto generatorius
• Augančio medžio algoritmo labirinto generatorius
• Rekursyvus Backtracker labirinto generatorius