Generator Labirin Perburuan dan Bunuh

Algoritma Hunt and Kill sebenarnya merupakan versi modifikasi dari Recursive Backtracker. Modifikasi tersebut terdiri dari pemindaian sistematis (atau "berburu") sel baru untuk melanjutkan ketika tidak dapat melangkah lebih jauh, berbeda dengan pencarian rekursif sejati yang akan selalu kembali ke sel sebelumnya pada tumpukan.

Oleh karena itu, algoritma ini dapat dengan mudah diadaptasi untuk menghasilkan labirin dengan tampilan dan nuansa yang berbeda, hanya dengan memilih untuk memasuki mode "berburu" lebih sering atau sesuai dengan aturan tertentu. Versi yang diimplementasikan di sini hanya memasuki mode "berburu" ketika tidak dapat bergerak lebih jauh dari sel saat ini.

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 Perburuan dan Pembunuhan

Algoritma Hunt and Kill adalah metode sederhana namun efektif untuk menghasilkan labirin. Algoritma ini agak mirip dengan pencarian mendalam (yaitu algoritma Recursive Backtracker), kecuali bahwa ketika tidak dapat bergerak lebih jauh dari posisi saat ini, algoritma ini secara sistematis memindai (atau "berburu") labirin untuk menemukan sel baru untuk melanjutkan pencarian. Algoritma ini terdiri dari dua fase utama: berjalan dan berburu.

Bagaimana Algoritma Hunt and Kill Bekerja untuk Pembuatan Labirin

Langkah 1: Mulai dari sel acak

• Temukan sel secara acak di dalam kotak dan tandai sebagai telah dikunjungi.

Langkah 2: Fase Berjalan (Jalan Acak)

• Pilih tetangga yang belum dikunjungi secara acak.
• Pindah ke tetangga tersebut, tandai sebagai sudah dikunjungi, dan buat jalur antara sel sebelumnya dan sel yang baru.
• Ulangi hingga tidak ada lagi tetangga yang belum dikunjungi.

Langkah 3: Fase Perburuan (Pelacakan Balik melalui Pemindaian)

• Pindai kisi-kisi baris demi baris (atau kolom demi kolom).
• Temukan sel pertama yang belum dikunjungi yang memiliki setidaknya satu tetangga yang telah dikunjungi.
• Hubungkan sel tersebut ke sel tetangga yang telah dikunjungi untuk melanjutkan fase berjalan.
• Ulangi hingga semua sel telah dikunjungi.

Bacaan Lebih Lanjut

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

• Generator Labirin Algoritma Kruskal
• Generator Labirin Pelacak Balik Rekursif
• Generator Labirin Algoritma Eller