Hunt futhi Kill Maze Generator

I-algorithm ye-Hunt and Kill empeleni iyinguqulo eguquliwe ye-Recursive Backtracker. Ukuguqulwa kuqukethe ukuskena okuhlelekile (noma "ukuzingela") iseli elisha ukuze liqhubeke kusukela lapho lingakwazi ukuya phambili, ngokungafani nokusesha okuphindaphindwayo kwangempela, okuzohlala kubuyela kuseli langaphambilini esitaki.

Ngenxa yalokhu, le algorithm ingashintshwa kalula ukuze ikhiqize ama-maze anokubukeka nokuzwakala okuhlukile, ngokukhetha nje ukungena kwimodi "yokuzingela" kaningi noma ngokwemithetho ethile. Inguqulo esetshenziswa lapha ingena kuphela kwimodi "yokuzingela" uma ingenakukwazi ukuya kude neseli yamanje.

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 Yokuzingela Nokubulala

I-algorithm ye-Hunt and Kill iyindlela elula kodwa ephumelelayo yokwenza ama-maze. Ifana kancane nokusesha okujulile (okungukuthi i-algorithm ye-Recursive Backtracker), ngaphandle kokuthi uma ingakwazi ukuya phambili kusuka endaweni yamanje, iskena ngokuhlelekile (noma "izingela") phezu kwe-maze ukuthola iseli elisha elizoqhubeka nalo. I-algorithm inezigaba ezimbili eziyinhloko: ukuhamba nokuzingela.

Indlela i-Hunt and Kill Algorithm esebenza ngayo ku-Maze Generation

Isinyathelo 1: Qala kuseli elingahleliwe

• Thola iseli elingahleliwe kugridi bese ulimaka njengelivakashelwe.

Isinyathelo 2: Isigaba Sokuhamba (Ukuhamba Okungahleliwe)

• Khetha umakhelwane ongavakashelwa ngokungahleliwe.
• Yiya kulowo makhelwane, umake njengovakashelwe, bese uqopha indlela phakathi kweseli langaphambilini neseli elisha.
• Phinda kuze kube yilapho kungekho omakhelwane abangavakashelwanga abasele.

Isinyathelo 3: Isigaba Sokuzingela (Ukulandelela Ngokusebenzisa Ukuskena)

• Skena umugqa wegridi ngomugqa (noma ikholomu ngekholomu).
• Thola iseli lokuqala elingavakashelwa elinomakhelwane oyedwa okungenani ovakashelwe.
• Xhuma leyo seli kumakhelwane ovakashelwe ukuze uqalise kabusha isigaba sokuhamba.
• Phinda kuze kube yilapho wonke amaseli esevakashelwe.

Ukufunda Okuqhubekayo

Uma ukujabulele lokhu okuthunyelwe, ungaphinda uthande lezi ziphakamiso:

• Recursive Backtracker Maze Generator
• Wilson sika Algorithm Maze Generator
• Kruskal sika Algorithm Maze Generator