Ellera algoritma labirinta ģenerators

Ellera algoritms ir labirintu ģenerēšanas algoritms, kas efektīvi ģenerē perfektus labirintus (labirint bez cilpām un ar vienu ceļu starp jebkuriem diviem punktiem), izmantojot rindu pa rindai pieeju. Tas ģenerē labirintus, kas ir līdzīgi Kruskala algoritmam, bet to dara, ģenerējot tikai vienu rindu vienlaikus, 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 procedurā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 Ellers.

Algoritms ir ievērojams ar savu efektīvo rindu pa rindai pieeju labirintu ģenerēšanai, padarot to ideāli piemērotu bezgalīgiem labirintiem vai reāllaikā ģenerētiem labirintiem. Tas bieži tiek minēts procedurā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 ģenerēšanai

Ellera algoritms apstrādā vienu rindu vienlaikus, saglabājot 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, tomēr, lai nodrošinātu, ka ģenerētais labirints ir patiešām 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

• Piešķiriet katrai rindas šūnai unikālu kopas ID.

2. darbība. Horizontāli savienojiet dažas blakus esošās šūnas

• Nejauši apvienot blakus esošās šūnas, iestatot tām vienādu kopas ID. Tas nodrošina horizontālu fragmentu esamību.

3. solis: izveidojiet vertikālus savienojumus ar nākamo rindu

• Katrai rindā redzamajai kopai vismaz vienai šūnai ir jābūt savienotai uz leju (lai nodrošinātu savienojamību).
• Nejauši izvēlieties vienu vai vairākas šūnas no katras kopas, lai savienotu tās ar nākamo rindu.

4. darbība. Pāriet uz nākamo rindu

• Pārnest vertikālos savienojumus, piešķirot atbilstošajām šūnām zemāk to pašu kopas ID.
• Piešķiriet jaunus kopas ID visām nepiešķirtajām šūnām.

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

• Turpiniet apstrādi rindu pa rindai.

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

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

Papildu lasāmviela

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

• Medīt un nogalināt labirinta ģenerators
• Augošu koku algoritma labirinta ģenerators
• Rekursīvs Backtracker labirinta ģenerators