Jenereta ya Maze ya Algorithm ya Eller

Algorithm ya Eller ni algorithm ya kizazi cha maze ambayo hutoa mazes kamili (mazes bila kitanzi na njia moja kati ya pointi mbili) kwa kutumia njia ya safu kwa safu. Inatoa mazes sawa na algorithm ya Kruskal, lakini inafanya hivyo kwa kuzalisha safu moja tu kwa wakati mmoja, bila hitaji la kuhifadhi maze nzima katika kumbukumbu. Hiyo inafanya kuwa muhimu kwa kuzalisha mazes kubwa sana kwenye mifumo ndogo sana na kwa kizazi cha maudhui ya utaratibu.

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 ni maarufu kwa njia yake ya ufanisi ya safu kwa kizazi cha maze, na kuifanya iwe bora kwa mazes isiyo na mwisho au mazes zinazozalishwa kwa wakati halisi. Kwa kawaida imetajwa katika kizazi cha maudhui ya utaratibu na fasihi ya kizazi cha maze, lakini sijaweza kupata vyanzo vya msingi vinavyoelezea uchapishaji wake wa awali.

Jinsi Algorithm ya Eller inavyofanya kazi kwa Kizazi cha Maze

Algorithm ya Eller huchakata safu moja kwa wakati mmoja, kudumisha na kurekebisha seti za seli zilizounganishwa. Inahakikisha muunganisho wakati wa kuepuka vitanzi, na inapanua kwa ufanisi maze chini.

Inaweza kinadharia kutumika kuzalisha mazes isiyo na mwisho, hata hivyo ili kuhakikisha kuwa maze zinazozalishwa ni kweli kuokoka, ni muhimu kubadili mantiki ya "mstari wa mwisho" wakati fulani kumaliza maze.

Hatua ya 1: Anzisha safu ya kwanza

• Pangia kila seli katika safu ya kitambulisho cha kipekee kilichowekwa.

Hatua ya 2: Jiunge na Seli za Adjacent kwa usawa

• Changanisha kwa nasibu seli zilizo karibu kwa kuziweka kwenye kitambulisho sawa kilichowekwa. Hii inahakikisha kuwa kuna vifungu vya usawa.

Hatua ya 3: Unda Miunganisho Wima kwenye Safu Ulalo Ifuatayo

• Kwa kila seti inayoonekana kwenye safu, angalau seli moja lazima iunganishe chini (ili kuhakikisha muunganisho).
• Chagua kwa nasibu seli moja au zaidi kutoka kwa kila seti ili kuunganisha kwenye safu mlalo inayofuata.

Hatua ya 4: Nenda kwenye safu mlalo inayofuata

• Weka mbele miunganisho wima kwa kugawa kitambulisho sawa kilichowekwa kwenye seli zinazolingana hapa chini.
• Pangia vitambulisho vipya vya seti kwa seli zozote ambazo hazijasainiwa.

Hatua ya 5: Rudia Hatua 2–4 Mpaka Safu ya Mwisho Ifikie

• Endelea kuchakata safu mlalo kwa safu.

Hatua ya 6: Mchakato wa Safu ya Mwisho

• Hakikisha seli zote katika safu mlalo ya mwisho ni za seti sawa kwa kuunganisha seti zozote zilizobaki tofauti.