Saya mencoba membuat roguelike kecil dan pergi sejauh menghasilkan ruang acak dan koridor. Setiap kamar adalah objek yang dipasang dan berisi daftar susunan dari kamar lain yang dihubungkan oleh koridor.
Saya dapat memilih kamar yang tidak terhubung, tetapi bagaimana saya bisa tahu kamar-kamar yang terhubung hanya satu sama lain tetapi tidak untuk sebagian besar yang lain, membentuk sebuah pulau?
untuk diilustrasikan dengan lebih baik masalah di sini adalah gambar dari konsol pada tingkat macet. Kamar 5 dan 6 hanya terhubung satu sama lain. Algoritma apa yang dapat saya gunakan untuk mendeteksi itu?
Jawaban:
Mulailah dengan daftar kamar lengkap. Pilih ruang awal. Menavigasi dari kamar itu ke semua kamar yang terhubung. Untuk setiap kamar yang Anda kunjungi, menghapusnya dari daftar kamar dan menambahkannya ke daftar A . Setelah Anda telah mengunjungi semua koneksi Anda, setiap kamar yang tersisa dalam daftar tidak terhubung ke ruang awal atau salah satu kamar di daftar A .
Anda kemudian dapat melanjutkan dengan memilih kamar dari sisa daftar lengkap, dan menavigasi lagi. Kali ini menambah daftar B . Lanjutkan proses ini sampai Anda tidak memiliki kamar lagi di daftar asli. Anda sekarang memiliki daftar semua set kamar yang terhubung.
Masalah seperti ini mudah disesuaikan dengan masalah teori graf. Misalnya, masalah yang Anda jelaskan di atas berkaitan langsung dengan konektivitas .
sumber
Koleksi kamar Anda pada dasarnya adalah sebuah grafik, dan masalah Anda bermuara pada menemukan komponen yang terhubung ("pulau") dalam grafik itu.
Cara sederhana untuk menemukan komponen yang terhubung adalah dengan melakukan BFS (pencarian pertama kali) dari setiap titik. Melakukan BFS dari simpul A akan membuat Anda mendapatkan semua simpul di komponen yang terhubung dengan simpul A.
Jadi, pada dasarnya, Anda mulai dengan titik sembarang, lakukan BFS dan tandai setiap titik yang ditemui sebagai anggota "pulau" pertama. Kemudian Anda beralih ke simpul tak bertanda berikutnya dan melakukan BFS lagi, kali ini pelabelan menemui simpul sebagai anggota "pulau" ke-2, dan seterusnya.
sumber
Anda dapat menggambarkan ruangan sebagai simpul pada grafik terarah . Dengan melakukan itu, Anda akan dapat menerapkan algoritma terkenal untuk menyelesaikan masalah Anda.
Algoritma Dijkstra , misalnya, menghasilkan pohon jalur terpendek untuk titik awal yang diberikan pada grafik. Pohon ini akan berisi semua simpul yang dapat dijangkau dari titik awal. Anda kemudian dapat menyimpulkan bahwa simpul yang tidak ada di pohon adalah bagian dari pulau lain. Anda dapat menerapkan algoritme pada simpul-simpul ini untuk mendapatkan pohon yang mewakili setiap pulau.
sumber