GraphsMenengahFase D–FE1E5

PRIM MAZE

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.

Example use case

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

Syllabus

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

Objectives

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

How It Works

·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

Prerequisites

·Graf
·Grid 2D

Real-World Uses

·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

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