Penjana Maze Algoritma Eller

Algoritma Eller ialah algoritma penjanaan maze yang cekap menghasilkan mazes sempurna (mazes tanpa gelung dan satu laluan antara mana-mana dua titik) menggunakan pendekatan baris demi baris. Ia menghasilkan maze yang serupa dengan algoritma Kruskal, tetapi ia melakukannya dengan menjana hanya satu baris pada satu masa, tanpa perlu menyimpan keseluruhan maze dalam ingatan. Itu menjadikannya berguna untuk menghasilkan maze yang sangat besar pada sistem yang sangat terhad dan untuk penjanaan kandungan prosedur.

Labirin yang sempurna ialah labirin di mana terdapat betul-betul satu laluan dari mana-mana titik dalam mez ke mana-mana titik lain. Ini bermakna anda tidak boleh mengelilingi dalam bulatan, tetapi anda sering menemui jalan buntu, memaksa anda untuk berpusing dan kembali.

Peta maze yang dijana di sini termasuk versi lalai tanpa sebarang kedudukan mula dan penamat, jadi anda boleh memutuskannya sendiri: akan ada penyelesaian dari mana-mana titik dalam maze ke mana-mana titik lain. Jika anda mahukan inspirasi, anda boleh mendayakan kedudukan permulaan dan penamat yang dicadangkan - malah melihat penyelesaian antara kedua-duanya.

Tentang Algoritma Eller

Algoritma Eller diperkenalkan oleh David Eller.

Algoritma ini terkenal dengan pendekatannya yang efisien baris demi baris dalam penjanaan labirin, menjadikannya ideal untuk labirin tak terhingga atau labirin yang dijana secara langsung. Ia sering disebut dalam literatur penjanaan kandungan prosedural dan penjanaan labirin, tetapi saya belum dapat mencari sumber utama yang memperincikan penerbitan asalnya.

Bagaimana Algoritma Eller Berfungsi untuk Penjanaan Labirin

Algoritma Eller memproses satu baris pada satu masa, mengekalkan dan mengubah set sel yang disambungkan. Ia memastikan penyambungan sambil mengelakkan gelung, dan ia secara efisien melanjutkan labirin ke bawah.

Secara teori, ia boleh digunakan untuk menghasilkan labirin tak terhingga, namun untuk memastikan labirin yang dijana itu boleh diselesaikan, adalah perlu untuk beralih ke logik "baris terakhir" pada satu ketika untuk menyelesaikan labirin.

Langkah 1: Mulakan Baris Pertama

• Berikan setiap sel dalam baris ID set unik.

Langkah 2: Gabungkan Beberapa Sel Bersebelahan Secara Mendatar

• Gabungkan sel bersebelahan secara rawak dengan menetapkan mereka kepada ID set yang sama. Ini memastikan bahawa terdapat laluan mendatar.

Langkah 3: Cipta Sambungan Menegak ke Baris Seterusnya

• Untuk setiap set yang muncul dalam baris, sekurang-kurangnya satu sel mesti menyambung ke bawah (untuk memastikan penyambungan).
• Pilih secara rawak satu atau lebih sel dari setiap set untuk disambungkan ke baris seterusnya.

Langkah 4: Berpindah ke Baris Seterusnya

• Teruskan sambungan menegak dengan memberikan ID set yang sama kepada sel yang sepadan di bawah.
• Berikan ID set baru kepada mana-mana sel yang tidak diberikan ID.

Langkah 5: Ulangi Langkah 2–4 Sehingga Baris Terakhir Dicapai

• Teruskan memproses baris demi baris.

Langkah 6: Proses Baris Terakhir

• Pastikan semua sel dalam baris terakhir tergolong dalam set yang sama dengan menggabungkan mana-mana set yang masih berasingan.