Kuwinda na Ua jenereta ya Maze

Algoriti ya Hunt and Kill ni toleo lililobadilishwa la Recursive Backtracker. Marekebisho hayo yanajumuisha kuchanganua kimfumo (au "uwindaji") kwa seli mpya ili kuendelea kutoka wakati haiwezi kuendelea zaidi, tofauti na utafutaji wa kweli wa recursive, ambao utarudi kwenye seli iliyopita kwenye rundo.

Kwa sababu hii, algoriti hii inaweza kubadilishwa kwa urahisi ili kutoa maze zenye mwonekano na hisia tofauti, kwa kuchagua tu kuingia katika hali ya "uwindaji" mara nyingi zaidi au kulingana na sheria maalum. Toleo linalotekelezwa hapa huingia tu katika hali ya "uwindaji" wakati haliwezi kwenda mbali zaidi kutoka kwa seli ya 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

Algoritimu ya Kuwinda na Kuua ni njia rahisi lakini yenye ufanisi ya kutengeneza maze. Inafanana kwa kiasi fulani na utafutaji wa kina (yaani algoritimu ya Kurudia Nyuma), isipokuwa pale ambapo haiwezi kwenda mbali zaidi kutoka kwenye nafasi ya sasa, huchanganua kwa utaratibu (au "kuwinda") juu ya maze ili kupata seli mpya ya kuendelea nayo. Algoritimu hii ina awamu mbili kuu: kutembea na kuwinda.

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

Hatua ya 1: Anza kwenye seli isiyo na mpangilio

• Tafuta seli nasibu kwenye gridi na uweke alama kama imetembelewa.

Hatua ya 2: Awamu ya Kutembea (Kutembea Bila Kutarajia)

• Chagua jirani ambaye hajatembelewa bila mpangilio.
• Sogea kwa jirani huyo, tia alama kama ametembelea, na chonga njia kati ya seli iliyotangulia na mpya.
• Rudia hadi kusiwe na majirani wasiotembelewa waliobaki.

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

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

Kusoma Zaidi

Ikiwa ulifurahia chapisho hili, unaweza pia kupenda mapendekezo haya:

• Kuongezeka kwa Jenereta ya Maze ya Algorithm ya Miti
• Jenereta ya Maze ya Algorithm ya Eller
• Jenereta ya Maze ya Algorithm ya Wilson