Kuwinda na Ua jenereta ya Maze

Algorithm ya kuwinda na kuua ni toleo lililobadilishwa la Recursive Backtracker. Marekebisho yanajumuisha kuchanganua kwa utaratibu (au "kuwinda") kwa seli mpya kuendelea kutoka wakati haiwezi kwenda mbali zaidi, kinyume na utafutaji wa kweli wa kujirudia, ambao utarejea kila mara kwenye kisanduku cha awali kwenye rafu.

Kwa sababu ya hili, algorithm hii inaweza kubadilishwa kwa urahisi ili kuzalisha mazes yenye sura na hisia tofauti, kwa kuchagua tu kuingiza hali ya "kuwinda" mara nyingi zaidi au kulingana na sheria maalum. Toleo linalotekelezwa hapa linaingia tu katika hali ya "kuwinda" wakati haliwezi kwenda mbali zaidi kutoka kwa kisanduku cha sasa.

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 Kuwinda na Kuua

Algorithm ya Kuwinda na Ua ni njia rahisi lakini yenye ufanisi ya kutengeneza maze. Inafanana kwa kiasi fulani na utafutaji wa kina wa kwanza (yaani algoriti ya Recursive Backtracker), isipokuwa wakati haiwezi kwenda mbali zaidi kutoka kwa nafasi ya sasa, inachanganua kwa utaratibu (au "kuwinda") juu ya mlolongo ili kutafuta kisanduku kipya cha kuendelea. Algorithm ina awamu mbili kuu: kutembea na uwindaji.

Jinsi Algorithm ya Kuwinda na Kuua Hufanya Kazi kwa Kizazi cha Maze

Hatua ya 1: Anza kwa seli nasibu

• Tafuta kisanduku nasibu kwenye gridi ya taifa na uweke alama kama kilitembelewa.

Hatua ya 2: Awamu ya Kutembea (Matembezi Bila mpangilio)

• Chagua jirani ambaye hajatembelewa nasibu.
• Sogea kwa jirani huyo, itie alama kuwa imetembelewa, na uchonge njia kati ya seli ya awali na mpya.
• Rudia hadi hakuna majirani ambao hawajatembelewa kushoto.

Hatua ya 3: Awamu ya Uwindaji (Kufuatilia Nyuma kupitia Uchanganuzi)

• Changanua safu mlalo ya gridi kwa safu (au safu kwa safu).
• Tafuta seli ya kwanza ambayo haijatembelewa ambayo ina angalau jirani mmoja aliyetembelewa.
• Unganisha kisanduku hicho kwa jirani aliyetembelewa ili kuendelea na hatua ya kutembea.
• Rudia hadi seli zote zimetembelewa.