Ukukhula Tree Algorithm Maze Generator

I-algorithm Yesihlahla Esikhulayo iyathakazelisa, ngoba ingalingisa ukuziphatha kwamanye ama-algorithms ambalwa, kuye ngokuthi iseli elilandelayo likhethwa kanjani ngesikhathi sokukhiqiza. Ukuqaliswa kuleli khasi kusebenzisa indlela yobubanzi-kuqala, 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 Yesihlahla Esikhulayo

I-algorithm Yesihlahla Esikhulayo iyindlela eguquguqukayo nenamandla yokukhiqiza ama-maze aphelele. I-algorithm iyathakazelisa ngoba ingalingisa ukuziphatha kwamanye ama-algorithms esizukulwane se-maze, njenge-algorithm ye-Prim, i-recursive backtracking, nokuhlukaniswa okuphindaphindayo, kuye ngokuthi ukhetha kanjani iseli elilandelayo ozolicubungula.

Indlela I-algorithm Yesihlahla Esikhulayo Esebenza Ngayo

Isinyathelo 1: Ukuqalisa

• Qala ngegridi yamaseli angavakashelwa.
• Khetha iseli eqala ngokungahleliwe bese uyengeza ohlwini.

Isinyathelo sesi-2: I-Maze Generation Loop

• Ngenkathi uhlu lwamaseli lungenalutho:
  • Khetha iseli ohlwini ngokusekelwe kuqhinga elithile (elichazwe ngezansi).
  • Baza iphaseji elisuka kuseli elikhethiwe liye komunye womakhelwane abangavakashelwanga (okhethwe ngokungahleliwe).
  • Engeza umakhelwane ohlwini njengoba manje isiyingxenye ye-maze.
  • Uma iseli elikhethiwe lingenabo omakhelwane abangavakashelwa, lisuse ohlwini.

Isinyathelo sesi-3: Ukunqanyulwa

• I-algorithm iyaphela lapho engasekho amaseli ohlwini, okusho ukuthi yonke i-maze iqoshiwe.

Amasu Okukhethwa Kweseli (Ukuguquguquka kwe-algorithm)

Isici esichazayo se-algorithm Yesihlahla Esikhulayo yindlela okhetha ngayo ukuthi yiliphi iseli ozolicubungula ngokulandelayo. Lokhu kukhetha kuthinta kakhulu ukubukeka kwe-maze:

Iseli Entsha Kakhulu (Ukuziphatha Okufana Nesitaki) - I-Recursive Backtracker:

• Njalo khetha iseli esanda kufakwa.
• Ikhiqiza amaphasishi amade, asontekile aneziphetho eziningi ezifile (njenge-deep-first maze yokusesha).
• Ama-Mazes avame ukuba namaphaseji amade futhi kulula ukuwaxazulula.

Iseli Engahleliwe (I-algorithm ye-Prim Engahleliwe):

• Khetha iseli engahleliwe ohlwini isikhathi ngasinye.
• Idala imaze esabalaliswe ngokulinganayo enemizila eyinkimbinkimbi, ephithene.
• Amaphasishi amade ambalwa kanye namagatsha amaningi.

Iseli Elidala Kakhulu (Ukuziphatha Okufana Nomugqa):

• Njalo khetha iseli elidala kakhulu ohlwini.
• Ikhiqiza ama-maze ngokusabalalisa okufanayo, njengephethini yokusesha yobubanzi bokuqala.
• Amaphasishi amafushane, anamahlathi anoxhumano oluminyene.
• (Le yinguqulo esetshenziswe lapha)

Izindlela ezihlanganisiwe:

Hlanganisa amasu ezici ezihlukahlukene ze-maze. Ngokwesibonelo:

• Okusha okungu-90%, okungu-10% okungahleliwe: Kubukeka kakhulu njenge-maze ye-backtracker ephindaphindayo, kodwa ngamagatsha ezikhathi ezithile aqhekeza amaphasishi amade.
• Okusha okungu-50%, okungu-50% kwakudala: Ibhalansisa amaphasishi amade nokukhula okunehlathi.