Wilson sika Algorithm Maze Generator

I-algorithm kaWilson iyindlela yokuhamba ngokungahleliwe esuswa ngendlela ejikelezayo ekhiqiza izihlahla ezibanzi ezifanayo zokudala i-maze. Lokhu kusho ukuthi wonke ama-maze angaba khona osayizi othile cishe angadalwa ngokulinganayo, okwenza kube yindlela yokwenza i-maze engachemile. I-algorithm kaWilson ingabhekwa njengenguqulo ethuthukisiwe ye-algorithm ka-Aldous-Broder, njengoba ikhiqiza ama-maze anezici ezifanayo, kodwa isebenza ngokushesha okukhulu, ngakho angizange ngikhathazeke ngokusebenzisa i-algorithm ka-Aldous-Broder lapha.

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 kaWilson

I-algorithm kaWilson yokukhiqiza izihlahla ezibanzi ezifanayo kusetshenziswa udonga olungahleliwe olusulwe ngeluphu yadalwa nguDavid Bruce Wilson.

UWilson waqala ukwethula le algorithm ngo-1996 ngenkathi ecwaninga ngezihlahla ezihlukanisa ngokungahleliwe kanye namaketanga kaMarkov ku-probability theory. Nakuba umsebenzi wakhe wawugxile kakhulu kwizibalo kanye ne-physics yezibalo, le algorithm iye yamukelwa kabanzi ekwakhiweni kwe-maze ngenxa yekhono layo lokukhiqiza ama-maze afanayo ngokuphelele.

Indlela i-Algorithm kaWilson esebenza ngayo ku-Maze Generation

I-algorithm kaWilson iqinisekisa ukuthi i-maze yokugcina ixhunywe ngokugcwele ngaphandle kwanoma yiziphi izihibe ngokusika izindlela eziphindaphindwayo kusuka kumaseli angavakashelwa kusetshenziswa ukuhamba okungahleliwe.

Isinyathelo 1: Qalisa

• Qala ngegridi egcwele izindonga.
• Chaza uhlu lwawo wonke amaseli okudlula okungenzeka.

Isinyathelo 2: Khetha Iseli Lokuqala Elingahleliwe

• Khetha noma yiliphi iseli elingahleliwe bese ulimaka njengelivakashelwe. Lokhu kusebenza njengendawo yokuqala ye-maze ngesikhathi sokukhiqizwa.

Isinyathelo 3: Ukuhamba Okungahleliwe Ngokusula I-Loop

• Khetha iseli elingavakashelwanga bese uqala ukuhamba ngokungahleliwe (ukuhamba ngezindlela ezingahleliwe).
• Uma ukuhamba kufinyelela kuseli elivele livakashelwe, susa noma yiziphi izihibe endleleni.
• Uma uhambo luxhumene nendawo evakashelwe, maka wonke amaseli asendleleni njengoba evakashelwe.

Isinyathelo 4: Phinda Kuze Kube Wonke Amaseli Avakashelwe:

• Qhubeka ukhetha amaseli angavakashelwanga futhi wenze ukuhamba okungahleliwe kuze kube yilapho iseli ngalinye liyingxenye ye-maze.

Ukufunda Okuqhubekayo

Uma ukujabulele lokhu okuthunyelwe, ungaphinda uthande lezi ziphakamiso:

• Hunt futhi Kill Maze Generator
• Ukukhula Tree Algorithm Maze Generator
• Recursive Backtracker Maze Generator