Generator Labirin Algoritma Pohon Tumbuh

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

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 Growing Tree

Algoritma Growing Tree merupakan 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, backtracking rekursif, dan pembagian rekursif, tergantung pada bagaimana Anda memilih sel berikutnya untuk diproses.

Cara Kerja Algoritma Growing Tree

Langkah 1: Inisialisasi

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

Langkah 2: Loop Pembuatan Labirin

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

Langkah 3: Penghentian

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

Strategi Pemilihan Sel (Fleksibilitas Algoritma)

Fitur penentu algoritma Growing Tree adalah bagaimana Anda memilih sel mana yang akan diproses selanjutnya. Pilihan ini secara drastis memengaruhi tampilan labirin:

Sel Terbaru (Perilaku Seperti Tumpukan) – Pelacakan Balik Rekursif:

• Selalu pilih sel yang terakhir ditambahkan.
• Menghasilkan koridor yang panjang dan berliku-liku dengan banyak jalan buntu (seperti labirin pencarian kedalaman).
• Labirin cenderung memiliki lorong yang panjang dan mudah dipecahkan.

Sel Acak (Algoritma Prim Acak):

• Pilih sel acak dari daftar setiap kali.
• Menciptakan labirin yang terdistribusi secara merata dengan jalur yang rumit dan kusut.
• Koridor panjang lebih sedikit, tetapi percabangan lebih banyak.

Sel Tertua (Perilaku Seperti Antrean):

• Selalu pilih sel terlama dalam daftar.
• Menghasilkan labirin dengan penyebaran yang lebih seragam, seperti pola pencarian breadth-first.
• Lorong pendek dan lebat dengan koneksi yang rapat.
• (Ini adalah versi yang diterapkan di sini)

Pendekatan Hibrida:

Gabungkan strategi untuk berbagai karakteristik labirin. Misalnya:

• 90% terbaru, 10% acak: Tampak seperti labirin penelusuran balik rekursif, tetapi dengan cabang sesekali yang memecah koridor panjang.
• 50% terbaru, 50% terlama: Menyeimbangkan koridor panjang dengan pertumbuhan lebat.