Generator Labirin Algoritma Eller

Algoritma Eller adalah algoritma pembangkitan labirin yang secara efisien menghasilkan labirin sempurna (labirin tanpa putaran dan jalur tunggal antara dua titik mana pun) menggunakan pendekatan baris demi baris. Algoritma ini menghasilkan labirin yang mirip dengan algoritma Kruskal, tetapi melakukannya dengan menghasilkan hanya satu baris pada satu waktu, tanpa perlu menyimpan seluruh labirin dalam memori. Hal ini membuatnya berguna untuk menghasilkan labirin yang sangat besar pada sistem yang sangat terbatas dan untuk pembangkitan konten prosedural.

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 Eller

Algoritma Eller diperkenalkan oleh David Eller.

Algoritma ini terkenal karena pendekatannya yang efisien, yaitu pembuatan labirin baris demi baris, sehingga ideal untuk labirin tak terbatas atau labirin yang dibuat secara real-time. Algoritma ini sering dikutip dalam literatur pembuatan konten prosedural dan pembuatan labirin, tetapi saya belum dapat menemukan sumber primer yang merinci publikasi aslinya.

Bagaimana Algoritma Eller Bekerja untuk Pembuatan Labirin

Algoritma Eller memproses satu baris pada satu waktu, mempertahankan dan memodifikasi kumpulan sel yang terhubung. Algoritma ini memastikan konektivitas sambil menghindari perulangan, dan secara efisien memperluas labirin ke bawah.

Secara teoritis, algoritma ini dapat digunakan untuk menghasilkan labirin tak terbatas, namun untuk memastikan bahwa labirin yang dihasilkan benar-benar dapat dipecahkan, perlu dilakukan peralihan ke logika "baris terakhir" pada titik tertentu untuk menyelesaikan labirin.

Langkah 1: Inisialisasi Baris Pertama

• Tetapkan ID set unik untuk setiap sel dalam baris tersebut.

Langkah 2: Gabungkan Beberapa Sel yang Berdekatan Secara Horizontal

• Gabungkan sel-sel yang berdekatan secara acak dengan menetapkan ID set yang sama. Ini memastikan adanya jalur horizontal.

Langkah 3: Buat Koneksi Vertikal ke Baris Berikutnya

• Untuk setiap himpunan yang muncul dalam baris, setidaknya satu sel harus terhubung ke bawah (untuk memastikan konektivitas).
• Pilih secara acak satu atau lebih sel dari setiap set untuk dihubungkan ke baris berikutnya.

Langkah 4: Pindah ke Baris Berikutnya

• Lanjutkan koneksi vertikal dengan menetapkan ID set yang sama ke sel-sel yang sesuai di bawahnya.
• Tetapkan ID set baru ke sel mana pun yang belum diberi ID.

Langkah 5: Ulangi Langkah 2–4 Hingga Baris Terakhir Tercapai

• Lanjutkan pemrosesan baris demi baris.

Langkah 6: Memproses Baris Terakhir

• Pastikan semua sel di baris terakhir termasuk dalam himpunan yang sama dengan menggabungkan himpunan-himpunan terpisah yang tersisa.

Bacaan Lebih Lanjut

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

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