Ang Algorithm Maze Generator ni Eller

Ang algorithm ni Eller ay isang algorithm ng pagbuo ng maze na mahusay na gumagawa ng mga perpektong maze (mga maze na walang mga loop at isang solong landas sa pagitan ng alinmang dalawang punto) gamit ang isang row-by-row na diskarte. Gumagawa ito ng mga maze na katulad ng algorithm ng Kruskal, ngunit ginagawa nito ito sa pamamagitan ng pagbuo lamang ng isang hilera sa isang pagkakataon, nang hindi nangangailangan ng pag-imbak ng buong maze sa memorya. Ginagawa nitong kapaki-pakinabang para sa pagbuo ng napakalaking maze sa napakalimitadong mga system at para sa pagbuo ng nilalamang pamamaraan.

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 Algoritmo ni Eller

Ang Algoritmo ni Eller ay ipinakilala ni David Eller.

Ang algoritmong ito ay kilala sa kanyang mabisang pamamaraang row-by-row sa pagbuo ng maze, na ginagawa itong perpekto para sa mga walang katapusang maze o mga maze na nabubuo sa real-time. Madalas itong binabanggit sa mga literatura tungkol sa procedural content generation at maze-generation, ngunit hindi ko nahanap ang mga pangunahing pinagkukunan na naglalarawan ng orihinal nitong publikasyon.

Paano Gumagana ang Algoritmo ni Eller sa Pagbuo ng Maze

Ang algoritmo ni Eller ay nagproseso ng isang hilera nang paisa-isa, pinapanatili at binabago ang mga set ng mga magkakaugnay na cells. Tinitiyak nito ang konektividad habang iniiwasan ang mga loop, at mabisang pinapalawak ang maze pababa.

Teoretikal, maaari itong gamitin upang bumuo ng mga walang katapusang maze, ngunit upang matiyak na ang nabuo na maze ay talagang malulutas, kinakailangan na lumipat sa "final row" logic sa isang punto upang tapusin ang maze.

Hakbang 1: I-initialize ang Unang Hilerang

• Magtalaga ng natatanging set ID sa bawat cell sa hilera.

Hakbang 2: Pagsamahin ang Ilang Magkatabing Cells nang Pahalang

• Magkakasunod na pagsamahin ang mga magkatabing cells sa pamamagitan ng pagtakda ng parehong set ID. Tinitiyak nito na may mga pahalang na daanan.

Hakbang 3: Gumawa ng Vertical na Koneksyon Patungo sa Susunod na Hilerang

• Para sa bawat set na lumilitaw sa hilera, kailangan mayroong kahit isang cell na kumokonekta pababa (upang matiyak ang konektividad).
• Random na pumili ng isa o higit pang mga cell mula sa bawat set upang kumonekta sa susunod na hilera.

Hakbang 4: Magpatuloy sa Susunod na Hilera

• Ipasa ang mga vertical na koneksyon sa pamamagitan ng pagtatakda ng parehong set ID sa mga kaukulang cell sa ibaba.
• Magtalaga ng mga bagong set ID sa mga cell na hindi pa naitatakda.

Hakbang 5: Ulitin ang Hakbang 2–4 Hanggang Maabot ang Huling Hilera

• Magpatuloy sa pagproseso ng hilera-hilera.

Hakbang 6: Proseso ang Huling Hilera

• Tiyakin na ang lahat ng cells sa huling hilera ay kabilang sa parehong set sa pamamagitan ng pagsasama-sama ng mga natitirang hiwalay na set.