Lumalagong Puno Algorithm Maze Generator

Ang algorithm ng Growing Tree ay kawili-wili, dahil maaari nitong tularan ang pag-uugali ng ilang iba pang mga algorithm, depende sa kung paano pinili ang susunod na cell sa panahon ng henerasyon. Ang pagpapatupad sa page na ito ay gumagamit ng malawak na una, mala-queue na diskarte.

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 Algorithm ng Lumalagong Puno

Ang algorithm ng Lumalagong Puno ay isang flexible at makapangyarihang paraan para makabuo ng perpektong labirinto. Interesante ang algorithm na ito dahil kaya nitong gayahin ang kilos ng ilang iba pang algorithm sa pagbuo ng labirinto, tulad ng algorithm ni Prim, recursive backtracking, at recursive division, depende sa kung paano pipiliin ang susunod na cell na iproseso.

Paano Gumagana ang Algorithm ng Lumalagong Puno

Hakbang 1: Inisyalizasyon

• Mag-umpisa sa isang grid ng mga cell na hindi pa nabisita.
• Pumili ng isang random na cell bilang panimulang cell at idagdag ito sa isang listahan.

Hakbang 2: Loop ng Pagbuo ng Labirinto

• Habang hindi pa empty ang listahan ng mga cell:
  • Pumili ng cell mula sa listahan batay sa isang partikular na estratehiya (ipinapaliwanag sa ibaba).
  • Gumuhit ng isang daanan mula sa napiling cell patungo sa isa sa mga hindi pa nabisitang kalapit na cell (na pinili nang random).
  • Idagdag ang kalapit na cell sa listahan dahil isa na itong bahagi ng labirinto.
  • Kung walang hindi pa nabisitang kalapit na cell ang napiling cell, alisin ito mula sa listahan.

Hakbang 3: Pagtatapos

• Tatapusin ng algorithm kapag wala nang natirang cell sa listahan, ibig sabihin, natapos na ang buong labirinto.

Mga Estratehiya sa Pagpili ng Cell (Pagkakaroon ng Pagkakataon ang Algorithm)

Ang pangunahing katangian ng algorithm ng Lumalagong Puno ay kung paano mo pipiliin kung aling cell ang ipoproseso sa susunod. Ang pagpili na ito ay may malaking epekto sa itsura ng labirinto:

Pinakabagong Cell (Pag-uugali ng Stack) – Recursive Backtracker:

• Laging piliin ang pinaka-bagong idinagdag na cell.
• Nagbubuo ng mahahabang, paikot-ikot na mga koridor na may maraming patay na dulo (tulad ng isang depth-first search na labirinto).
• Ang mga labirinto ay may mga mahahabang daanan at madaling lutasin.

Random na Cell (Randomized Prim's Algorithm):

• Pumili ng isang random na cell mula sa listahan bawat pagkakataon.
• Nagbubuo ng isang mas pantay na distribusyon ng labirinto na may mga kumplikado at magulong mga daan.
• Mas kaunting mahahabang koridor at mas maraming mga sanga.

Pinakamatandang Cell (Pag-uugali ng Queue):

• Laging piliin ang pinakamatandang cell sa listahan.
• Nagbubuo ng mga labirinto na may mas pantay na distribusyon, tulad ng isang breadth-first search na pattern.
• Maikli, mabagsik na mga daanan na may mas maraming koneksyon.
• (Ito ang bersyon na ipinapatupad dito)

Hybrid na Paraan:

Pagsamahin ang mga estratehiya para sa iba't ibang katangian ng labirinto. Halimbawa:

• 90% pinakabago, 10% random: Mukhang karamihan ay isang recursive backtracker na labirinto, ngunit may paminsan-minsang mga sanga na nagpuputol sa mga mahahabang koridor.
• 50% pinakabago, 50% pinakamatanda: Nagbibigay ng balanse sa pagitan ng mahahabang koridor at bushy na paglago.