Ellera algoritma labirinta ģenerators

Ellera algoritms ir labirintu ģenerēšanas algoritms, kas efektīvi rada nevainojamus labirintus (labirintus bez cilpām un vienu ceļu starp jebkuriem diviem punktiem), izmantojot rindu pa rindu pieeju. Tas rada Kruskal algoritmam līdzīgus labirintus, taču tas tiek darīts, vienlaikus ģenerējot tikai vienu rindu, bez nepieciešamības saglabāt visu labirintu atmiņā. Tas padara to noderīgu ļoti lielu labirintu ģenerēšanai ļoti ierobežotās sistēmās un procesuāla satura ģenerēšanai.

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

Ellera algoritmu ieviesa Deivids Elers.

Algoritms ir ievērojams ar savu efektīvu rindu pa rindu pieeju labirintu ģenerēšanai, padarot to ideāli piemērotu bezgalīgiem labirintiem vai labirintiem, kas ģenerēti reāllaikā. Tas parasti tiek citēts procesuālā satura ģenerēšanas un labirintu ģenerēšanas literatūrā, taču man nav izdevies atrast primāros avotus, kuros būtu detalizēti aprakstīta tā sākotnējā publikācija.

Kā Ellera algoritms darbojas labirintu paaudzē

Ellera algoritms apstrādā vienu rindu vienlaikus, uzturot un modificējot savienoto šūnu kopas. Tas nodrošina savienojamību, vienlaikus izvairoties no cilpām, un efektīvi paplašina labirintu uz leju.

Teorētiski to var izmantot, lai ģenerētu bezgalīgus labirintus, taču, lai nodrošinātu, ka ģenerētais labirints ir faktiski atrisināms, kādā brīdī ir jāpārslēdzas uz "pēdējās rindas" loģiku, lai pabeigtu labirintu.

1. darbība: inicializējiet pirmo rindu

• Katrai rindas šūnai piešķiriet unikālu kopas ID.

2. darbība: pievienojieties dažām blakus esošajām šūnām horizontāli

• Nejauši sapludiniet blakus esošās šūnas, iestatot tām vienu un to pašu kopas ID. Tas nodrošina, ka ir horizontālas ejas.

3. darbība: izveidojiet vertikālus savienojumus ar nākamo rindu

• Katrai rindā redzamajai kopai ir jāsavieno vismaz viena šūna uz leju (lai nodrošinātu savienojamību).
• Nejauši izvēlieties vienu vai vairākas šūnas no katras kopas, lai izveidotu savienojumu ar nākamo rindu.

4. darbība: pārejiet uz nākamo rindu

• Pārvietojiet vertikālos savienojumus, piešķirot to pašu kopas ID attiecīgajām tālāk esošajām šūnām.
• Piešķiriet jaunu kopas ID visām nepiešķirtajām šūnām.

5. darbība: atkārtojiet 2.–4. darbību, līdz ir sasniegta pēdējā rinda

• Turpiniet apstrādi pēc rindas.

6. darbība: apstrādājiet pēdējo rindu

• Pārliecinieties, vai visas šūnas pēdējā rindā pieder vienai un tai pašai kopai, apvienojot visas atlikušās atsevišķās kopas.