How to efficiently store a large amount of data?

Question

I am doing minecraft-like game. I have a limited world in size 32x16x32 chunk. Each chunk is a structure in which there is a three-dimensional array containing the values ​​of the blocks located in it. Structures and arrays are so arranged that from world coordinates I can get the block number that I need and its value. When you start the program, the world is generated, but I need to save all these block values ​​in a file so that when the world changes, these changes are saved after exiting the program. How do I need to organize the recording of data chunks to a file so that it is productive and economical in terms of memory occupied?

Let structures and arrays be declared as c [32] [16] [32] - structures int block_id [16] [16] [16] - block id

Answer 1

First of all, consider if it is actually necessary to break down the world into units of storage. 32x16x32x16x16x16 = 67,108,864 blocks. When each block is a 2 byte integer representing the type-ID, your world is just 128MB of data. All but the most low-end platforms should be able to handle that in-memory. But let's assume that you already tried that and came to the conclusion that you do need to persist and retrieve individual chunks to/from the filesystem.

---

You are usually going to load and store complete chunks, so the data of each chunk should stay together. Serializing and deserializing a fixed length array to a file is trivial, and stackoverflow should provide plenty of code examples. So I don't think I need to get into more detail here.

Now about how to organize the chunks into files.

Quick and dirty solution: use the filesystem. Save each chunk to one file with a naming convention which includes the coordinates of the chunk (like world1_15_12_27.chunk). Let the operating system worry about organizing and finding those files.

More sophisticated solution: Use an embedded SQL database. I made good experiences with SQLite for single-user applications, but there are alternatives available which might be worth looking at. Create a table chunks with the primary key INTEGER x, INTEGER y, INTEGER z and a non-key field BLOB data which contains the serialized data of the chunk. A "SQL by the book" solution would be to normalize the chunk data, but I would advise against it, because as previously said, your primary use-case is to save and load whole chunks. You are not going to query the database for individual blocks.

Using blobs also gives you the option to run your chunks through a stock compression algorithm like LZMA, DEFLATE, bzip etc. to reduce the size of your database. It might seem unintuitive, but compressing your chunks might in some cases actually improve loading times, because reading data from the filesystem can take longer than running it through a decompression algorithm.

"Not Invented Here" syndrome solution: Instead of using a ready-made embedded database, invent your own world file format which provides database-like indexing.

When you invent your own format, keep in mind that most storage media are optimized for reading and writing data in sequence. Seeking to a different position within a file is often a slow operation (this changed a bit with solid state drives, but it's still the case). So you should keep data which is usually loaded at once in continuous sections to avoid jumping around in the file.

A simple solution could be to start the file format with an index, followed by the chunks. The index lists all chunks contained in the file and where each chunk begins. Read the index first, then seek to that chunk within the file. When your chunks always have a fixed size (you are not using compression) and the whole world is generated at startup (as opposed to Minecraft which generates chunks on-demand), then the index might be unnecessary because you can simply calculate the starting position of each chunk and seek to it. position = chunk_size * (x + y * 16 + z * 32)

I'm looking forward to playing your game.

Answer 2

What if you didn't actually need to store all of those blocks?

I mean, you generate all of the world base at the start of the game from seed anyways, right? So, why not just store changes to the world that player made? I don't think that the amount of changes will ever be that huge it will perform worse than just straight loading the whole world from the disk.

So, when the changes are loaded, you just need to sequentially apply them to the memory that you store your world data in.

You might say, well, if, for example, changes are spread all over the world, it could cause lots of cache misses, since we apply changes one-by-one to (possibly) completely different parts of the computer memory.

And I think that this can easily be fixed by grouping the changes based on their memory location when saving.

Answer 3

Aside from databases and so on, one efficient choice is a multi-level storage bitmap. Basically, a storage bitmap uses a "1" bit for data, and a "0" bit for no-data. There's a balance depending on how barren your data is, but I think a balanced alternative would have 4-5 levels of bitmaps, resulting in a maximum of 8 MB of bitmaps assuming all cells are filled. The algorithm quickly becomes efficient as the data density drops. The break-even point would be at about 87.5% cell density, the lower your data, the more impressive it can become.

Basically, each chunk is stored on the disk only if it has at least 1 object. This bitmap requires up to 2kb of initial storage data. For each present chunk, break it in to 4x4x4 sub-chunks. This results in a 8 byte bitmap per present chunk.

From there, subdivide those in to 2x2x2 chunks, which requires a 1 byte bitmap each. Finally, one last byte bitmap describes which of the 8 cells are populated in this area. After that, it becomes trivial to just read the object data in sequential order.

If your data density is far less than 50%, one final super-chunk bitmap could cut down the chunk bitmap by adding a small 32 byte super-chunk bitmap for each 4x4x4 super-chunk that contains at least one chunk.

To read the data, simply start from the top bitmap and initialize a counter. For each bit, check if it's a 1, and if so, start processing the next smaller sub-area. After each bit, increment the counter by 1 to keep track of what you're doing. This is basically recursive logic, so some optimization is possible here.

To write the data, initialize a full set of empty maps for each possible level. Then, for each cell, set the appropriate present bits. Finally, output each of the non-zero bitmaps in order from the chunk/super-chunk level down to the cell level.

For performance, you can interleave the objects with the bitmaps; every time you output a 2x2x2 bitmap, output all of the objects in bit order. Other designs are possible too, but this is probably the most straightforward and facilitates sequential reads/writes for optimal saving/loading times.

As you can see, Minecraft itself uses a similar structure, a Region format. A region is a set of chunks stored by proximity, which in turn has a bunch of chunks in it. Note that they use separate files, but for a file the size you're talking about, one region is probably acceptable.