Jenereta ya Maze ya Algorithm ya Wilson

Algorithm ya Wilson ni njia ya kutembea bila mpangilio ambayo hutoa miti ya sare kwa uumbaji wa maze. Hii inamaanisha kuwa mazes zote zinazowezekana za saizi fulani zina uwezekano sawa wa kuzalishwa, na kuifanya kuwa mbinu ya kizazi cha maze isiyo na upendeleo. Algorithm ya Wilson inaweza kuchukuliwa kuwa toleo bora la algorithm ya Aldous-Broder, kwani inazalisha mazes na sifa zinazofanana, lakini inaendesha haraka sana, kwa hivyo sijasumbua kutekeleza algorithm 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 Algorithm ya Wilson

Algorithm ya Wilson ya kuzalisha miti ya sare ya kutandaza kwa kutumia ukuta wa nasibu wa kitanzi iliundwa na David Bruce Wilson.

Wilson awali ilianzisha algorithm hii katika 1996 wakati wa kutafiti miti ya muda mrefu na minyororo ya Markov katika nadharia ya uwezekano. Ingawa kazi yake ilikuwa hasa katika hisabati na fizikia ya takwimu, algorithm tangu wakati huo imekuwa ikichukuliwa sana kwa kizazi cha maze kutokana na uwezo wake wa kuzalisha mazes sare kamili.

Jinsi Algorithm ya Wilson inavyofanya kazi kwa Kizazi cha Maze

Algorithm ya Wilson inahakikisha kuwa maze ya mwisho imeunganishwa kikamilifu bila kitanzi chochote kwa njia za kuchora kutoka kwa seli zisizotembelewa kwa kutumia matembezi ya nasibu.

Hatua ya 1: Kuanzisha

• Anza na gridi ya taifa iliyojazwa na kuta.
• Fafanua orodha ya seli zote zinazowezekana za kifungu.

Hatua ya 2: Chagua Seli ya Kuanza bila mpangilio

• Chagua seli yoyote ya nasibu na uweke alama kama ilivyotembelewa. Hii hutumika kama mwanzo wa maze wakati wa kizazi.

Hatua ya 3: Kutembea bila mpangilio na Loop-Erasing

• Chagua seli isiyotembelewa na uanze kutembea bila mpangilio (kusonga kwa mwelekeo wa nasibu).
• Ikiwa matembezi yanafikia seli iliyotembelewa tayari, futa kitanzi chochote kwenye njia.
• Mara tu matembezi yanapounganisha kwenye eneo lililotembelewa, weka alama kwenye seli zote kwenye njia kama ilivyotembelewa.

Hatua ya 4: Rudia mpaka seli zote zitembelewe:

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