Generator Labirin Algoritma Pohon Tumbuh

Algoritma Growing Tree menarik karena dapat meniru perilaku beberapa algoritma lain, tergantung pada bagaimana sel berikutnya dipilih selama proses pembuatan. Implementasi pada halaman ini menggunakan pendekatan breadth-first, seperti antrian.

Labirin yang sempurna adalah labirin yang hanya memiliki satu jalan dari titik mana pun di dalam labirin ke titik lainnya. Itu berarti Anda tidak bisa berputar-putar, tetapi Anda akan sering menemui jalan buntu, memaksa Anda untuk berbalik dan kembali.

Peta labirin yang dibuat di sini termasuk versi default tanpa posisi awal dan akhir, sehingga Anda dapat menentukannya sendiri: akan ada solusi dari titik mana pun di dalam labirin ke titik lainnya. Jika Anda menginginkan inspirasi, Anda dapat mengaktifkan posisi awal dan akhir yang disarankan - dan bahkan melihat solusi di antara keduanya.

Tentang Algoritma Pohon yang Berkembang

Algoritma Growing Tree adalah metode yang fleksibel dan ampuh untuk menghasilkan labirin yang sempurna. Algoritma ini menarik karena dapat meniru perilaku beberapa algoritma pembuatan labirin lainnya, seperti algoritma Prim, penelusuran balik rekursif, dan pembagian rekursif, tergantung pada bagaimana Anda memilih sel berikutnya yang akan diproses.

Bagaimana Algoritma Pohon yang Berkembang Bekerja

Langkah 1: Inisialisasi

• Mulailah dengan kisi-kisi sel yang belum dikunjungi.
• Pilih sel awal secara acak dan tambahkan ke dalam daftar.

Langkah 2: Siklus Pembuatan Labirin

• Selama daftar sel belum kosong: Pilih sel dari daftar berdasarkan strategi tertentu (dijelaskan di bawah). Buat jalur dari sel yang dipilih ke salah satu tetangganya yang belum dikunjungi (dipilih secara acak). Tambahkan tetangga tersebut ke daftar karena sekarang menjadi bagian dari labirin. Jika sel yang dipilih tidak memiliki tetangga yang belum dikunjungi, hapus sel tersebut dari daftar.

Langkah 3: Penghentian

• Algoritma berakhir ketika tidak ada lagi sel dalam daftar, yang berarti seluruh labirin telah diukir.

Strategi Seleksi Sel (Fleksibilitas Algoritma)

Ciri khas algoritma Growing Tree adalah bagaimana Anda memilih sel mana yang akan diproses selanjutnya. Pilihan ini secara dramatis memengaruhi tampilan labirin:

Sel Terbaru (Perilaku Mirip Tumpukan) – Backtracker Rekursif:

• Selalu pilih sel yang paling baru ditambahkan.
• Menghasilkan koridor panjang dan berkelok-kelok dengan banyak jalan buntu (seperti labirin pencarian kedalaman pertama).
• Labirin cenderung memiliki lorong yang panjang dan mudah dipecahkan.

Sel Acak (Algoritma Prim yang Diacak):

• Pilih sel secara acak dari daftar setiap kali.
• Menciptakan labirin yang terdistribusi lebih merata dengan jalur yang kompleks dan kusut.
• Lebih sedikit koridor panjang dan lebih banyak percabangan.

Sel Tertua (Perilaku Mirip Antrian):

• Selalu pilih sel tertua dalam daftar.
• Menghasilkan labirin dengan sebaran yang lebih seragam, seperti pola pencarian breadth-first.
• Lorong-lorong pendek dan rimbun dengan banyak percabangan.
• (Ini adalah versi yang diterapkan di sini)

Pendekatan Hibrida:

Gabungkan strategi untuk berbagai karakteristik labirin. Misalnya:

• 90% terbaru, 10% acak: Sebagian besar terlihat seperti labirin backtracker rekursif, tetapi dengan cabang-cabang sesekali yang memecah koridor panjang.
• 50% terbaru, 50% terlama: Menyeimbangkan koridor panjang dengan pertumbuhan yang rimbun.

Bacaan Lebih Lanjut

Jika Anda menikmati postingan ini, Anda mungkin juga menyukai saran berikut:

• Generator Labirin Pelacak Balik Rekursif
• Generator Labirin Perburuan dan Bunuh
• Generator Labirin Algoritma Kruskal