Saya mencoba untuk menghasilkan dinding yang memotong titik tertentu dari titik tertentu lainnya. Gambar terlampir menunjukkan hal yang saya kejar:
- Biru terpisah dari Merah.
- Biru dipisahkan dari Merah dan Kuning.
- Biru dipisahkan dari Merah dengan penghalang ubin.
- Multiple Blue dipisahkan dari multiple Red.
Ada ide bagaimana melakukan ini?
procedural-generation
tiles
tilemap
grid
IanLarson
sumber
sumber
Jawaban:
Saya akan menyajikan konsep umum dan tiga solusi menggunakan konsep itu.
Konsep adalah peta Pengaruh : Untuk setiap lokasi di peta, Anda akan menyimpan angka yang mewakili jarak ke setiap titik warna. Dengan begitu, untuk setiap posisi Anda dapat menanyakan seberapa jauh dari biru, merah, hijau, dll. Kami menyebut hasilnya adalah peta pengaruh.
Untuk detail lebih lanjut tentang motivasi, pembuatan dan penggunaan peta pengaruh dalam permainan, lihat: Mekanisme Pemetaan Pengaruh: Representasi, Algoritma & Parameter .
Saya tidak tahu untuk apa dinding ini, kepala kanon saya adalah bahwa kita berbicara tentang permainan strategi, dan AI memutuskan di mana menempatkan dinding. Untuk melakukan itu, ada banyak pendekatan selain yang disajikan di sini. Pendekatan sederhana akan menempatkan dinding pada jarak tetap dari titik-titik warna dan menggabungkan area ketika mereka tumpang tindih - dan, tentu saja, jangan membangun mereka di atas hambatan - keuntungan dari metode ini adalah bahwa ia menjamin bahwa dinding tidak terlalu jauh untuk mengirim pasukan untuk membela mereka dan itu sangat murah secara komputasi. Saya berasumsi Anda menginginkan sesuatu yang lebih kompleks.
Solusi 1 :
Untuk menemukan cara untuk membungkus biru, temukan perbedaan antara jarak ke biru dan ke hal lain, untuk setiap titik. Tambahan : Wilayah di mana perbedaan adalah positif adalah domain pengaruh untuk biru. Jika Anda mengambil domain pengaruh untuk setiap titik warna, Anda bisa membuat Diagram Voronoi . Terima kasih kepada Sirisian karena menyebut mereka .
Kita dapat berargumen bahwa untuk titik yang mendekati biru, perbedaannya akan positif, dan untuk titik yang dekat dengan titik warna lain, perbedaannya akan negatif. Mengingat bahwa jarak adalah fungsi kontinu, oleh teorema nilai menengah, kita dapat menyatakan bahwa setidaknya satu titik di tengah perbedaannya akan mendekati nol. Sebuah solusi akan melacak dinding yang meminimalkan jarak antara semua ubin di mana perbedaannya mendekati nol.
Apapun atau tidaknya solusi memperhitungkan hambatan tergantung pada fungsi jarak. Jika Anda hanya menggunakan jarak Manhattan atau Euclidean tanpa mempertimbangkan jalur yang mungkin, maka tembok yang dihasilkan tidak akan mengambil keuntungan dari hambatan yang ada di peta.
Catatan: solusi ini mendekati area yang sama untuk biru dan sisanya dalam skenario datar.
Solusi 2 :
Secara abstrak, Anda bisa menemukan titik choke antara area pengaruh biru dan yang lainnya, lalu letakkan dinding di sana. Melakukan hal ini akan menempatkan dinding di tempat-tempat di mana pengaruhnya tidak dalam keseimbangan (dinding ujung saya lebih dekat ke satu sisi) tetapi akan meminimalkan panjang dinding.
Pendekatan yang berguna untuk menemukan choke point adalah memecah skenario menjadi simpul cembung dan membuat jaringan yang mewakili skenario. Anda akan mulai dengan asumsi Anda akan meletakkan dinding di sekitar node yang secara langsung berwarna biru, dan kemudian mulai memajukan jaringan (selalu meningkatkan jarak dari biru) dan mempertimbangkan panjang dinding jika Anda menempatkannya di sekitar apa yang telah Anda kembangkan sejauh ini. Solusi Anda adalah posisi yang memiliki panjang minimum (dan lokasi dinding adalah titik tersedak).
Dalam praktiknya, algoritma ini sedikit lebih rumit dari itu karena mungkin ada konsekuensi dalam skenario. Anda hanya perlu mempertimbangkan setiap percabangan sekali, dan memilih posisi terbaik untuk dinding untuk percabangan itu.
Solusi 3 :
Solusi pertama memiliki masalah yang mungkin menyebabkan dinding yang terlalu panjang. Solusi kedua memiliki masalah yang mungkin menyebabkan dinding yang terlalu jauh dari biru.
Perhatikan bahwa bekerja dengan piksel, ubin, atau bekerja dengan jaringan, konsep peta pengaruh, sebagai representasi jarak ke titik warna adalah valid dan berguna. Dengan demikian, dimungkinkan untuk menerapkan solusi 1 melalui jaringan node cembung.
Solusi ketiga saya adalah menggabungkan pendekatan di atas. Setelah Anda bekerja melalui jaringan, Anda dapat mempertimbangkan panjang dinding dan perbedaan pengaruhnya - dan metrik lain yang Anda inginkan - sebagai satu metrik “biaya” indikator yang dapat Anda optimalkan.
sumber