Version Control for Save Data

Question

So I have this tile-based game (something like Farmville). As "tile-based" implies, the save data could potentially become very large. Game saves are stored on cloud, and any change to the save data forces me to send the whole save file to the game client, which you can imagine is terribly inefficient if the changes are very small (changing even a single tile will trigger sending of all the save data).

I'm looking at the possibility of version control to mitigate the network load. In this solution, I imagine that:

1. The client sends the server a version number.
2. The server matches the number to an older version of the savefile and compares it with the latest version.
3. The server sends a diff file back to the client, which uses it to interpret and re-produce the latest version, along with the latest version number for future reference.

How can I implement this?

Answer 1

Instead of sending the whole map on every load and save, divide your game map into rectangular blocks of tiles (chunks) and implement a network protocol to save/load individual chunks.

When a client connects, it requests only the chunks around the player. When the player moves, the client requests additional chunks around their new location. That way the client won't download any parts of the map it won't need anyway.

When a client saves, it only uploads those chunks to the server which it changed since the last save.

Further, in most games the map information is quite suitable for compression with stock compression algorithms. So you might shave off some traffic by compressing the map chunks with an algorithm like LZMA, DEFLATE, bzip etc. before sending them over the network.

Answer 2

In addition to storing the whole map on the server, store a journal of the map. This is a list of structures with 3 fields:

• x-coordinate
• y-coordinate
• tile state

The list index is the version number.

Whenever a map tile is changed, add a new entry for that tile to the journal.

When a client requests to be updated from version n, then:

• Create a temporary empty map (empty as in "no tile at all", not "empty grass tile")
• Traverse the journal from n to end updating that temporary map in order of journal entries.
• The result will be a mostly empty map with only those tiles set which changed since version n. Run this map through a compression algorithm like LZMA, DEFLATE or bzip. They will reduce the space which is taken up by empty sections considerably.
• Send this compressed delta-map to the client
• On the client-side, uncompress the map
• Iterate the map from the network and copy it to the local map, while skipping those tiles which are empty.

To avoid running out of storage for the journal, you might want to limits its maximum size to a few hundred to a few thousand versions by discarding older versions. When a client requests to be updated from a version which was already discarded, just send them the current map.

Answer 3

This sounds like a very odd use case. Are you sure you're not looking for a more all-encompassing solution than you actually need? There are several approaches you could apply to a map to make it possible to have it be expansive and yet still small:

1. Sparse data structures E.g. if your world is mostly grass that the player has to traverse, with a few "islands" or terrain actually modified by a player, you can save only the parts the player actually modified, and whenever the game is asked to show an area that isn't in your save game, you just return a default tile (in our example, grass).

2. Palettes Many maps contain repeating patterns. E.g. long stretches that are only grass, or maybe a building's roof is always made up of two start tiles, an arbitrary number of pairs of middle tiles, and then two end tiles. When you transfer it, instead of sending these tiles individually, what you can instead do is just have a "palette" stored locally that contains the two start tiles in the right arrangement, a pair of middle tiles, and the two end tiles, each given a number, and transmit 3 special codes that say "palette entry 1", "palette entry 2", "palette entry 3".

3. Run-Length Encoding Often maps also contain long stretches of identical information. A common mechanism to reduce that is to just send a number with every tile. So instead of "roof start", "roof middle", "roof middle", "roof middle", "roof end", you transfer 1x "roof start", 3x "roof middle", 1x "roof end". Now while maps that have few repeating items may use more room to represent this information, repetitive maps collapse so much that they'll usually balance things out again.

4. Repeat codes Similarly, you can add a buffer in which you remember the last row (or whatever unit you choose) you received, and then add a simple "repeat last row" code. So if you have a stretch that is all the same tile, you transfer one row of that tile, and then 10 short codes saying "again". There are even more complex ways to do this.

   E.g. HyperCard had a B/W graphic format where they even XORed together the previous row with another one. That way, they were able to re-transmit only the different parts of a row, and generate three repeating patterns out of two repeats interrupted by a different one.

   E.g. a checkerboard pattern is every other pixel is black, but among three rows, every other row is the reverse. If you then just say "512x black XORed onto the previous white/black row", you get black/white row instead. with much less information. Basically, a checkerboard turns from uncompressable into one row of black/white pixels followed by a bunch of "repeat inverted" codes.

5. Selective Updates By remembering the size and position (in tile coordinates) of a block of tiles, you can re-transmit arbitrary subsections of a map. If a single tile changes, you only transmit that one tile's new value and tell your app "insert that at position 100,100. Or insert this 4x3 block of tiles at position 17,2 (effectively overwriting the tiles from 17,2 to 21,2 and 17,3 to 21,3 and 17,4 to 21,4).

6. Information Reduction This is like Mipmapping in computer games: If you know your player will be zoomed out very far, try to transmit less information first that looks the same. E.g. if a user is zoomed at 1/4th, you could transmit only 1/4th of the tiles. If there are squares of the same tiles, just transmit the one larger tile. And then only transmit more detailed information for areas that contain more information, or even that you know the user is working with.

   This could e.g. mean that you show certain houses slightly wrong in the zoomed-out version, and as you zoom in make them look more right. What you can do here depends heavily on the tiles you have and what is important in your game.

   Only when the user actually clicks a certain tile in a huge, zoomed-out map, you could then load the information you need to let them manipulate those tiles in detail, and render it with more precision, scaled down. And you could of course do like progressive loading of images in older browsers used to work, where you first get the low-res version of the map, and then slowly you load more detail. The low-res version lets the user orient themselves and move the mouse to where they want to manipulate, and by that time the high-res version may have been loaded in the background.

7. Generation Numbers Whenever something on the map is changed, you increment a "generation" counter you have, and you remember that number on each tile when you change it. It is like a "last changed" timestamp on a file, just that we don't use wall time, because we don't really care about the seconds it took to make the actual change on our server, or the time that goes by while the user is logged out. Now, when your user logs into the server, they can tell you "this is the last time stamp I've seen" and you can just collect all tiles that have a bigger generation number than that and send them back.

You're not really saying much about your game and how it'll actually work, and why maps can be this large that transferring this data would be a problem.