Recursive Backtracker Maze Generator

I-algorithm ye-recursive backtracker empeleni iwukusesha okujulile kwenhloso evamile. Uma isetshenziselwa ukukhiqiza i-maze, ishintshe kancane ukuze ikhethe indlela ngokungahleliwe, kanti uma isetshenziselwa izinjongo zokusesha zangempela, umuntu uvame ukusesha izinga ngalinye ngokulandelana okuqondile. Ivame ukukhiqiza ama-maze anezindlela ezinde, ezigobile kanye nesisombululo eside kakhulu, esigobile.

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.

I-algorithm ye-recursive backtracker iyindlela yokusesha ejulile yokuqala yokukhiqiza ama-maze aphelele (ama-maze angenazo izihibe kanye nendlela eyodwa phakathi kwamaphuzu amabili). Ilula, iyasebenza kahle, futhi ikhiqiza ama-maze akhangayo abonakala kahle anemizila emide, egobile.

Naphezu kwegama layo, akudingeki ukuthi isetshenziswe kusetshenziswa i-recursion. Ivame ukusetshenziswa ngendlela ephindaphindayo kusetshenziswa umugqa we-LIFO (okungukuthi i-stack). Kuma-maze amakhulu kakhulu, ukusebenzisa i-recursion kungenzeka kakhulu ukuthi kuholele ekugcwaleni kwe-call stack, kuye ngolimi lohlelo kanye nememori etholakalayo. Umugqa we-LIFO ungashintshwa kalula ukuze uphathe idatha eningi, ngisho nokugcina umugqa kudiski noma kudathabheyisi uma imemori etholakalayo inganele.

Indlela Esebenza Ngayo

I-algorithm isebenza kusetshenziswa indlela yokusesha ngokujulile okusekelwe ku-stack. Nasi ukuhlukaniswa kwesinyathelo ngesinyathelo:

1. Khetha iseli lokuqala bese ulimaka njengelivakashelwe.
2. Ngenkathi kukhona amaseli angavakashelwanga: Bheka amaseli angomakhelwane angakavakashelwa. Uma okungenani umakhelwane oyedwa ongakavakashelwa ekhona: Khetha ngokungahleliwe omunye womakhelwane abangakavakashelwa. Susa udonga phakathi kweseli yamanje nomakhelwane okhethiwe. Yiya kumakhelwane okhethiwe bese uwumaka njengovakashelwe. Cindezela iseli yamanje esitaki. Uma kungekho omakhelwane abangakavakashelwa abakhona: Buyela emuva ngokukhipha iseli lokugcina esitaki.
3. Qhubeka nale nqubo kuze kube yilapho isitaki singenalutho.

Iqiniso elithakazelisayo ngale algorithm ukuthi isebenza kokubili njengejeneretha ye-maze kanye ne-solver ye-maze. Uma uyiqhuba ku-maze esevele yenziwe bese uyama lapho ufika endaweni yokugcina enqunyiwe, i-stack izoqukatha ikhambi le-maze.

Empeleni nginezinhlobo ezimbili zale algorithm ezisetshenziswayo kulesi siza: umugqa we-LIFO osuselwe ekukhiqizeni ama-maze kuleli khasi kanye nowe-recursion osuselwe ekuxazululeni ama-maze, kanye nama-maze akhiqizwe amanye ama-algorithm (yileyo ndlela amamephu anezixazululo enziwa ngayo). Ukuba nezinguqulo ezimbili ezihlukene kungokwezemidlalo ngoba ngingumuntu ofundayo okuthola kuthakazelisa, noma yikuphi bekungasebenza kokubili ;-)

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