Jenereta ya Maze ya Algorithm ya Wilson

Algoritimu ya Wilson ni mbinu ya kutembea bila mpangilio inayofutwa kitanzi ambayo hutoa miti yenye upana sawa kwa ajili ya uundaji wa maze. Hii ina maana kwamba maze zote zinazowezekana za ukubwa fulani zina uwezekano sawa wa kuzalishwa, na kuifanya kuwa mbinu ya kutengeneza maze isiyo na upendeleo. Algoritimu ya Wilson inaweza kuchukuliwa kuwa toleo lililoboreshwa la algoritimu ya Aldous-Broder, kwani hutoa maze zenye sifa zinazofanana, lakini inafanya kazi kwa kasi zaidi, kwa hivyo sijajisumbua kutekeleza algoriti ya Aldous-Broder hapa.

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 Algorithimu ya Wilson

Algoritimu ya Wilson ya kutengeneza miti yenye upana sawa kwa kutumia ukuta nasibu uliofutwa kwa kitanzi iliundwa na David Bruce Wilson.

Wilson alianzisha algoriti hii mwanzoni mwaka wa 1996 alipokuwa akitafiti miti inayozunguka bila mpangilio na minyororo ya Markov katika nadharia ya uwezekano. Ingawa kazi yake ilikuwa hasa katika hisabati na fizikia ya takwimu, algoriti hiyo imetumika sana kwa ajili ya uzalishaji wa maze kutokana na uwezo wake wa kutoa maze zinazofanana kikamilifu.

Jinsi Algorithm ya Wilson Inavyofanya Kazi kwa Kizazi cha Maze

Algoritimu ya Wilson inahakikisha kwamba maze ya mwisho imeunganishwa kikamilifu bila mizunguko yoyote kwa kuchonga njia mara kwa mara kutoka kwa seli ambazo hazijatembelewa kwa kutumia matembezi ya nasibu.

Hatua ya 1: Anzisha

• Anza na gridi iliyojaa kuta.
• Bainisha orodha ya seli zote zinazowezekana za kupitisha.

Hatua ya 2: Chagua Seli ya Kuanza Bila Kupangilia

• Chagua seli yoyote nasibu na uiweke alama kama imetembelewa. Hii hutumika kama mahali pa kuanzia pa maze wakati wa kizazi.

Hatua ya 3: Kutembea Bila Kutarajia kwa Kufuta Kitanzi

• Chagua seli ambayo haijatembelewa na uanze kutembea bila mpangilio (kusonga katika pande zisizo na mpangilio).
• Ikiwa njia ya kutembea itafikia seli ambayo tayari imetembelewa, futa vitanzi vyovyote kwenye njia.
• Mara tu matembezi yanapounganishwa na eneo lililotembelewa, weka alama kwenye seli zote kwenye njia kama zilizotembelewa.

Hatua ya 4: Rudia Hadi Seli Zote Zitembelewe:

• Endelea kuchagua seli ambazo hazijatembelewa na kufanya matembezi ya nasibu hadi kila seli iwe sehemu ya maze.

Kusoma Zaidi

Ikiwa ulifurahia chapisho hili, unaweza pia kupenda mapendekezo haya:

• Kuongezeka kwa Jenereta ya Maze ya Algorithm ya Miti
• Kuwinda na Ua jenereta ya Maze
• Jenereta ya Maze ya Backtracker ya Kujirudia