Cara untuk menyimpan data peta 2D yang berpotensi tidak terbatas?

29

Saya memiliki platformer 2D yang saat ini dapat menangani potongan dengan 100 kali 100 ubin, dengan koordinat potongan disimpan sepanjang, jadi ini adalah satu-satunya batas peta (maxlong * maxlong). Semua posisi entitas dll, semuanya relevan dan tidak ada batasan di sana.

Masalah yang saya alami adalah bagaimana menyimpan dan mengakses potongan-potongan ini tanpa memiliki ribuan file. Adakah ide untuk format arsip biaya HD yang cepat & murah yang tidak perlu membuka semuanya sekaligus?

Blam
sumber
2
Beberapa struktur data yang dapat Anda lihat untuk mendapatkan inspirasi lebih banyak adalah matriks jarang dan tabel halaman (multilevel) .
Andrew Russell
Prioritas rendah: Bisakah Anda mengklarifikasi apakah tipe data "panjang" adalah 32- atau 64-bit?
Randolf Richardson
2
@ Randolf mengingat bahwa ini adalah C #, mungkin dia berarti C # longyang 64-bit (jadi maxlong adalah Int64.MaxValue).
Andrew Russell
Notch memiliki beberapa hal menarik untuk dikatakan tentang peta tak terbatas di Minecraft di blognya di sini: notch.tumblr.com/post/3746989361/terrain-generation-part-1
dlras2

Jawaban:

17

Buat format peta khusus untuk gim Anda. Ini lebih mudah dari yang Anda kira. Cukup gunakan kelas BinaryWriter. Pertama, tulis tajuknya dalam beberapa int atau uint. Informasi untuk dimasukkan dalam header:

  • String ajaib / angka ajaib dari format file Anda.
  • Awal / akhir / ukuran potongan yang dijelaskan dalam file ini

dan juga (dan inilah bagian penting kinerja

  • int yang menggambarkan posisi awal di dalam file. Jadi, Anda tidak perlu mencari potongan tertentu.

Dengan metode di atas, Anda dapat (dan seharusnya) membuat indeks isi file Anda, berisi semacam deskripsi (nama yang ditentukan pengguna untuk wilayah / chunk, atau hanya koordinat) dan sebagai nilai kedua posisi dalam file.

Kemudian, ketika Anda ingin memuat potongan tertentu, Anda hanya perlu mencari di dalam indeks. Ketika Anda mendapat posisi, atur saja fileStream.Position = PositionOfChunkFromIndex dan Anda dapat memuatnya.

Ini semua tentang desain format file dengan header yang menjelaskan konten file paling efisien.

Simpan saja file dengan ekstensi khusus yang Anda buat dan mulai lagi.

BONUS: Tambahkan kompresi BZip2 ke wilayah tertentu dari file / seluruh konten (bukan header !!), sehingga Anda dapat membongkar potongan tertentu dari file, untuk jejak memori yang sangat kecil.

Riki
sumber
12
Layak untuk ditunjukkan bahwa, jika Anda akan memodifikasi file ini sambil jalan, Anda akan menginginkan header / indeks berukuran tetap atau eksternal, sehingga Anda dapat menambahkan potongan ke file tanpa harus menulis ulang seluruh file (karena perubahan offset).
Andrew Russell
Pada titik itu, bukankah Anda hanya mengimplementasikan database flatfile?
Kera-inago
13

Saya mengalami masalah yang sama dan memutuskan untuk membuat struktur sendiri untuk menangani data. Ini didasarkan longgar pada quadtree, tetapi memiliki ekspansi yang tak terbatas (setidaknya sebesar Int) di semua arah. Itu dirancang untuk menangani data berbasis grid yang diperluas dari titik pusat, seperti Minecraft sekarang. Ini adalah ruang yang efisien dalam memori, dan sangat cepat.

Anda dapat menentukan besaran minimum untuk setiap node (besarnya 7 akan menjadi 128x128) dan sekali setiap node memiliki persentase tertentu dari subnode yang dihuni, ia secara otomatis meratakan dirinya sendiri ke dalam array dua dimensi. Ini berarti bahwa bagian yang sangat padat (mis., Benua yang sepenuhnya dieksplorasi) akan memiliki kinerja array (sangat cepat) tetapi bagian yang jarang penduduknya (misalnya, garis pantai seseorang berkeliaran ke atas dan ke bawah tetapi tidak menjelajahi pedalaman) akan memiliki kinerja yang baik dan penggunaan memori yang rendah.

Kode saya dapat ditemukan di sini . Kode lengkap, teruji (tes unit dan beban), dan cukup optimal. Namun, cara kerja bagian dalam belum terdokumentasi dengan baik, tetapi semua metode publik harus digunakan. Jika ada yang memutuskan untuk mencobanya, jangan ragu untuk menghubungi saya dengan pertanyaan atau komentar.

Saya belum menggunakannya untuk menyimpan data ke file, tapi ini masalah yang menarik dan saya mungkin akan mengatasinya nanti.

dlras2
sumber
Jadi ini pada dasarnya adalah pohon yang dapat diupgrade, bukan? Apa yang saya lewatkan?
kaoD
2
Peningkatan terbesar atas pohon yang dapat diupgrade adalah bahwa ia 'meratakan' simpul tertentu dari pohon yang padat penduduk (default 70%) ke dalam susunan 2D, daripada membuatnya terstruktur seperti pohon. Ini memberi Anda kecepatan pencarian array, tanpa ukuran (tak terbatas) dari array yang tak terbatas.
dlras2
Baik simpul daun dan dalam, kan? Ide yang menarik, mungkin memberikan hasil yang baik, saya akan mencobanya jika saya membutuhkan ini. Btw, +1 untuk memberikan kode dan jawaban cepat! Oh, dan pengujian unit juga dilakukan, saya (sayangnya) tidak pernah melakukan itu dalam proyek pribadi saya :)
kaoD
Kami tidak melakukan pengujian unit di tempat kerja saya, jadi sayangnya cara saya memberontak .. Saya membuat aplikasi demo untuk itu, yang menunjukkan bagaimana itu mengisi dan meratakan, jadi jika saya dapat membersihkannya dalam beberapa berikutnya hari jadi layak, saya akan mempostingnya di sini juga. Lebih masuk akal bila Anda melihatnya.
dlras2
1
Saya lupa melihatnya, maaf! Saya masih ingin membersihkannya, tapi saya perlahan-lahan mengerjakan ulang beberapa kode antara kelas dan pekerjaan rumah, sehingga tidak akan lama. Untuk saat ini, demo lama yang tidak cantik ada di sini: j.mp/qIwKYt Secara un-pretty, sebagian saya maksudkan itu membutuhkan banyak penjelasan, jadi jangan lupa membaca README dan jangan ragu untuk bertanya di sini atau melalui email.
dlras2
3

Anda dapat menggunakan database sebagai gantinya - PostgreSQL memiliki beberapa kemampuan pengindeksan khusus yang dioptimalkan untuk jenis data yang terletak oleh koordinat X dan Y. Anda juga dapat menentukan bahwa data yang dikembalikan berada dalam radius tertentu daripada di daerah berbentuk persegi atau bujur.

  PostgreSQL (sumber gratis dan terbuka)
  http://www.postgresql.org/

Ada juga basis data lain, dan untuk sisi klien Anda mungkin menemukan tipe tertentu lebih cocok untuk ini karena mereka dapat berjalan sendiri (diprakarsai oleh aplikasi klien game Anda) atau dapat dimasukkan sebagai bagian dari perpustakaan kode Anda bisa "gunakan saja." Keuntungannya adalah Anda tidak perlu merancang skema pengindeksan karena sebagian besar mesin database SQL sudah melakukan ini dengan cukup baik.

Keuntungan dengan pendekatan database adalah bahwa Anda dapat membuat potongan Anda lebih kecil (atau menyingkirkan potongan sepenuhnya dan hanya menggunakan ubin langsung, tetapi penggunaan setidaknya potongan kecil / kelompok banyak ubin mungkin lebih efisien tergantung pada desain Anda), dan kemudian menggunakan kueri SQL untuk membawa area yang lebih besar daripada yang dapat dilihat. Dengan pra-pemuatan untuk tumpang tindih dengan area yang tidak dapat dilihat di dekatnya, ubin dapat disiapkan sebelum pemain memindahkan karakter mereka, menghasilkan pengalaman bermain game yang lebih baik (semoga lebih mulus).

Saya perhatikan bahwa beberapa game menyimpan "cache" dari data peta pada hard drive lokal setelah mendapatkannya pertama kali (ini tidak diragukan lagi untuk mengurangi I / O jaringan), seperti Ashen Empires:

  Ashen Empires (gratis untuk bermain, implementasi 2D yang indah)
  http://www.ashenempires.com/

Melacak stempel waktu "terakhir diperbarui" dengan setiap potongan / ubin juga akan membantu karena, untuk tempat data yang disimpan secara lokal tersedia, kueri SQL dapat menyertakan klausa "WHERE timestamp_column> $ local_timestamp" tambahan sehingga hanya potongan / ubin yang diperbarui yang mendapatkan diunduh (dua manfaat dari menghemat bandwidth seperti ini adalah biaya konektivitas yang lebih rendah, dan sedikit lag untuk pemain Anda, yang akan menjadi lebih jelas ketika permainan Anda menjadi populer).

Tangkapan layar dari Ashen Empires (beberapa karakter ada di bank lokal, dan dari penampilan tulang-tulang itu di lantai, sepertinya beberapa monster kerangka pasti telah mengembara dan kemungkinan dibantai oleh penjaga kota setempat):

masukkan deskripsi gambar di sini

Randolf Richardson
sumber
2

Jangan menyimpan dan mengaksesnya, simpan hanya benih acak yang diperlukan serta perubahan pemain ke peta. Kemudian hasilkan porsi yang diperlukan saat run-time (jalankan algoritme pembuatan Anda, lalu terapkan perubahan pemain). Dengan prosedur pembuatan yang benar dan konsisten, peta yang dihasilkan akan selalu sama untuk seed awal yang sama.

Secara teoritis Anda dapat melakukan peta yang benar-benar tak terbatas yang akan menyimpan ke file yang sangat kecil dengan cara ini.

kode sh
sumber
@Josh Petrie terima kasih atas koreksi bahasa / gaya yang signifikan dan luar biasa pada posting saya. Sayang sekali saya tidak bisa memutakhirkan hasil edit :-D
kode sh
1

Apakah ada cara Anda dapat mempartisi potongan (semacam 'subkontinen / negara' di dunia Anda)? Jadi mungkin Anda dapat memiliki beberapa jenis file indeks yang memungkinkan Anda dengan cepat menemukan sub-file / bagian mana dari file yang lebih besar yang perlu Anda muat untuk memiliki sebagian dalam memori ...

dokter hewan
sumber
selalu ada cara Anda dapat mempartisi potongan. SELALU. apakah mereka dapat dilihat oleh pemain / relevan dengan seluruh sistem atau tidak, selalu ada cara untuk membagi data dunia menjadi bongkahan, biasanya dengan berbagai cara.
kode sh
0

Anda bisa mengambil ide dari Minecraft. Awalnya mereka memiliki file per chunk. Sekarang mereka menggunakan format MCRegion, yang mengelompokkan potongan menjadi area 32x32 dan menyimpan salah satu dari mereka per file.

Bebek Komunis
sumber