GrafMenengahFase D–FE1E5

Pembangkitan Labirin dengan Prim

Pembangkitan labirin berbasis algoritma Prim menumbuhkan lorong mulai dari satu sel benih. Dinding di sekitar sel yang telah dikunjungi ditambahkan ke frontier; algoritma memilih dinding secara acak, dan jika sel di seberangnya belum dikunjungi, dinding tersebut dibuka menjadi lorong dan dinding baru ditambahkan ke frontier. Proses berlanjut hingga seluruh sel terhubung. Visualisasi menampilkan grid dengan lorong yang tumbuh sampai labirin lengkap.

Contoh kasus

Pembangkitan peta labirin acak secara prosedural pada game atau level generator.

Silabus

Prim menumbuhkan labirin dari satu sel benih, memperluas lorong dengan membuka dinding acak dari daftar frontier.

Tujuan Belajar

·Memahami konsep frontier sebagai daftar dinding kandidat
·Menjelaskan cara lorong tumbuh dari satu sel awal
·Menerapkan Prim untuk membangkitkan labirin acak

Cara Kerja

·Pilih satu sel benih dan tandai sudah dikunjungi
·Tambahkan dinding di sekitar sel itu ke daftar frontier
·Pilih satu dinding acak dari frontier
·Bila sel di seberangnya belum dikunjungi, buka dinding jadi lorong
·Tambahkan dinding baru ke frontier, ulangi sampai semua sel terhubung

Prasyarat

·Graf
·Grid 2D

Contoh Nyata

·Membangkitkan peta labirin acak secara prosedural di game
·Level generator yang bikin stage baru tiap kali main
·Membuat pola maze unik untuk teka-teki di aplikasi

Kompleksitas O(V log V) atau O(E) tergantung struktur frontier