Generator Labirin Algoritma Eller

Algoritma Eller adalah algoritma pembuatan labirin yang secara efisien menghasilkan labirin sempurna (labirin tanpa lingkaran dan satu jalur antara dua titik) menggunakan pendekatan baris demi baris. Algoritma ini menghasilkan labirin yang mirip dengan algoritma Kruskal, tetapi melakukannya dengan hanya menghasilkan 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 pembuatan 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.

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

Cara Kerja Algoritma Eller untuk Pembuatan Labirin

Algoritme Eller memproses satu baris pada satu waktu, memelihara dan memodifikasi set sel yang terhubung. Algoritme ini memastikan konektivitas sekaligus menghindari loop, dan memperluas labirin ke bawah secara efisien.

Secara teori, logika ini dapat digunakan untuk menghasilkan labirin tak terhingga jumlahnya, namun untuk memastikan labirin yang dihasilkan benar-benar dapat dipecahkan, logika "baris terakhir" perlu diubah pada titik tertentu untuk menuntaskan labirin tersebut.

Langkah 1: Inisialisasi Baris Pertama

• Tetapkan setiap sel pada baris dengan ID set yang unik.

Langkah 2: Gabungkan Beberapa Sel yang Berdekatan Secara Horizontal

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

Langkah 3: Buat Koneksi Vertikal ke Baris Berikutnya

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

Langkah 4: Pindah ke Baris Berikutnya

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

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

• Lanjutkan pemrosesan baris demi baris.

Langkah 6: Proses Baris Terakhir

• Pastikan semua sel pada baris terakhir termasuk dalam set yang sama dengan menggabungkan set terpisah yang tersisa.