Hunt futhi Kill Maze Generator

I-algorithm ye-Hunt and Kill ngempela inguqulo eguquliwe ye-Recursive Backtracker. Ukuguqulwa kuqukethe ukuskena ngokuhlelekile (noma "ukuzingela") ukuze iseli elisha liqhubeke kusukela lapho lingakwazi ukuqhubekela phambili, ngokuphambene nokusesha kweqiniso okuphindaphindiwe, okuzohlala kubuyela esitokisini sangaphambilini esitakini.

Ngenxa yalokhu, le algorithm ingashintshwa kalula ukukhiqiza ama-mazes ngokubukeka okuhlukile nokuzizwa, ngokukhetha nje ukungena kwimodi "yokuzingela" kaningi noma ngokwemithetho ethile. Inguqulo eyenziwe lapha ingena kuphela kwimodi "yokuzingela" lapho ingakwazi ukuqhubekela phambili kusuka esitokisini samanje.

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-Hunt and Kill Algorithm

I-algorithm ye-Hunt and Kill iyindlela elula kodwa ephumelelayo yokukhiqiza ama-mazes. Kufana ngandlela-thile nokusesha okujulile kokuqala (okungukuthi i-algorithm ye-Recursive Backtracker), ngaphandle kwalapho ingakwazi ukuqhubekela phambili kusuka endaweni yamanje, ihlola ngokuhlelekile (noma "ukuzingela") phezu kwe-maze ukuthola iseli elisha lokuqhubeka kusuka. I-algorithm iqukethe izigaba ezimbili eziyinhloko: ukuhamba nokuzingela.

I-Hunt and Kill Algorithm isebenza kanjani ku-Maze Generation

Isinyathelo 1: Qala esitokisini esingahleliwe

• Thola iseli elingahleliwe kugridi bese uliphawula njengoba livakashelwe.

Isinyathelo 2: Isigaba Sokuhamba (Ukuhamba Okungahleliwe)

• Khetha umakhelwane ongahleliwe ongahleliwe.
• Hambisa kulowo makhelwane, uphawule njengoba uvakashelwe, bese uqopha indlela phakathi kweseli langaphambilini nelisha.
• Phinda kuze kube yilapho kungekho omakhelwane abangafakwanga abasele.

Isinyathelo 3: Isigaba Sokuzingela (Ukubuyela emuva nge-Scanning)

• Skena umugqa wegridi ngomugqa (noma ikholomu ngekholomu).
• Thola iseli lokuqala elingafakwanga elinomakhelwane okungenani oyedwa ovakashelwe.
• Xhuma lelo seli kumakhelwane ovakashelwe ukuze uqale kabusha isigaba sokuhamba.
• Phinda kuze kube yilapho wonke amaseli evakashelwe.