Kruskal algoritma labirinta ģenerators

Kruskala algoritms ir minimālā paplašināmā koka algoritms, ko var pielāgot labirintu ģenerēšanai. Tas ir īpaši efektīvs perfektu labirintu izveidei. Alternatīva Kruskala algoritmam ir Prima algoritms, kas arī ir minimālā paplašināmā koka algoritms, taču, tā kā tie ģenerē identiskus labirintus un Kruskala algoritms darbojas ātrāk, es neesmu apgrūtinājies ar Prima algoritma ieviešanu.

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 Kruskala algoritmu

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

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

Kā Kruskala algoritms darbojas labirintu ģenerēšanai

1. darbība: inicializēt

• Katru labirinta šūnu uztveriet kā atsevišķu komplektu (unikālu komponentu).
• Uzskaitiet visas sienas starp blakus esošajām šūnām kā potenciālās malas.

2. darbība: kārtojiet sienas

• Sakārtojiet sienas nejaušā secībā. Ja to ieviešat kā īstu Kruskala algoritmu, sakārtojiet sienas nejaušā secībā (jo labirinta ģenerēšanai nav nepieciešami svari).

3. solis: Procesa sienas

• Atkārtojiet cauri sajauktajām sienām.
• Ja divas šūnas, ko dala siena, pieder pie dažādām kopām (t.i., 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ā Kruskala 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ā. Manu Union-Find algoritma PHP implementāciju varat apskatīt šeit: Saite

Papildu lasāmviela

Ja jums patika šī ziņa, jums varētu patikt arī šie ieteikumi:

• Rekursīvs Backtracker labirinta ģenerators
• Augošu koku algoritma labirinta ģenerators
• Vilsona algoritma labirinta ģenerators