Penjana Maze Algoritma Pokok Tumbuh

Algoritma Growing Tree menarik, kerana ia boleh meniru tingkah laku beberapa algoritma lain, bergantung pada cara sel seterusnya dipilih semasa penjanaan. Pelaksanaan pada halaman ini menggunakan pendekatan yang didahulukan secara meluas, seperti baris gilir.

Labirin yang sempurna ialah labirin di mana terdapat betul-betul satu laluan dari mana-mana titik dalam mez ke mana-mana titik lain. Ini bermakna anda tidak boleh mengelilingi dalam bulatan, tetapi anda sering menemui jalan buntu, memaksa anda untuk berpusing dan kembali.

Peta maze yang dijana di sini termasuk versi lalai tanpa sebarang kedudukan mula dan penamat, jadi anda boleh memutuskannya sendiri: akan ada penyelesaian dari mana-mana titik dalam maze ke mana-mana titik lain. Jika anda mahukan inspirasi, anda boleh mendayakan kedudukan permulaan dan penamat yang dicadangkan - malah melihat penyelesaian antara kedua-duanya.

About the Growing Tree Algorithm

Algoritma Growing Tree adalah kaedah yang fleksibel dan kuat untuk menghasilkan labirin yang sempurna. Algoritma ini menarik kerana ia dapat meniru tingkah laku beberapa algoritma penjanaan labirin lain, seperti algoritma Prim, penjejakan kembali rekursif, dan pembahagian rekursif, bergantung kepada bagaimana anda memilih sel seterusnya untuk diproses.

How the Growing Tree Algorithm Works

Langkah 1: Inisialisasi

• Mula dengan grid sel yang belum dilawati.
• Pilih sel permulaan secara rawak dan tambahkannya ke dalam senarai.

Langkah 2: Gelung Penjanaan Labirin

• Semasa senarai sel tidak kosong:
  • Pilih satu sel dari senarai berdasarkan strategi tertentu (yang dijelaskan di bawah).
  • Gali laluan dari sel yang dipilih ke salah satu jirannya yang belum dilawati (dipilih secara rawak).
  • Tambah jiran ke dalam senarai kerana ia kini menjadi sebahagian daripada labirin.
  • Jika sel yang dipilih tiada jiran yang belum dilawati, keluarkannya dari senarai.

Langkah 3: Penamatan

• Algoritma berakhir apabila tiada lagi sel dalam senarai, yang bermaksud seluruh labirin telah digali.

Strategi Pemilihan Sel (Fleksibiliti Algoritma)

Ciri utama algoritma Growing Tree adalah bagaimana anda memilih sel yang akan diproses seterusnya. Pemilihan ini memberi kesan yang besar terhadap rupa labirin:

Sel Terbaru (Tingkah Laku Seperti Stack) – Penjejakan Kembali Rekursif:

• Sentiasa pilih sel yang baru sahaja ditambah.
• Menghasilkan lorong yang panjang dan berliku dengan banyak jalan mati (seperti labirin carian mendalam pertama).
• Labirin cenderung mempunyai lorong panjang dan mudah diselesaikan.

Sel Rawak (Algoritma Prim Rawak):

• Pilih sel rawak dari senarai setiap kali.
• Mewujudkan labirin yang lebih teragih dengan laluan yang kompleks dan kusut.
• Lebih sedikit lorong panjang dan lebih banyak cabang.

Sel Terlama (Tingkah Laku Seperti Queue):

• Sentiasa pilih sel yang paling lama dalam senarai.
• Menjana labirin dengan penyebaran yang lebih sekata, seperti corak carian lebar pertama.
• Laluan pendek yang rimbun dengan sambungan yang padat.
• (Ini adalah versi yang dilaksanakan di sini)

Pendekatan Hibrid:

Gabungkan strategi untuk ciri labirin yang pelbagai. Contohnya:

• 90% sel terbaru, 10% sel rawak: Nampak seperti labirin penjejakan kembali rekursif, tetapi dengan cawangan sekali-sekala yang memecahkan lorong panjang.
• 50% sel terbaru, 50% sel terlama: Menyeimbangkan lorong panjang dengan pertumbuhan yang rimbun.