Bagaimana mengelola dependensi antara peta ubin dan unit

11

Saya memiliki strategi berbasis ubin 2D dalam karya. Saya mengembara bagaimana menangani hubungan antara peta dan unit di peta.

Diberikan koordinat ubin saya harus bisa mendapatkan unit berdiri di atasnya, jika ada. Pada saat yang sama, jika diberi unit saya ingin bisa mendapatkan koordinat unit.

Saya telah melihat dua solusi untuk ini. Solusi pertama adalah memiliki unit menyimpan koordinat dan unit referensi peta menyimpan di ubinnya. Ini menciptakan ketergantungan siklus antara peta dan unit. Saya perlu memastikan bahwa peta suatu unit apa pun tetap disinkronkan jika unit bergerak.

Solusi kedua adalah dengan hanya memiliki unit melacak koordinat mereka. Untuk mengetahui apakah ubin berisi unit dan untuk mendapatkan unit itu, saya akan mengulang seluruh rangkaian unit yang saya temukan dengan koordinat yang cocok. Itu mendapatkan rides dari ketergantungan siklik, tetapi kehilangan properti O (1) solusi pertama untuk mencari unit dari peta. Ini mungkin bertambah karena saya ingin dapat memindai peta secara teratur untuk hal-hal seperti pencarian jalur, menentukan rentang gerakan, dan menemukan target yang valid untuk unit tertentu.

Saya juga tidak bisa hanya menyimpan unit di peta (atau bisakah saya?). Unit dikaitkan dengan "pasukan", baik pemain atau AI. Pasukan harus dapat dengan mudah mengakses dan beralih ke semua unitnya.

Karena ini tampaknya menjadi masalah umum dalam permainan strategi, apakah ada pola lain selain dua yang saya jelaskan untuk mengelola hubungan unit / peta?

tiles maps character AJM
sumber

Jawaban:

3

Ini bukan pola yang populer tetapi dunia basis data relasional menawarkan cara ketiga: gunakan struktur data yang memiliki banyak kunci. Dalam bentuk tabel, ini mungkin terlihat seperti ini:

Unit id    Location
-------------------
  1309     13,15
  2357      7,93
  8552      7,93

Anda ingin dapat bertanya, "di mana unit 2357?" dan kembali 7,93. Anda juga ingin dapat bertanya, "ada apa di lokasi 7,93?" dan kembali 2357 dan 8552. Ada struktur data yang memungkinkan beberapa kunci untuk mencari sesuatu. Anda dapat menyimpan ini di luar unit dan di luar peta jika Anda ingin menghapus dependensi.

Namun, dalam praktiknya lebih umum untuk menyimpan lokasi di setiap unit, dan kemudian di samping menggunakan struktur data partisi spasial yang memberi tahu Anda unit apa yang ada di wilayah tertentu. Karena ini adalah struktur yang terpisah, daerah tidak harus berupa ruang kotak; mereka bisa menjadi area yang lebih besar.

Saya sarankan melakukan apa pun yang paling mudah (solusi kedua Anda) dan kemudian jika itu masalah kinerja Anda dapat menambahkan partisi spasial untuk membuat pencarian lebih cepat.

amitp
sumber
Jadi, struktur data partisi spasial yang Anda sebutkan bisa saja berupa peta (yang dalam kasus saya seolah-olah kotak 2D ubin). Saya berasumsi ketika unit bergerak (atau ditambahkan, atau dihapus) Saya masih perlu memperbarui unit dan struktur partisi spasial agar tetap sinkron. Mungkin itu salah satu hal yang harus saya jalani?
AJM
1
Ya, peta adalah partisi spasial berbutir paling halus yang akan Anda gunakan. Daftar global semua unit adalah partisi berbutir paling kasar. ;) Anda hanya perlu memperbarui partisi sebelum digunakan. Jika Anda menggunakannya sepanjang waktu, Anda mungkin ingin memperbaruinya setiap kali unit dipindahkan. Namun, jika Anda hanya menggunakannya untuk beberapa fase dari logika pembaruan, Anda bisa melalui daftar unit dalam satu pass dan menghitung struktur data partisi, kemudian membuangnya setelah selesai. Dengan begitu, Anda tidak harus selalu menyinkronkannya.
amitp
5

Nah, Anda kecuali Anda beberapa ribu unit per pemain, saya tidak akan khawatir tentang penggunaan memori, dan menggunakan solusi pertama. Memori sepertinya lebih murah daripada CPU.

Faktanya bahkan jika Anda memiliki 4000 unit per pemain, menggunakan dua bilangan bulat untuk menyimpan lokasi di sana, dan 8 pemain, yang hanya membutuhkan 2MB, tetapi dengan solusi pertama, Anda bisa menggunakan O (1) pengambil koordinat, daripada O (n) (dengan asumsi tidak disortir), yang dengan banyak unit bisa lambat.

Sebagian besar game tampaknya berbasis pixel, bukan tile, sekarang menjadi hari jadi mereka hanya perlu mendapatkan unit untuk menyimpan co-ords.

Ray Britton
sumber
Saya tidak khawatir tentang penggunaan memori, saya lebih tertarik dalam mengelola dependensi (dalam arti Desain Berorientasi Objek). Bukan memori tambahan yang akan ditimbulkan oleh solusi pertama yang membuat saya khawatir, ini adalah ketergantungan siklus yang saya curigai, sebanyak saya menyukai pengambil koordinat O (1). Juga, saya tahu banyak game berbasis pixel sekarang, tapi saya suka ubin jadi itulah yang saya gunakan. : P
AJM
@ AJM, sama, aplikasi berbayar yang akan saya rilis di android akan menggunakan ubin.
Ray Britton