Ukukhula Tree Algorithm Maze Generator

I-algorithm ye-Growing Tree iyathakazelisa, ngoba ingalingisa ukuziphatha kwamanye ama-algorithms amaningana, kuye ngokuthi iseli elilandelayo likhethwa kanjani ngesikhathi sokukhiqiza. Ukusetshenziswa kuleli khasi kusebenzisa indlela efana nobubanzi bokuqala, efana nomugqa.

I-maze ephelele i-maze lapho kukhona indlela eyodwa ncamashi ukusuka kunoma iyiphi indawo ku-maze ukuya kunoma iyiphi enye indawo. Lokho kusho ukuthi ngeke ugcine usuzungeza emibuthanweni, kodwa uzohlangana nezinto ezifile, okuphoqa ukuthi ujike uphinde ubuyele emuva.

Amamephu we-maze akhiqizwe lapha afaka inguqulo ezenzakalelayo ngaphandle kwanoma yiziphi izindawo zokuqala nokuqeda, ukuze ukwazi ukuzinqumela lokho: kuzoba nesixazululo kusuka kunoma iyiphi indawo ku-maze kuya kunoma iyiphi enye indawo. Uma ufuna ugqozi, ungavumela indawo yokuqala neyokuqeda ephakanyisiwe - futhi ubone ngisho nesixazululo phakathi kwakho kokubili.

Mayelana ne-Algorithm Yokukhula Kwesihlahla

I-algorithm ye-Growing Tree iyindlela eguquguqukayo nenamandla yokukhiqiza ama-maze aphelele. I-algorithm iyathakazelisa ngoba ingalingisa ukuziphatha kwamanye ama-algorithms amaningi okukhiqiza ama-maze, njenge-algorithm ka-Prim, i-recursive backtracking, kanye ne-recursive division, kuye ngokuthi ukhetha kanjani iseli elilandelayo ukuze ulicubungule.

Indlela I-Algorithm Yokukhulisa Isihlahla Esebenza Ngayo

Isinyathelo 1: Ukuqalisa

• Qala ngegridi yamaseli angavakashelwanga.
• Khetha iseli lokuqala elingahleliwe bese ulifaka ohlwini.

Isinyathelo 2: I-Maze Generation Loop

• Nakuba uhlu lwamaseli lungenalutho: Khetha iseli ohlwini ngokusekelwe isu elithile (elichazwe ngezansi). Bhala isiqephu esivela kuseli elikhethiwe siye komunye womakhelwane balo abangavakashelwanga (okhethwe ngokungahleliwe). Engeza umakhelwane ohlwini njengoba manje useyingxenye ye-maze. Uma iseli elikhethiwe lingenabo omakhelwane abangavakashelwanga, lisuse ohlwini.

Isinyathelo 3: Ukuqeda

• I-algorithm iphela uma kungasekho amanye amaseli ohlwini, okusho ukuthi yonke i-maze isiqoshiwe.

Amasu Okukhetha Amaseli (Ukuguquguquka kwe-Algorithm)

Isici esichazayo se-algorithm ye-Growing Tree ukuthi ukhetha kanjani ukuthi yiliphi iseli ozolicubungula ngokulandelayo. Lokhu kukhetha kuthinta kakhulu ukubukeka kwe-maze:

Iseli Elisha Kakhulu (Ukuziphatha Okufana Ne-Stack) - I-Recursive Backtracker:

• Khetha njalo iseli elisanda kufakwa.
• Ikhiqiza imihubhe emide, egobile eneziphetho eziningi ezingenakufinyeleleka (njenge-maze yokusesha ejulile kuqala).
• Ama-maze avame ukuba nezindlela ezinde futhi kulula ukuwaxazulula.

Iseli Engahleliwe (I-Algorithm kaPrim Engahleliwe):

• Khetha iseli elingahleliwe ohlwini isikhathi ngasinye.
• Idala i-maze esakazeke ngokulinganayo enezindlela eziyinkimbinkimbi nezixakile.
• Imizila emifushane embalwa kanye namagatsha amaningi.

Iseli Elidala Kunawo Wonke (Ukuziphatha Okufana Nomugqa):

• Khetha njalo iseli elidala kunawo wonke ohlwini.
• Idala ama-maze anokusabalala okufanayo, njengephethini yokusesha enobubanzi bokuqala.
• Izindlela ezimfushane, ezinamahlathi ezinezixhumanisi ezixineneyo.
• (Lena inguqulo esetshenziswe lapha)

Izindlela Ezihlanganisiwe:

Hlanganisa amasu ezicini ezahlukahlukene ze-maze. Isibonelo:

• Okusha kakhulu okungu-90%, okungahleliwe okungu-10%: Kubukeka kakhulu njenge-maze ye-backtracker ephindaphindayo, kodwa ngezikhathi ezithile kunamagatsha ahlukanisa imihubhe emide.
• 50% entsha, 50% endala: Ilinganisela imihubhe emide nokukhula okunamahlumela.

Ukufunda Okuqhubekayo

Uma ukujabulele lokhu okuthunyelwe, ungaphinda uthande lezi ziphakamiso:

• Isibali sekhodi sehashi Eller's Algorithm Maze Generator
• Hunt futhi Kill Maze Generator
• Kruskal sika Algorithm Maze Generator