Apa format file flat yang baik untuk menyimpan peta ubin 2D yang dapat tumbuh tanpa batas ke segala arah?

Saya membuat mesin peta sederhana yang secara otomatis akan berkembang ke segala arah dengan konten yang dihasilkan secara prosedural sesuai kebutuhan.

Apa cara yang baik untuk menyimpan data peta, berlabuh pada asal 0,0 sehingga subset persegi panjang dari data peta dapat dimuat dengan cepat dan efisien dari titik mana pun di peta?

Saya punya ide bahwa mungkin saya harus membagi peta ke sektor yang berbeda dan kemudian menggunakan semacam format header untuk mengidentifikasi di mana dalam file sektor tertentu disimpan. Apakah ini teknik yang baik atau apakah ada teknik yang lebih baik, lebih efisien yang bisa saya lihat?

Saya akan menyarankan agar tidak menggunakan file flat tunggal untuk jumlah data yang secara teori tidak terbatas.

Jika Anda memiliki jumlah data yang tidak terbatas secara teoritis maka Anda memerlukan akses acak , yang berarti banyak file atau database - atau format file datar yang diindeks, yang melibatkan pemecahan masalah indeks yang sudah diselesaikan oleh sistem file atau database.

Jika Anda menyebarkan potongan-potongan Anda di beberapa file, mendapatkan potongan di (-110, 5000) hanya masalah mengatakan "% APPDATA% / game / map / -110 / 5000.dat" (atau nama file lain jika Anda ingin mulai mengompres mereka). Database hanya perlu kueri. Jika sepotong tidak memiliki data, Anda tidak bisa menyimpan apa pun. Satu file datar tidak menawarkan kecepatan dan kenyamanan akses acak langsung.

Dalam satu file ukuran sewenang-wenang, untuk akses acak cepat Anda harus memiliki jaminan untuk posisi setiap potongan data, yang berarti menggunakan indeks (karena pencarian biner mentah melalui potongan data Anda akan merusak kinerja, dan membuat kisi di file dengan "kosong" tempat memberi Anda masalah Byte56 ). Setelah Anda mengembangkan sistem pengindeksan, berikan efisiensi dan tulis sendiri API, Anda telah membuat ulang sesuatu seperti sistem file atau database. Kecuali Anda benar-benar mendapatkan sesuatu dari melakukan itu mungkin tidak sepadan dengan investasi. Misalnya, Steam mendapat manfaat besar-besaran dari format file GCF / NCF mereka.

Jika Anda ingin beberapa keamanan disimpan, Anda masih bisa melakukannya. Misalnya, Anda dapat mengenkripsi setiap potongan individual. Untuk mencegahnya dihapus, Anda dapat memiliki hash pusat berdasarkan data yang tersimpan. Jika data yang disimpan tidak cocok dengan hash (dan program Anda tidak menyebabkan perubahan), sebagian telah dihapus.

Solusi yang paling sering digunakan adalah memecah menjadi banyak file, namun pertanyaan Anda tidak menyiratkan satu file saja. Satu-satunya pilihan yang masuk akal untuk ini (menurut saya) adalah meniru sistem file yang sangat sederhana di dalam file tunggal itu. Ini sebenarnya tidak terlalu sulit untuk dilakukan, tetapi Anda benar-benar harus mempertimbangkan untuk menggunakan banyak file jika Anda bisa.

Jika Anda harus tetap berpegang pada satu file, maka Anda mungkin menemukan inspirasi untuk implementasi Anda dari ext2 fs. http://en.wikipedia.org/wiki/Ext2 Saya tahu itu membantu saya membuat beberapa keputusan bagus ketika saya harus mengimplementasikan FS sederhana untuk sebuah game.

Tapi sungguh, untuk setiap peta yang tumbuh, biasanya lebih baik hanya menggunakan file untuk setiap potongan "yang diakses".

Saya menerapkan sistem chunking untuk permainan saya ketika saya mengutak-atik dunia tak terbatas (tidak yakin apakah saya akan menyimpannya atau tidak). Untuk digunakan dengan satu file, pada awalnya saya menggunakan posisi dunia chunk untuk menghitung byte offset ke dalam file. Ini mengasumsikan ukuran potongan statis, atau setidaknya maksimum statis. Namun, jika pengguna untuk pergi ke satu arah untuk sementara waktu, file ini akan menjadi sangat jarang karena ukurannya, karena ada area besar tanah yang belum dihasilkan sehingga ada ruang kosong di file.

Saya juga mencoba sistem dua file. Satu file memegang peta "chunk position" hingga "chunk file offset" berpasangan. Yang kedua memegang semua bongkahan. Ketika sebuah chunk baru dihasilkan, itu hanya berjalan di akhir file chunk, dan offset itu disimpan dalam file position-> offset. Yang ini adalah masalah ketika Anda memiliki BANYAK potongan dan menemukan offset di posisi-> file offset memerlukan sedikit waktu. Jika Anda merasa layak, Anda dapat memuat data posisi-> offset ke dalam hash-map on load, untuk memiliki akses cepat.

Saya menggunakan opsi yang kedua untuk saat ini, tetapi dapat beralih ke hal lain jika saya menemukan bahwa kinerjanya kurang. Mungkin dengan informasi ini Anda akan dapat membuat sesuatu yang bekerja untuk Anda. Semoga berhasil!