Jenereta ya Maze ya Algorithm ya Eller

Algorithm ya Eller ni algorithm ya uzalishaji wa maze ambayo hutoa kwa ufanisi mazes kamilifu (mazes zisizo na vitanzi na njia moja kati ya nukta mbili) kwa kutumia mbinu ya safu-kwa-mstari. Inazalisha mazes zinazofanana na algorithm ya Kruskal, lakini inafanya hivyo kwa kutoa safu-mfululizo moja tu kwa wakati mmoja, bila hitaji la kuhifadhi maze nzima kwenye kumbukumbu. Hiyo inafanya iwe muhimu kwa kutengeneza mazes kubwa sana kwenye mifumo midogo sana na kwa ajili ya uzalishaji wa maudhui ya kiutaratibu.

Maze kamili ni maze ambayo kuna njia moja kutoka kwa hatua yoyote kwenye maze hadi hatua nyingine yoyote. Hiyo ina maana kwamba huwezi kuishia kuzunguka kwenye miduara, lakini mara nyingi utakutana na ncha zisizokufa, na kukulazimisha kugeuka na kurudi nyuma.

Ramani za mlolongo zinazozalishwa hapa ni pamoja na toleo chaguo-msingi bila nafasi zozote za kuanza na kumaliza, kwa hivyo unaweza kujiamulia hizo: kutakuwa na suluhu kutoka sehemu yoyote kwenye msururu hadi sehemu nyingine yoyote. Ikiwa unataka msukumo, unaweza kuwezesha nafasi iliyopendekezwa ya kuanza na kumaliza - na hata kuona suluhisho kati ya hizo mbili.

Kuhusu Algorithm ya Eller

Algorithm ya Eller ilianzishwa na David Eller.

Algorithm hii inajulikana kwa mbinu yake bora ya safu-kwa-mstari ya kutengeneza maze, na kuifanya iwe bora kwa maze au maze zisizo na kikomo zinazozalishwa kwa wakati halisi. Mara nyingi hutajwa katika utengenezaji wa maudhui ya kiutaratibu na fasihi ya utengenezaji wa maze, lakini sijaweza kupata vyanzo vya msingi vinavyoelezea uchapishaji wake wa asili.

Jinsi Algorithm ya Eller Inavyofanya Kazi kwa Kizazi cha Maze

Algoritimu ya Eller huchakata safu moja baada ya nyingine, ikidumisha na kurekebisha seti za seli zilizounganishwa. Inahakikisha muunganisho huku ikiepuka mizunguko, na inapanua maze kuelekea chini kwa ufanisi.

Kinadharia inaweza kutumika kutengeneza maze zisizo na kikomo, hata hivyo ili kuhakikisha kwamba maze inayozalishwa inaweza kutatuliwa, ni muhimu kubadili hadi kwenye mantiki ya "safu ya mwisho" wakati fulani ili kumaliza maze.

Hatua ya 1: Anzisha Safu ya Kwanza

• Mpe kila seli kwenye safu mlalo kitambulisho cha kipekee cha seti.

Hatua ya 2: Jiunge na Baadhi ya Seli Zilizo Karibu Mlalo

• Unganisha seli zilizo karibu bila mpangilio kwa kuziweka kwenye kitambulisho sawa cha seti. Hii inahakikisha kwamba kuna njia za mlalo.

Hatua ya 3: Unda Miunganisho ya Wima kwenye Safu Inayofuata

• Kwa kila seti inayoonekana kwenye safu mlalo, angalau seli moja lazima iunganishwe chini (ili kuhakikisha muunganisho).
• Chagua seli moja au zaidi kutoka kila seti bila mpangilio ili kuungana na safu mlalo inayofuata.

Hatua ya 4: Sogeza kwenye Safu Inayofuata

• Sogeza mbele miunganisho ya wima kwa kugawa kitambulisho sawa cha seti kwenye seli zinazolingana zilizo hapa chini.
• Pangia vitambulisho vipya vya seti kwa seli zozote ambazo hazijagawiwa.

Hatua ya 5: Rudia Hatua 2–4 Hadi Safu ya Mwisho Ifikiwe

• Endelea kusindika safu kwa safu.

Hatua ya 6: Kushughulikia Safu ya Mwisho

• Hakikisha seli zote katika safu mlalo ya mwisho zinahusiana na seti moja kwa kuunganisha seti zozote tofauti zilizobaki.

Kusoma Zaidi

Ikiwa ulifurahia chapisho hili, unaweza pia kupenda mapendekezo haya:

• Jenereta ya Maze ya Backtracker ya Kujirudia
• Jenereta ya Maze ya Algorithm ya Wilson
• Kuwinda na Ua jenereta ya Maze