'Zonasi' area di peta ubin besar, serta ruang bawah tanah

Gim saya memiliki peta seperti yang dimiliki Minecraft, seperti pseudoinfinite dan dibuat secara acak. Dan besar. Katakanlah pengguna telah menjelajahi zona 1000x1000 (2D di sini), jadi itu 1.000.000 ubin.

Jelas saya tidak akan bisa menyimpan semuanya di memori. Saya juga tidak ingin mengabaikan semuanya dari 10 ubin atau radius apa pun - keduanya tidak akan memperbarui (semua NPC, mungkin ubin reaktif) dan saya harus bekerja dengan posisi canggung seperti 1382.12918.

Jadi jika saya harus membaginya menjadi potongan atau zona atau apa pun yang mengatakan ubin 64x64, saya harus menyimpan setiap ubin dan posisi objek seperti:

Potongan a, b. Posisi x, y.

Tetapi bagaimana jika saya ingin ruang bawah tanah dan sejenisnya di peta saya? Jadi satu ubin yang mengarah ke ruang bawah tanah 40 lantai, masing-masing dengan luas 40x40. Saya tidak bisa menyimpannya di peta yang sama.

Dan ada sisi memori; berapa banyak yang bisa saya simpan dalam memori pada saat yang bersamaan secara wajar? Saya bisa membuat ubin dengan ID dengan mudah, dan memiliki array 2D normal di sana. Atau lagi, apakah ada solusi yang lebih efektif daripada memiliki file data tipe ubin ? Jadi untuk 64x64 .. itu hanya akan menjadi 20 ribu atau apa pun. Saya ingin sebanyak mungkin sekitar dimuat untuk pembaruan paling realistis. Tapi saya tidak tahu batas seperti apa yang bisa saya tekan tanpa menjadi memori memonopoli.

Sementara saya setuju dengan sentimen: "jangan khawatir tentang hal itu kecuali itu masalah yang sudah terbukti", saya pikir itu layak untuk dipikirkan sejak dini: pas dengan retro-solusi jauh lebih menyakitkan. Dan ya, mereka hanya memperbarui ubin 'terdekat' saja. Tetapi penyimpanan dan kemudahan pengangkutan item di dunia game Anda secara efisien sangat penting karena alasan kinerja.

Apa yang sebenarnya Anda pikirkan di sini adalah kumpulan data yang jarang: sesuatu di mana indeks potensial besar (atau tidak terbatas), tetapi hanya sebagian kecil yang benar-benar digunakan. Poin kuncinya adalah Anda tidak tahu persis proporsi mana yang akan digunakan.

Solusi standar untuk masalah set data yang jarang adalah dengan memisahkan indeks / addressability dari penyimpanan data aktual. Jadi jika objek ubin itu mahal, maka simpanlah dalam bentuk yang ringkas (mis. Array datar). Tetapi biarkan diindeks melalui objek yang lebih murah. Dalam bentuknya yang paling sederhana, ini bisa berupa matriks 2D (atau 3D) yang dapat Anda indeks dengan mudah berdasarkan koordinat, tetapi setiap item dalam matriks hanyalah sebuah indeks. Anda kemudian menggunakan indeks itu untuk mencari konten ubin yang sebenarnya dalam array yang terpisah dan kompak. Jika konten ubin belum ada, kemudian tambahkan ke akhir array, dan simpan indeks dalam matriks 3D.

Solusinya menjadi lebih kompleks jika Anda ingin mendukung penghapusan konten (karena mengarah pada fragmentasi array konten), dan jika konten ubin Anda murah, maka bobot tambahan indeks (indeks 32-bit atau 64-bit) mungkin akan membanjiri tabungan karena tidak menyimpan setiap ubin potensial. Ini juga merupakan pencarian tambahan, yang akan merusak kinerja cache Anda.

Anda bisa mendapatkan efisiensi penyimpanan yang lebih besar dengan memperkenalkan lapisan tipuan ekstra. Katakanlah Anda mengatur ubin Anda menjadi potongan-potongan, dan potongan memiliki rincian 64x64x64. Diberi ubin pada 125, 1, 132, Anda tahu itu milik bagian (1,0,2). Jadi Anda memiliki dunia, yang terdiri dari array chunk kompak, dan matriks indeks chunk (-1 jika chunk tidak ada). Isi setiap potongan (jika ada) adalah matriks indeks ubin 64x64x64 (-1 jika ubin belum ada), dan susunan kompak ubin yang digunakan. Dengan cara ini, Anda tidak membakar sejumlah besar indeks ubin untuk bongkahan yang tidak pernah digunakan. Dengan mengikuti pendekatan semacam ini, dan memilih angka yang masuk akal untuk granularity chunk, Anda dapat meningkatkan semesta Anda secara besar-besaran, dan menjaga penggunaan memori Anda tetap terkendali. Sebenarnya, jika Anda membuat potongan 32x32x32,

Anda juga dapat melakukan trik licik, seperti menggunakan bit orde tinggi dari indeks chunk atau tile Anda untuk mengartikan sesuatu yang istimewa. Jadi jika entri dalam matriks ubin memiliki set bit atas, maka 31 bit yang lebih rendah tidak berarti indeks ubin, sebaliknya mereka berarti 'indeks warp' atau sesuatu yang serupa, dan Anda dapat melihat itu di daftar yang dikelola secara terpisah. untuk mengetahui koordinat yang dituju.

Mengapa Anda tidak bisa menyimpan satu juta ubin dalam memori? Bahkan ponsel saya memiliki 256MB RAM; sejuta ubin kosong akan menjadi apa, 4-32MB?