Recursive Backtracker Maze Generator

I-algorithm ye-backtracker ephindaphindwayo ngempela injongo ejwayelekile yokujula-ukusesha kokuqala. Uma isetshenziselwa isizukulwane se-maze, yaguqula kancane ukukhetha indlela ngokungahleliwe, kanti uma isetshenziselwa izinhloso zokusesha zangempela, umuntu ngokuvamile angacinga nje izinga ngalinye ngokulandelana komugqa. Ivame ukukhiqiza ama-mazes ngamaphasiji amade, ajikelezayo kanye nesisombululo eside kakhulu, esisontekile.

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-backtracker ephindaphindayo iyindlela yokusesha ejulile yokuqala yokukhiqiza ama-mazes aphelele (ama-mazes angenawo ama-loops kanye nendlela eyodwa phakathi kwanoma yimaphi amaphuzu amabili). Kuyinto elula, esebenza kahle, futhi ikhiqiza ama-mazes abonakalayo akhangayo ngamaphasiji amade, ajikelezayo.

Naphezu kwegama layo, akudingeki ukuthi isetshenziswe ngokusebenzisa ukuphindaphinda. Kuvame ukusetshenziswa ngendlela yokuphindaphinda kusetshenziswa umugqa we-LIFO (okungukuthi isitaki). Ngama-mazes amakhulu kakhulu, ukusebenzisa ukuphindaphinda kungenzeka kakhulu ukuthi kuholele ekuchichimeni kwesitaki sezingcingo, kuye ngolimi lwezinhlelo kanye nenkumbulo etholakalayo. Umugqa we-LIFO ungashintshwa kalula ekuphatheni inani elikhulu lemininingwane, ngisho nokugcina umugqa ku-disk noma ku-database uma inkumbulo ekhona inganele.

Isebenza Kanjani

I-algorithm isebenza ngokusebenzisa indlela yokusesha yokuqala yokujula okusekelwe kwisitaki. Nakhu ukuqhekeka kwesinyathelo ngesinyathelo:

1. Khetha iseli lokuqala bese uliphawula njengoba livakashelwe.
2. Ngenkathi kukhona amaseli angafakwanga:
   • Bheka amaseli angomakhelwane angakavakashelwa.
   • Uma okungenani umakhelwane oyedwa ongafakwanga ekhona:
     • Ngokungahleliwe khetha omunye womakhelwane abangafakwanga.
     • Susa udonga phakathi kweseli lamanje nomakhelwane okhethiwe.
     • Hambisa kumakhelwane okhethiwe bese uphawula njengoba uvakashelwe.
     • Sunduza iseli lamanje kusitaki.
   • Uma kungekho omakhelwane abangafakwanga abakhona:
     • Backtrack ngokuqhamuka iseli lokugcina kusuka kusitaki.
3. Qhubeka nale nqubo kuze kube yilapho isitaki singenalutho.

Iqiniso elithakazelisayo ngale algorithm ukuthi isebenza kokubili njenge-generator ye-maze futhi njengomxazululi we-maze. Uma uyigijima ku-maze esivele yenziwe futhi uvele uyeke lapho ushaya iphuzu lokuphela elinqunyiwe, isitaki sizoqukatha isisombululo ku-maze.

Empeleni nginezinguqulo ezimbili zale algorithm ezidlalwayo kule sayithi: umugqa we-LIFO osekelwe omunye wokukhiqiza ama-mazes kuleli khasi kanye nokuphindaphinda okusekelwe ekuxazululeni ama-mazes, futhi ama-mazes akhiqizwa ngamanye ama-algorithms (yindlela amabalazwe anezixazululo enziwa ngayo). Ukuba nezinguqulo ezimbili ezahlukene nje kwezemidlalo ngoba ngiyi-nerd eyithola ithakazelisa, noma ngabe ingasebenza kokubili ;-)