Caching for multiplayer map download

[DarkShadow44]

TL;DR

Allow multiplayer maps to be cached so only the changed parts need downloading, decreasing download time.

First off, this is nothing I realistically see being implemented, although a guy can dream

Why ?

Maps that get explored a lot can get pretty big, especially when using mods like SpaceExploration.
This is a problem when playing on a server, since every reconnect requires a full map download. When not using a dedicated server, that is usually limited by the hosts upload speed. For big maps, this takes quite some time. Afterwards we need to "catch up" when the server wasn't paused, exacerbating the problem. When your save is bigger than 100MB, or even 250MB, this is very painful.
One crash due to a mod misbehaving, and you need to do it all over again. Caching to reduce the download time would help alleviate those problems.
Those threads come up from time to time, for example here: viewtopic.php?t=92114
Necessary for vanilla? Probably not. With mods it would be very useful, though.

How ?

I came up with an idea how it could be handled, that I'd like to put up for discussion.
My idea is caching the map on the client: After a successful connect to the server, the client saves the map as "checkpoint save".
When the next time the save is played, we can make the following assumption:

• All factory elements, pollution, enemies, and so on will most likely change.
• The explored but not touched terrain is probably still the same - we'll call that "probably not changing data"
  This would include tiles, trees, resources, decorations and maybe more.

So, when connecting to the server again, we can use that checkpoint to decrease the amount of transmitted data.
A connection would look like this:

• Client can always request a full map transfer, or a partial map transfer
• For a full map transfer, we use the existing logic. Otherwise:
• Server calculates a checksum(md5) for each chunk, only including the "probably not changing data".
• Send list of chunk coordinates with their checksums to the client
• Client compares the checksums to the chunks it has from the "checkpoint". Client drops all chunks the server doesn't have.
• Client sends the server a list of chunk coordinates that it does not have
• Server sends map data, excluding the "probably not changing data" for the chunks the client already has
• Client downloads partial map and merges it with the "checkpoint"

Finding the correct checkpoint for a save could go by the map name, or perhaps the seed - since the same seed should yield the same map.
All transmissions would again be zlib compressed, to minimize data needed to transmit.

Of course I don't know exactly how factorio serializes the saves, or how easy that would be to implement. But theoretically this should allow us to cut transmitted map size by quite a margin for maps that have a lot of untouched explored terrain.

Thoughts and comments?

[ssilk]

Lately I had the insight, that for really big maps it is more and more uncertain that a chunk gets modified ever. You have chunks, that include your factory and more chunks that you maybe have killed some trees, but the big, big normality are chunks, you never even have walked on.

Those chunks need not to be included in the safe-file. Because they can be recomputed with the map-generator… it takes a while but you probably will never notice it, because you never walk on it. Map: Until a chunk gets regenerated you see a (cached) version of the map-part.

[DarkShadow44]

Those chunks need not to be included in the safe-file. Because they can be recomputed with the map-generator… it takes a while but you probably will never notice it, because you never walk on it. Map: Until a chunk gets regenerated you see a (cached) version of the map-part.

You mean just the map preview would be saved? Interesting idea. How would that work for resources? And for enemies? AFAIK as soon as they are generated, they can expand. Or killed with artillery.

Another point, when building a railtrack, all chunks around could be excluded from the save, right? Now what happens when I drive the train, will the generation make the game crawl to a halt? We'd probably need to include at least all chunks that are visible from a player structure.
Similar issue I see with artillery, is it really not a problem to regenerate all the chunks?

As soon a a chunk is touched, you need to save it though. Imagine me crashing into trees/rocks while searching for resources, and this means a lot gets touched. Similarly, when you just build a long rail-track, this would prevent chunks from being excluded.
In that light, is it really a problem when the local save is big? Because I only see the problem for multiplayer.

Anyways, I'd like to play around with that idea, just to see how it plays - but that's hardly possible without it being implemented first. A bit of a chicken-egg problem here.

[ssilk]

How would that work for resources? And for enemies? AFAIK as soon as they are generated, they can expand. Or killed with artillery.

Ressourcen are part of the generated map.
Enemies: well, yes, kind of problem. The entities need to be saved of course, because the all have a state. Growing biter nests is also a problem, because that changes also the map.

But the changes are only in a limited area around the nests.

Also a problem: the biters change the map by eating trees, if they are in the way.

Maybe like so: if there are only some minimal changes to a chunk (missing some trees, added some worms…) the changes can be applied as diff after the generation of the chunk.

Another point, when building a railtrack, all chunks around could be excluded from the save, right? Now what happens when I drive the train, will the generation make the game crawl to a halt? We'd probably need to include at least all chunks that are visible from a player structure.
Similar issue I see with artillery, is it really not a problem to regenerate all the chunks?

Well, the game can become laggy, if it wants to generate too much chunks at once. But that’s it. So if you drive very fast (e.g. airplane) in one direction you can come to a point, when you don’t see a map on your ground anymore. That is a bit of problem with big maps, because they also tend to be quite CPU intensive. But chunks are generated in background, threaded, so this is not so slow as you might think.

As soon a a chunk is touched, you need to save it though. Imagine me crashing into trees/rocks while searching for resources, and this means a lot gets touched. Similarly, when you just build a long rail-track, this would prevent chunks from being excluded.
In that light, is it really a problem when the local save is big? Because I only see the problem for multiplayer.

Na, single player also has this problem. I had saves where loading needed 2-3 minutes, saving 5. Mainly because of the large areas I discovered.

Anyways, I'd like to play around with that idea, just to see how it plays - but that's hardly possible without it being implemented first. A bit of a chicken-egg problem here.

I think this could be implemented by a mod.
There are already mods that delete unused chunks:
https://mods.factorio.com/mod/DeleteEmptyChunks
https://mods.factorio.com/mod/unused_ch ... val_rework
https://mods.factorio.com/mod/CleanMap

This algorithm could work so:
- find unused chunks, store the coordinates in the mod for saving.
- delete unused chunks before saving.
- on load recover the chunks in kind of background process

[DarkShadow44]

Maybe like so: if there are only some minimal changes to a chunk (missing some trees, added some worms…) the changes can be applied as diff after the generation of the chunk.

Possibly. But that doesn't sound too easy either. Especially not for a mod...

Na, single player also has this problem. I had saves where loading needed 2-3 minutes, saving 5. Mainly because of the large areas I discovered.

May I ask how big that save was? For me, I can load even 200MB maps in a few seconds. Loading from a SSD?

I think this could be implemented by a mod.
There are already mods that delete unused chunks:
https://mods.factorio.com/mod/DeleteEmptyChunks
https://mods.factorio.com/mod/unused_ch ... val_rework
https://mods.factorio.com/mod/CleanMap

Maybe, but only partially. All those still have the issue that modified chunks (e.g. harvested resources) are still deleted.
The mod would need to track everything that happens to a chunk (for a diff), or just one flag whether we can delete it.
What mods can't handle is the map part - deleted chunks will be black. When I explore, I'd like to keep seeing what is where. You never know when you need those resources TBH, that's the biggest deal breaker here.
Next part is enemies, you'd need to kill them over and over again if their chunks get deleted. How would you properly address that?
Last thing is probably pollution, on "barren" planets from SpaceExploration, pollution easily affects the entire planet. Would we just delete the chunks (despite the pollution in them) or would we have to keep them? Just deleting it sounds wrong to me, although it shouldn't affect the game, really.

This algorithm could work so:
- find unused chunks, store the coordinates in the mod for saving.
- delete unused chunks before saving.
- on load recover the chunks in kind of background process

Considering how long a planet scan takes in SpaceExploration, it could take hours for a big map to be fully re-generated again - even when generating chunks at full speed.

All combined, I think those are two different ideas that can cooexist. I think a diff would still make sense for multiplayer, since we could even diff chunks that aren't empty or are modified by players.

Edit:
The problem here is not the map size itself (aka size on disk), but the load time, right? What if the game could "sort" chunks, and save the chunks away from player build structures separately? That way the game could start when the "main" chunks are loaded, and continue loading the "less important" chunks in the background. Of course, if a player walks into one of those chunks we'd either need to pause or priorities loading those chunks somehow...

[mrvn]

Lately I had the insight, that for really big maps it is more and more uncertain that a chunk gets modified ever. You have chunks, that include your factory and more chunks that you maybe have killed some trees, but the big, big normality are chunks, you never even have walked on.

Those chunks need not to be included in the safe-file. Because they can be recomputed with the map-generator… it takes a while but you probably will never notice it, because you never walk on it. Map: Until a chunk gets regenerated you see a (cached) version of the map-part.

Take a mega factory in a grid pattern as example. If you explore and build more or less spherical or square shaped then the modified area would be proportional to r^2 and the unchanged part (r+x)^2 - r^2 = 2 r x + x^2. Where x is the distance of chunks getting generated from the player or the radar radius. The modified area grows quadratic with r while the unmodified only linear. So I wouldn't bet on most chunks having never been modified.

But you have a very good point: Why is any data included in the save that is identical to what it was at chunk generation? Apart from a few landfills the terrain of the map shouldn't be included at all. Sounds like it is. Trees, ore, cliffs could use 1 bit in the chunk to mark is as modified. Or generate the chunk again and compare. But that might slow down saving more than the bandwidth saving gains.

So I would go with a bitfield in the chunk to mark modifications. Fell a tree: modified.trees = true. Place a landfill/waterfill: modified.land = true. Place a miner on some ore (or hand mining ore): modified.ore = true.

Note: I would go with placing a miner instead of actually mining ore because the later would require setting the bit every time an ore is mined. Placing a miner happens rarely and you probably will power it and have it mine ore soon enough.


All of that goes towards reducing the map size that needs to be downloaded and certainly would be worth it. But I have another idea: Distribute the work.

All clients have the same map. So when a new player joins have them all save the map and each upload parts of it. You can use something like the bittorrent protocol. Split the saved map into chunks of 16-1024k and have the server checksum each chunk. Those get send to the new client. The new client then requests a few chunks from each old client and can verify the checksums to rule out transmission errors. The faster an old client uploads chunks the more chunks are requested in parallel from it so the sender doesn't run out of stuff to send. The upload bandwidth of all clients get combined.

And then take this one step further. As said all clients have the same map. And lets trust each client not to send garbage on purpose. Now split the map into regions. Could be geographically connected chunks or hash(chunk_x, chunk_y) == region_id or anything to split the map into blocks that are somewhat larger than chunks. You want a lot more regions than players but not millions either. Why not limit it to 65536 regions? The new player then requests regions from each client, the client saves the region and uploads it. As before the faster the upload from a client the more regions the client requests in parallel. That way each client would save the next region for upload while uploading the previous and no client is idle during map upload. No need for the server to save a 300MB map and upload it all on it's own.

[mrvn]

The problem here is not the map size itself (aka size on disk), but the load time, right? What if the game could "sort" chunks, and save the chunks away from player build structures separately? That way the game could start when the "main" chunks are loaded, and continue loading the "less important" chunks in the background. Of course, if a player walks into one of those chunks we'd either need to pause or priorities loading those chunks somehow...

That could mostly work. But there are mods like AAI that have entities that scan chunks. They take x,y coordinates from a circuit connection, count the amount of resources at that place and output that on a circuit connection. When that happens the game would have to pause, download that chunk with high priority and then hope the client doesn't get dropped from the game while waiting for it.

And what about pollution? You need to know how much each chunk absorbs and any aliens in that chunk need to remember the absorbed pollution. The number of chunks without pollution that could be saved might not be that large.

Also it's not just the player walking into one of those chunks. You need the whole visible region around the player. Everything on the minimap. God help any new player going into map mode.

More. It's any player or bot walking into one of those chunks. Or just a radar scanning one. If a radar scans a new chunk the on_chunk_generated event fires and things like RSO then can access and modify a number of chunks around it. Each one would cause the client to pause, wait to download the accessed chunk and try to catch up again. That could snowball and drop the player quickly. And as said you already need all the polluted chunks within ticks.

[quyxkh]

So, server and client share a sync-saved state, client sends server the hash of its saved state and if the server has that it does its multiplayer save as usual but transmits only the diffs. Basically a Factorio-ized rsync. The server could also keep a pristine initial save; when the server doesn't have a sync'd save for the client, as for an initial download, it could send the game-setup params, let the client generate that and verify that what the client generates for the initial map is the one it got too before initiating the connect and diff-sending.

[mrvn]

So, server and client share a sync-saved state, client sends server the hash of its saved state and if the server has that it does its multiplayer save as usual but transmits only the diffs. Basically a Factorio-ized rsync. The server could also keep a pristine initial save; when the server doesn't have a sync'd save for the client, as for an initial download, it could send the game-setup params, let the client generate that and verify that what the client generates for the initial map is the one it got too before initiating the connect and diff-sending.

Nah, rsync is more clever and that method might also work.

First rsync checks time and size of the file. So in this case it would be mod checksums and tick count and some magic to identify the game. Mod checksum and game ID have to always match. If the tick count also matches then no download is needed at all.

If the tick count is wrong, which will be always for any unpaused game, then the rsync mechanism would send checksums for each chunk. Any chunk with a different checksum then gets downloaded. All chunks unmodified since the client last got it's map don't need to be downloaded.

The beauty of this is that the server does not need to know the old state the client has. The drawback is that it has to send all data for each needed chunk, no diff. If one item moves on a belt the whole chunk needs to be downloaded.

You could combine the two. The server could save diffs and map CRCs since the last autosave or until the diff data exceeds the map size. And use the rsync method when the map CRC of the client is unknown.

[ssilk]

Take a mega factory in a grid pattern as example. If you explore and build more or less spherical or square shaped then the modified area would be proportional to r^2 and the unchanged part (r+x)^2 - r^2 = 2 r x + x^2. Where x is the distance of chunks getting generated from the player or the radar radius. The modified area grows quadratic with r while the unmodified only linear. So I wouldn't bet on most chunks having never been modified.

But you’re assuming that a mega-factory is built in a grid.
Assume maps, where ore is a really rare thing (one ore patch every 5 kilometers) and the calculations look completely different.

You can with this suddenly play games, that where impossible before, because the save would be too big.

Fell a tree: modified.trees = true. Place a landfill/waterfill: modified.land = true. Place a miner on some ore (or hand mining ore): modified.ore = true.

I would just store modification or not. Then how often this chunk has been “used” (walked over, built and removed etc.), to know how “important” it is. And then the diff to the generated version (of corse limited to “what makes sense).

… complicated mechanism to download map from other players…
No need for the server to save a 300MB map and upload it all on it's own.

I know that this is about multiplayer, but that makes too much focus on specific games with lots of players. What if you just play with two players?

You need the whole visible region around the player. Everything on the minimap. God help any new player going into map mode.

You don’t need it. The map-view is still in the save. The chunks are generated in threads. (Problem arises with modded chunk-generation, because that is about 20 times slower. But that should not yet be discussed here). It would work, it would take a bit more time, but you spare some time in downloading. After a while there is no immediate new chunk to generate and you can catch up.

More. It's any player or bot walking into one of those chunks. Or just a radar scanning one.

Yes, it would take some time to generate that all. It must be a game-option which chunks should be saved (or how much diffs should be saved until the whole chunk is saved instead, and much more of that options) and which is regenerated.

[mrvn]

Take a mega factory in a grid pattern as example. If you explore and build more or less spherical or square shaped then the modified area would be proportional to r^2 and the unchanged part (r+x)^2 - r^2 = 2 r x + x^2. Where x is the distance of chunks getting generated from the player or the radar radius. The modified area grows quadratic with r while the unmodified only linear. So I wouldn't bet on most chunks having never been modified.

But you’re assuming that a mega-factory is built in a grid.
Assume maps, where ore is a really rare thing (one ore patch every 5 kilometers) and the calculations look completely different.

True. A railworld map will have a different explore and build pattern than an island world. A grid mega factory different from a bus design. I just mend that it's not always the same. A lot of games will have just one big pollution cloud until very late in the game if ever and everything with pollution will most likely be a changed chunk. Either because the aliens evolved some or you killed them.

You can with this suddenly play games, that where impossible before, because the save would be too big.

Fell a tree: modified.trees = true. Place a landfill/waterfill: modified.land = true. Place a miner on some ore (or hand mining ore): modified.ore = true.

I would just store modification or not. Then how often this chunk has been “used” (walked over, built and removed etc.), to know how “important” it is. And then the diff to the generated version (of corse limited to “what makes sense).

… complicated mechanism to download map from other players…
No need for the server to save a 300MB map and upload it all on it's own.

I know that this is about multiplayer, but that makes too much focus on specific games with lots of players. What if you just play with two players?

If it's headless + 2 players that still 1 server + 1 player to upload. If it's one player being the server then distributing workload can't work.

One thing to consider: In a 2 player game the times that a new player joins is more rare. In a 20 player game it happens lots of times. The chance of someone dropping or taking a break gets multiplied by the number of players. Speeding up map downloads for games with more players makes more players more happy. (that's a lot of mores ).

You need the whole visible region around the player. Everything on the minimap. God help any new player going into map mode.

You don’t need it. The map-view is still in the save. The chunks are generated in threads. (Problem arises with modded chunk-generation, because that is about 20 times slower. But that should not yet be discussed here). It would work, it would take a bit more time, but you spare some time in downloading. After a while there is no immediate new chunk to generate and you can catch up.

More. It's any player or bot walking into one of those chunks. Or just a radar scanning one.

Yes, it would take some time to generate that all. It must be a game-option which chunks should be saved (or how much diffs should be saved until the whole chunk is saved instead, and much more of that options) and which is regenerated.

Oh, I would have thought the map-view would be generated from the chunk data. It's completely redundant information. If the limit is bandwidth then why include that?


Maybe first aim at a lower hanging fruit and concentrate on 2 cases:

1) player joins for the first time

Generate the terrain from the noise functions. Then download everything different from that. The server can keep a flag in the chunk if the chunk has terrain alterations and a small diff to save cpu time when generating the upload.

2) a player joins having an old map

In each chunk store the tick the chunk was last modified. The client sends the tick of it's old map and the server uploads all chunks with more recent changes.

That would probably be as simple as you can make it.

[ssilk]

A lot of games will have just one big pollution cloud until very late in the game if ever and everything with pollution will most likely be a changed chunk. Either because the aliens evolved some or you killed them.

Hmmm. Right.

Speeding up map downloads for games with more players makes more players more happy. (that's a lot of mores ).

Makes much sense, yes.

Oh, I would have thought the map-view would be generated from the chunk data. It's completely redundant information. If the limit is bandwidth then why include that?

The problem is, that you need to remember the state of the map-part from the last time it was scanned. Otherwise it can be used to cheat.

1) player joins for the first time

2) a player joins having an old map

When I think about it, I mean now it’s useless to talk about specific strategies. If it would be a project from me, I would first make some simulations of typical usage cases. I would program something, that enables me to simulate the situation, so that I easily can replace mocked load/save strategies, catching-up speed, bandwidth /-quality, probabilities that players join and much more.

[DarkShadow44]

Na, single player also has this problem. I had saves where loading needed 2-3 minutes, saving 5. Mainly because of the large areas I discovered.

May I ask how big that save was? For me, I can load even 200MB maps in a few seconds. Loading from a SSD?

@ssilk Still wondering, would you mind telling me?

All clients have the same map. So when a new player joins have them all save the map and each upload parts of it. You can use something like the bittorrent protocol.
...
No need for the server to save a 300MB map and upload it all on it's own.

Sounds usefull, although not for my usecase. I mostly play with one friend at a time. But similar to ssilks idea, I think that could exist on its own.
Dividing the upload is a good plan, but so is reducing the transmitted amount of data.

That could mostly work. But there are mods like AAI that have entities that scan chunks. They take x,y coordinates from a circuit connection, count the amount of resources at that place and output that on a circuit connection. When that happens the game would have to pause, download that chunk with high priority and then hope the client doesn't get dropped from the game while waiting for it.

True. With serialized chunks, this could pose a big problem.

And what about pollution? You need to know how much each chunk absorbs and any aliens in that chunk need to remember the absorbed pollution. The number of chunks without pollution that could be saved might not be that large.

Well, chunks with pollution need to me "high priority". For us, the polluted area is not always that big, compared to the whole explored map.
Mind you, for my approach, the pollution is't that relevant. When there is no trees, even polluted chunks don't usually change. Biters are transmitted either way.

More. It's any player or bot walking into one of those chunks. Or just a radar scanning one. If a radar scans a new chunk the on_chunk_generated event fires and things like RSO then can access and modify a number of chunks around it. Each one would cause the client to pause, wait to download the accessed chunk and try to catch up again. That could snowball and drop the player quickly. And as said you already need all the polluted chunks within ticks.

True. Maybe not the best idea after all...

So, server and client share a sync-saved state, client sends server the hash of its saved state and if the server has that it does its multiplayer save as usual but transmits only the diffs. Basically a Factorio-ized rsync.

Yeah, that's my idea in a nutshell. Just more differentiated.

The drawback is that it has to send all data for each needed chunk, no diff. If one item moves on a belt the whole chunk needs to be downloaded.

Not if you do it like I explained in the OP.

You could combine the two. The server could save diffs and map CRCs since the last autosave or until the diff data exceeds the map size. And use the rsync method when the map CRC of the client is unknown.

I think my approach is better...

You don’t need it. The map-view is still in the save. The chunks are generated in threads. (Problem arises with modded chunk-generation, because that is about 20 times slower. But that should not yet be discussed here).

Why shouldn't that me discussed here? My usecase was specially for modded playthroughs like SpaceExploration.
And generating the map from scratch might take hours there, as I already noted.

1) player joins for the first time
Generate the terrain from the noise functions. Then download everything different from that. The server can keep a flag in the chunk if the chunk has terrain alterations and a small diff to save cpu time when generating the upload.

As noted, this might take even longer than downloading for big maps. Generating chunks is expensive.

2) a player joins having an old map
In each chunk store the tick the chunk was last modified. The client sends the tick of it's old map and the server uploads all chunks with more recent changes.

Ticks won't work. What if the server loaded a backup? You'll always desync the client, without them knowing what's wrong. That's why I proposed checksums in the OP.

[mrvn]

1) player joins for the first time
Generate the terrain from the noise functions. Then download everything different from that. The server can keep a flag in the chunk if the chunk has terrain alterations and a small diff to save cpu time when generating the upload.

As noted, this might take even longer than downloading for big maps. Generating chunks is expensive.

Time, cpu, bandwidth. Pick one.

At the start of the game generating the few explored chunks is fast. Only late stage the number of chunks becomes such a burden to generate. So some types of games, anything you play with a fixed set of players doesn't care about this.

The other thing is that generating the raw terrain can be done before downloading the map. The client would connect, get send a list of chunks to generate, generate them and only then the game freezes and saves the map for upload. The new player would have that long delay for generating the map but everyone else could keep playing while he is doing that.

The game could also go into map mode and show chunks as they are generated (only those visible on the real map). The server would send 2 lists: the visible chunks and the invisible chunks. Then the client can generate them so both lists finish at the same time.

2) a player joins having an old map
In each chunk store the tick the chunk was last modified. The client sends the tick of it's old map and the server uploads all chunks with more recent changes.

Ticks won't work. What if the server loaded a backup? You'll always desync the client, without them knowing what's wrong. That's why I proposed checksums in the OP.

If the clients tick is greater than the servers you would have also do the reverse. Have the client request all chunks that have a newer tick count after getting all the servers data. Checksums would work too but cost CPU to generate. You would have to go through all the maps data instead of just looking at one int per chunk. And then you have to transmit each checksum while the tick is just one int to transmit.

Or have the client go back to an older auto-save.


PS: Would decorations be synced between server and client? Does it make one bit of difference where on the map there are decorations? Are they part of the CRC?

[DarkShadow44]

As noted, this might take even longer than downloading for big maps. Generating chunks is expensive.

Time, cpu, bandwidth. Pick one.

Time and CPU are essentially the same. Technically I only care about time, since I only want to save bandwidth for faster transmission
If generating chunks is slower than downloading everything, it's IMHO pointless. I'm ignoring limited data connections here.

The other thing is that generating the raw terrain can be done before downloading the map. The client would connect, get send a list of chunks to generate, generate them and only then the game freezes and saves the map for upload. The new player would have that long delay for generating the map but everyone else could keep playing while he is doing that.

While that is very true, I personally only care about how quick a player can get into game. I only play with friends, so I'll wait anyways.

If the clients tick is greater than the servers you would have also do the reverse. Have the client request all chunks that have a newer tick count after getting all the servers data. Checksums would work too but cost CPU to generate. You would have to go through all the maps data instead of just looking at one int per chunk. And then you have to transmit each checksum while the tick is just one int to transmit.

Consider the following:

• Client saves map at tick 2M
• Server rolls back to tick 1M
• Server continues to run until tick 3M
• Client now connects to server

How do you propose we take care of that?

Checksums would work too but cost CPU to generate. You would have to go through all the maps data instead of just looking at one int per chunk. And then you have to transmit each checksum while the tick is just one int to transmit.

Considering the options from xxHash, the CPU cost shouldn't be too much. We have to read all data though, no way around that when using checksums.
Then again, we don't have to constantly set flags when chunks are modified. That's probably not an issue though

PS: Would decorations be synced between server and client? Does it make one bit of difference where on the map there are decorations? Are they part of the CRC?

Yes, decorations should to be synced. We'd want the map 100% the same on server and client. You never know what mods might do.

[mrvn]

If the clients tick is greater than the servers you would have also do the reverse. Have the client request all chunks that have a newer tick count after getting all the servers data. Checksums would work too but cost CPU to generate. You would have to go through all the maps data instead of just looking at one int per chunk. And then you have to transmit each checksum while the tick is just one int to transmit.

Consider the following:

• Client saves map at tick 2M
• Server rolls back to tick 1M
• Server continues to run until tick 3M
• Client now connects to server

How do you propose we take care of that?

That is a situation I didn't consider. It would blow up indeed.

The game always has a CRC for the whole state so the client can compute the CRC and detect this problem and fall back to checksum chunks or download a full map or something. I would consider this a rare event and not one we should optimize for at the cost of the rest.

One thing you could do is version the game in the style RCS/CVS used. Every time you save the game you increment the version so you have 1, 2, 3, ... When you roll back the game to save 2 you fork the game and the version becomes 2.1, 2.2, 2.3, 2.4, ... So the server keeps track of the roll backs. So when the client connects and says it has map 3 while the server is at 2.4 they know that they have diverged. If you roll back a lot the version could be 11.3.5.56.1.43.1.6.78.2.7.32.7.8.2.6.89.1. But compared to the map size that string is probably inconsequential.

PS: Would decorations be synced between server and client? Does it make one bit of difference where on the map there are decorations? Are they part of the CRC?

Yes, decorations should to be synced. We'd want the map 100% the same on server and client. You never know what mods might do.

Damn those mods with all their freedom to create chaos.

[DarkShadow44]

The game always has a CRC for the whole state so the client can compute the CRC and detect this problem and fall back to checksum chunks or download a full map or something. I would consider this a rare event and not one we should optimize for at the cost of the rest.

Well, how high is the cost of a checksum really? Since we need to touch the data anyways for serialization, I doubt having a quick checksum makes a huge difference. A checkums would help keep the logic contained to the download logic, compared to having to insert that "changed tick" writing at every possible place where a chunk gets modified. If you miss one place, you get hard to reproduce errors... I don't know, checksums just sound easier to implement and maintain to me.

[mrvn]

The game always has a CRC for the whole state so the client can compute the CRC and detect this problem and fall back to checksum chunks or download a full map or something. I would consider this a rare event and not one we should optimize for at the cost of the rest.

Well, how high is the cost of a checksum really? Since we need to touch the data anyways for serialization, I doubt having a quick checksum makes a huge difference. A checkums would help keep the logic contained to the download logic, compared to having to insert that "changed tick" writing at every possible place where a chunk gets modified. If you miss one place, you get hard to reproduce errors... I don't know, checksums just sound easier to implement and maintain to me.

It's churning through some GB of data and then transmitting num_chunks * 16 bytes or so. You would need a decent checksum because any collision would be fatal. I don't think a CRC32 would cut it. And the point of using a changed bit would be to not need to touch the data for serialization.

Note: not-modified chunks wouldn't have to be in save games either. If you explored a lot then that would reduce the save game size a lot. Just needs to save which chunks were explored and then they can be regenerated when you visit them again.

[DarkShadow44]

It's churning through some GB of data and then transmitting num_chunks * 16 bytes or so. You would need a decent checksum because any collision would be fatal. I don't think a CRC32 would cut it.

128bit sounds good enough. Sure, it might be a few MB transferred for huge maps, but then you can be certain that the chunk is actually the same on both sides. Using that, you don't have to care about rollbacks or clientside changes to the checkpoint-save. It feels safer, you know?

And the point of using a changed bit would be to not need to touch the data for serialization.

As I said, I'm not convinced it's that bad for performance - it should be in the cache by that point. After all, you need to touch the data for chunks you send anyways. The initial save of the map (saving everything, including compression) is extremely quick. Going by that, it's fast enough.
(That's why I said I'd like to play around with it myself, make some real measurements here )
You need to touch the data for chunks you send anyways. By that time it should be in cache, so making an additional checksum shouldn't hurt too much.
As I said, allows us to keep the implementation strictly confined to the map download code, which is architecturally looking a lot better.

Note: not-modified chunks wouldn't have to be in save games either. If you explored a lot then that would reduce the save game size a lot. Just needs to save which chunks were explored and then they can be regenerated when you visit them again.

That's back to the idea ssilk mentioned. Lets keep those two ideas separated please.

[ssilk]

Na, single player also has this problem. I had saves where loading needed 2-3 minutes, saving 5. Mainly because of the large areas I discovered.

May I ask how big that save was? For me, I can load even 200MB maps in a few seconds. Loading from a SSD?

@ssilk Still wondering, would you mind telling me?

Very big.
More than 300 mb. And now when I think about it, it was just so slow when I updated the mods or a new version did came out - so that the game needs to filter every single tile. In normal case load took about 20 seconds, save perhaps 60. When updating it could take 2-10 minutes. And because I thought save cannot be faster than load I added this 2/3 ratio to the save. I should be more careful with those numbers. But what I want to say is, that multiplayer is not the only problem when we talk about load/save.

About CRC: the crc is computed in background and not always up-to-date.

About speculation what the best method is: useless discussion.
I repeat: it is much too complex to say method x is the best. To be sure we need to program a simulator which uses the internal routines, simulation of network bandwidth/errors, simulation of some hardware and need to think about how to divide the behavior of the simulation from the results. Fun for more than a year in a team of minimum 4 full-time developers.