Saya merancang game dengan ruang bawah tanah yang dihasilkan secara acak. Saya ingin melihat ini sebagai grafik yang terhubung dan tidak terarah di mana simpul adalah kamar dan ujungnya adalah pintu atau koridor. Lalu saya memilih "sisi" simpul sebagai pintu masuk penjara bawah tanah, saya menghitung jarak antara pintu masuk ini dan semua simpul lainnya, dan memutuskan bahwa salah satu simpul terjauh adalah "tujuan" dari penjara bawah tanah itu (lokasi harta, bos, putri, dll.).
Saya melihat 2 cara untuk menghasilkan topografi ruang bawah tanah terakhir:
- Pertama-tama buat grafik acak, lalu coba isi dunia 2d dengan kamar di lokasi acak, dengan menghormati koneksi tepi. Saya pikir ini kadang-kadang akan sulit karena generasi kamar bisa "dikunci" mencoba menyesuaikan kamar di tempat-tempat yang tidak mungkin.
- Hasilkan kamar pertama, tempatkan secara acak di tempat yang sesuai, lalu petakan hasilnya ke node dan edge. Saya memutuskan untuk mencoba ini.
Gagasan saya terdiri dari:
- Pertama menghasilkan ruang besar yang akan berisi seluruh penjara bawah tanah.
- Letakkan dinding di dalam ruangan besar, di lokasi acak, bagi ruangan besar menjadi 2 ruangan kecil di area berbeda.
- Lalu saya terus membagi setiap kamar menjadi 2, sampai mereka terlalu kecil, atau jumlah total kamar mencapai maksimum (atau kondisi lainnya). Setiap kamar baru adalah sebuah simpul.
- Setelah selesai, saya memeriksa setiap kamar dan menemukan semua kamar lain yang berdekatan, menandai 2 node sebagai terhubung oleh tepi.
Dengan begitu saya memastikan bahwa semua kamar memiliki lokasi yang memungkinkan di dunia 2D, dan dipetakan dengan benar oleh grafik yang terhubung.
Masalah saya adalah terlalu banyak pintu dan koridor yang menghubungkan kamar.
Jadi saya ingin algoritma yang mengurangi jumlah tepi dari grafik yang tidak diarahkan terhubung , tetapi tetap terhubung (semua node tetap terjangkau) pada akhirnya.
Jawaban:
Gunakan Prim's Algorithm untuk mendapatkan pohon rentang minimum untuk grafik Anda (tambahkan bobot acak, atau tambahkan bobot lebih tinggi di dekat pintu masuk, atau lakukan algoritma pilihan Anda) dan tambahkan kembali beberapa pintu / tepi secara acak. Dengan cara ini Anda akan memiliki semua kamar yang terhubung dan beberapa jalur ekstra berlebihan.
sumber
Anda juga bisa mencoba Algoritma Kruskal
sumber
Beberapa generator ruang bawah tanah pada daftar ini dari Inkwell Ideas bersifat open source atau menyediakan dokumentasi tentang algoritme mereka. Google juga akan memberi Anda banyak dengan mencari generator bawah tanah '[programminglanguagename]'. Sayangnya favorit saya tidak dapat ditemukan dengan salah satu dari metode tersebut, meskipun merupakan yang paling baik didokumentasikan yang pernah saya temui, dan saya tidak dapat mengingat namanya karena saya kehilangan itu karena hard drive crash baru-baru ini. Saya akan memperbarui jawaban ini setelah saya melakukan pemulihan pada drive itu.
sumber