Kruskal algoritma labirinta ģenerators

Kruskal algoritms ir minimālā aptverošā koka algoritms, ko var pielāgot labirinta ģenerēšanai. Tas ir īpaši efektīvs ideālu labirintu izveidošanai. Alternatīva Kruskal algoritmam ir Prim algoritms, kas arī ir minimālā aptverošā koka algoritms, bet, tā kā tie ģenerē identiskus labirintus un Kruskal darbojas ātrāk, es neesmu apgrūtinājusies ar Prim algoritmu.

Ideāls labirints ir labirints, kurā ir tieši viens ceļš no jebkura labirinta punkta uz jebkuru citu punktu. Tas nozīmē, ka jūs nevarat nonākt apļveida ceļos, bet bieži sastapsieties ar strupceļiem, kas liks jums apgriezties un atgriezties atpakaļ.

Šeit ģenerētajās labirinta kartēs ir noklusējuma versija bez sākuma un beigu pozīcijām, lai jūs paši varētu tās noteikt: būs risinājums no jebkura labirinta punkta uz jebkuru citu punktu. Ja vēlaties iedvesmu, varat ieslēgt ieteikto sākuma un beigu pozīciju un pat apskatīt risinājumu starp šīm divām pozīcijām.

Par Kruskal algoritmu

Kruskala algoritmu izveidoja Džozefs Bernards Kruskals, jaunākais, amerikāņu matemātiķis, statistiķis un datorzinātnieks. Pirmo reizi viņš algoritmu aprakstīja 1956. gadā savā darbā "Par diagrammas īsāko aptverošo apakškoku un ceļojošā pārdevēja problēmu".

Algoritms ir izstrādāts, lai atrastu grafa minimālo aptverošo koku (MST), nodrošinot, ka visas virsotnes ir savienotas ar minimālu iespējamo kopējo malas svaru, vienlaikus izvairoties no cikliem.

Kā Kruskal algoritms darbojas labirintu ģenerēšanai

1. darbība. Inicializējiet

• Apstrādājiet katru labirinta šūnu kā atsevišķu komplektu (unikālu sastāvdaļu).
• Uzskaitiet visas sienas starp blakus esošajām šūnām kā iespējamās malas.

2. darbība: kārtojiet sienas

• Sajauciet vai nejauši pasūtiet sienas. Ieviešot to kā īstu Kruskal algoritmu, kārtojiet sienas nejaušā secībā (jo labirinta ģenerēšanai nav nepieciešami atsvari).

3. darbība: apstrādājiet sienas

• Atkārtojiet cauri sajauktajām sienām.
• Ja abas šūnas, kas sadalītas ar sienu, pieder dažādām kopām (ti, tās vēl nav savienotas labirintā), noņemiet sienu un apvienojiet kopas.
• Ja tie jau ir vienā komplektā, izlaidiet sienu (lai izvairītos no cikliem).

4. darbība: turpiniet līdz pabeigšanai

• Atkārtojiet šo procesu, līdz visas šūnas ir savienotas, veidojot vienu aptverošu koku.
• Beigās katra šūna ir savienota ar pārējām bez cilpām vai izolētām sekcijām.

Tā kā Kruskal algoritms balstās uz kopu apvienošanu, to var optimizēt, izmantojot Union-Find algoritmu, kas nodrošina efektīvu veidu, kā izsekot savienotās šūnas labirinta ģenerēšanas laikā. Jūs varat redzēt manu Union-Find algoritma ieviešanu PHP šeit: Disjoint Set (Union-Find Algorithm) PHP