Kuongezeka kwa Jenereta ya Maze ya Algorithm ya Miti

Algorithm ya Kukua kwa Mti ni ya kuvutia, kwa sababu inaweza kuiga tabia ya algorithms nyingine kadhaa, kulingana na jinsi seli inayofuata huchaguliwa wakati wa kizazi. Utekelezaji kwenye ukurasa huu hutumia njia 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 Kupanda kwa Mti

Algorithm ya Kupanda Mti ni njia rahisi na yenye nguvu ya kuzalisha mazes kamili. Algorithm ni ya kuvutia kwa sababu inaweza kuiga tabia ya algorithms nyingine kadhaa za kizazi cha maze, kama vile algorithm ya Prim, kurudia nyuma, na mgawanyiko wa kurudia, kulingana na jinsi unavyochagua seli inayofuata ya mchakato.

Jinsi Algorithm ya Kupanda ya Mti inavyofanya kazi

Hatua ya 1: Kuanzisha

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

Hatua ya 2: Loop ya Kizazi cha Maze

• Wakati orodha ya seli sio tupu:
  • Chagua seli kutoka kwenye orodha kulingana na mkakati maalum (uliofafanuliwa hapa chini).
  • Weka kifungu kutoka kwa seli iliyochaguliwa hadi kwa mmoja wa majirani zake ambao hawajatembelewa (waliochaguliwa kwa nasibu).
  • Ongeza jirani kwenye orodha kwani sasa ni sehemu ya maze.
  • Ikiwa seli iliyochaguliwa haina majirani ambao hawajatembelewa, iondoe kwenye orodha.

Hatua ya 3: Kukomesha

• Algorithm inamaliza wakati hakuna seli zaidi kwenye orodha, ikimaanisha maze nzima imechongwa.

Mikakati ya Uchaguzi wa Seli (Uwezekano wa Algorithm)

Kipengele kinachofafanua cha algorithm ya Mti wa Kukua ni jinsi unavyochagua seli gani ya kuchakata ijayo. Chaguo hili linaathiri sana muonekano wa maze:

Seli Mpya zaidi (Tabia kama ya Stack) - Backtracker ya Kujirudia:

• Daima chagua seli iliyoongezwa hivi karibuni.
• Inazalisha njia ndefu, za kupotosha na ncha nyingi zilizokufa (kama maze ya utafutaji wa kwanza).
• Mazes huwa na vifungu virefu na ni rahisi kutatua.

Seli ya nasibu (Algorithm ya Prim ya Randomized):

• Chagua seli ya nasibu kutoka kwenye orodha kila wakati.
• Huunda maze iliyosambazwa kwa usawa na njia ngumu, zilizopigwa.
• Njia chache za muda mrefu na matawi zaidi.

Seli ya zamani zaidi (Tabia kama ya Queue):

• Daima chagua seli ya zamani zaidi kwenye orodha.
• Inazalisha mazes na kuenea zaidi sare, kama muundo wa utafutaji wa kwanza wa upana.
• Njia fupi, zenye vichaka na unganisho nene.
• (Hii ni tafsiri ya toleo lililotekelezwa hapa)

Njia za mseto:

Unganisha mikakati ya sifa anuwai za maze. Kwa mfano:

• 90% mpya zaidi, 10% ya nasibu: Inaonekana zaidi kama maze ya nyuma ya kurudia, lakini kwa matawi ya mara kwa mara ambayo huvunja barabara ndefu.
• 50% mpya zaidi, 50% ya zamani: Mizani ya ukanda mrefu na ukuaji wa bushy.