Manghuli at Patayin ang Maze Generator
Nai-publish: Marso 19, 2025 nang 8:44:45 PM UTC
Maze generator gamit ang Hunt and Kill algorithm upang lumikha ng perpektong maze. Ang algorithm na ito ay katulad ng Recursive Backtracker, ngunit may posibilidad na bumuo ng mga maze na medyo hindi gaanong mahaba, paikot-ikot na mga corridor.Hunt and Kill Maze Generator
Ang Hunt and Kill algorithm ay talagang isang binagong bersyon ng Recursive Backtracker. Binubuo ang pagbabago ng sistematikong pag-scan (o "pangangaso") para sa isang bagong cell na magpatuloy mula sa kung kailan hindi na ito magpapatuloy, kumpara sa isang tunay na recursive na paghahanap, na palaging babalik sa nakaraang cell sa stack.
Dahil dito, madaling maiangkop ang algorithm na ito upang makabuo ng mga maze na may iba't ibang hitsura at pakiramdam, sa pamamagitan lamang ng pagpili na pumasok sa "hunting" mode nang mas madalas o ayon sa mga partikular na panuntunan. Ang bersyon na ipinatupad dito ay pumapasok lamang sa mode na "pangangaso" kapag hindi na ito makalayo sa kasalukuyang cell.
Ang perpektong maze ay isang maze kung saan mayroong eksaktong isang landas mula sa anumang punto sa maze hanggang sa anumang iba pang punto. Nangangahulugan iyon na hindi ka maaaring maglibot sa mga bilog, ngunit madalas kang makatagpo ng mga patay na dulo, na pinipilit kang tumalikod at bumalik.
Ang mga mapa ng maze na nabuo dito ay may kasamang default na bersyon nang walang anumang mga posisyon sa pagsisimula at pagtatapos, kaya maaari kang magpasya para sa iyong sarili: magkakaroon ng solusyon mula sa anumang punto sa maze hanggang sa anumang iba pang punto. Kung gusto mo ng inspirasyon, maaari mong paganahin ang isang iminungkahing posisyon sa pagsisimula at pagtatapos - at kahit na makita ang solusyon sa pagitan ng dalawa.
Tungkol sa Hunt and Kill Algorithm
Ang Hunt and Kill algorithm ay isang simple ngunit epektibong paraan para lumikha ng mga maze. Medyo katulad ito ng depth-first search (o ang Recursive Backtracker algorithm), maliban na kapag hindi na ito makakapagpatuloy mula sa kasalukuyang posisyon, sistematikong tinitingnan (o "hinahanap") nito ang maze upang makakita ng bagong cell na maaaring pagpatuluyan. Ang algorithm ay binubuo ng dalawang pangunahing yugto: ang paglalakad at ang panghuhunting.
Paano Gumagana ang Hunt and Kill Algorithm para sa Paglikha ng Maze
Hakbang 1: Magsimula sa isang random na cell
- Maghanap ng isang random na cell sa grid at markahan ito bilang nabisita.
Hakbang 2: Yugto ng Paglalakad (Random na Paglakad)
- Pumili ng isang random na hindi nabisitang kapitbahay.
- Maglakbay patungo sa kapitbahay na iyon, markahan ito bilang nabisita, at mag-ukit ng daan sa pagitan ng nakaraang cell at bagong cell.
- Ulitin hanggang wala nang hindi nabisitang kapitbahay.
Hakbang 3: Yugto ng Panghuhunting (Backtracking sa Pamamagitan ng Pagsusuri)
- I-scan ang grid ng row sa row (o column sa column).
- Hanapin ang unang hindi nabisitang cell na may kahit isang nabisitang kapitbahay.
- I-konekta ang cell na iyon sa isang nabisitang kapitbahay upang ipagpatuloy ang yugto ng paglalakad.
- Ulitin hanggang lahat ng cell ay nabisita na.