Kuongezeka kwa Jenereta ya Maze ya Algorithm ya Miti

Algoritimu ya Growing Tree inavutia, kwa sababu inaweza kuiga tabia ya algoriti zingine kadhaa, kulingana na jinsi seli inayofuata inavyochaguliwa wakati wa uzalishaji. Utekelezaji kwenye ukurasa huu unatumia mbinu ya upana-kwanza, kama foleni.

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 Kukua kwa Miti

Algoriti ya Growing Tree ni njia inayonyumbulika na yenye nguvu ya kutoa mazes kamilifu. Algoriti hii inavutia kwa sababu inaweza kuiga tabia ya algoriti zingine kadhaa za kutengeneza mazes, kama vile algoriti ya Prim, urejeshaji wa kurudi nyuma, na mgawanyiko wa kurudia, kulingana na jinsi unavyochagua seli inayofuata ili kusindika.

Jinsi Algorithm ya Kukua Miti Inavyofanya Kazi

Hatua ya 1: Uanzishaji

• Anza na gridi ya seli ambazo hazijatembelewa.
• Chagua seli ya kuanzia bila mpangilio na uiongeze kwenye orodha.

Hatua ya 2: Kitanzi cha Kuzalisha Maze

• Ingawa orodha ya seli si tupu: Chagua seli kutoka kwenye orodha kulingana na mkakati maalum (imeelezwa hapa chini). Chonga kifungu kutoka kwa seli iliyochaguliwa hadi kwa moja ya majirani zake ambao hawajatembelewa (kilichochaguliwa bila mpangilio). Ongeza jirani kwenye orodha kwa kuwa sasa ni sehemu ya maze. Ikiwa seli iliyochaguliwa haina majirani ambao hawajatembelewa, iondoe kwenye orodha.

Hatua ya 3: Kusitisha

• Algoritimu huisha wakati hakuna seli zaidi kwenye orodha, ikimaanisha kuwa maze nzima imechongwa.

Mikakati ya Uteuzi wa Seli (Unyumbulifu wa Algorithimu)

Kipengele kinachofafanua algoriti ya Growing Tree ni jinsi unavyochagua seli gani ya kusindika ijayo. Chaguo hili huathiri sana mwonekano wa maze:

Seli Mpya Zaidi (Tabia Inayofanana na Stack) - Kifuatiliaji Kinachojirudia:

• Chagua kila wakati seli iliyoongezwa hivi karibuni.
• Hutoa korido ndefu na zenye mikunjo zenye ncha nyingi zisizoeleweka (kama mzingile wa utafutaji wa kina cha kwanza).
• Maze huwa na njia ndefu na ni rahisi kutatua.

Seli Isiyo na Upendeleo (Algorithimu ya Prim Isiyo na Upendeleo):

• Chagua seli nasibu kutoka kwenye orodha kila wakati.
• Huunda maze iliyosambazwa sawasawa yenye njia changamano na zilizopinda.
• Korido chache ndefu na matawi zaidi.

Seli ya Kale Zaidi (Tabia Inayofanana na Foleni):

• Chagua kila wakati seli ya zamani zaidi kwenye orodha.
• Hutengeneza maze zenye umbo sawa zaidi, kama muundo wa utafutaji wa upana wa kwanza.
• Njia fupi, zenye vichaka na miunganisho minene.
• (Hili ndilo toleo linalotekelezwa hapa)

Mbinu Mseto:

Changanya mikakati ya sifa mbalimbali za maze. Kwa mfano:

• 90% mpya zaidi, 10% bila mpangilio: Inaonekana zaidi kama mzingo wa kifuatiliaji cha nyuma kinachojirudia, lakini mara kwa mara ikiwa na matawi ambayo huvunja korido ndefu.
• 50% mpya zaidi, 50% ya zamani zaidi: Husawazisha korido ndefu na ukuaji wa vichaka.

Kusoma Zaidi

Ikiwa ulifurahia chapisho hili, unaweza pia kupenda mapendekezo haya:

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