[Engine] A possible optimisation for desync recovery

[spazza360]

After playing 100+ hours with friends in multiplayer over the internet, I've experienced far too many desyncs, all of which take several minutes on larger maps due to a slow connection.
I believe there is room for a optimisation to the basic desync routine, involving some simple processing of the map prior to redistributing the map to the desynchronised player.

For those that don't quite understand how the game figures out when something goes wrong, it goes a little something like this:
-Every few ticks, the game checks if the map is the same on each players computer; This is called a CRC check.
-If the map (CRC) somehow doesn't match up, the game will pause and redownload the entire map again. This can take a rather long time when playing on slow internet connections.
-The game will unpause, and attempt to keep playing like normal, but sometimes the game will desync again due to the exact same error as last time, causing a desync loop.

In order to fix this long series of waiting for the redownload to finish, I have come up with the following idea:
When a desync does occur, it should be possible to do a quick CRC check for each 'chunk' and redistribute only the desynchronised chunks to the other players, and then rebuild the correct chunks into the existing map. Not only would this save transfer time, up to several minutes; but also bandwidth for having to send large (20MB+) maps over the internet, at the expense of some very short CPU processing time.

My basic programming knowledge indicates that this should not be too difficult to implement, but I don't know anything about the engine's existing implementation, so this may be incorrect.

[MF-]

Search first!
I have already linked some relevant threads to someone else here: https://forums.factorio.com/forum/vie ... 393#p51393

[ssilk]

Well, this is the basic underlaying idea, but of course Merkle trees are better.

[spazza360]

Search first!

Well I did, I looked through several suggestion pages and didn't notice anything that seemed similar, so I thought it was a new idea.
That's my mistake, I'll check more thoroughly next time.

[bobingabout]

Several minutes on a large map?

I've been playing with a friend on a small map, fortunately we havn't played long enough to start getting desyncs yet, but, it's basically "Okay, I'm connecting now, go make a cup of tea, take your time", because it takes about 15 mins to transfer.



But I agree, in fact I've sugested similar things before, try sending only the parts that need fixing, not everything, I think something that one of the Devs said to me was that the reason why they re-send everything, is because of what is known as the butterfly effect, one tiny little change can ripple, and ripple, and ripple, and change the entire world before you know it.

An example: Peice of coal doesn't make it into a boiler at the same time. Power levels then differ for each player, this causes factories to run a little slower for one player, causing all produced goods to be out of sync. If that power grid covers an entire base, the entire base is then out of sync.

[Tinyboss]

But I agree, in fact I've sugested similar things before, try sending only the parts that need fixing, not everything, I think something that one of the Devs said to me was that the reason why they re-send everything, is because of what is known as the butterfly effect, one tiny little change can ripple, and ripple, and ripple, and change the entire world before you know it.

An example: Peice of coal doesn't make it into a boiler at the same time. Power levels then differ for each player, this causes factories to run a little slower for one player, causing all produced goods to be out of sync. If that power grid covers an entire base, the entire base is then out of sync.

Maybe instead of breaking it up by geographic chunks, then, the save file should be broken up into pieces that don't have this kind of dense interdependence. For instance, the placement of buildings is not likely to change in response to a power fluctuation. The terrain even less so. Mainly it would be power states, inventories, inserters, and items on the ground/belts that would experience this butterly effect, I would guess.

(1) CRC check for the terrain. This would never fail in the absence of terrain-altering mods.
(2) CRC for stationary built items like belts, inserters, buildings. Only their location and settings (e.g. filters, recipes, modules present). This one would rarely fail since changing these things is not automated.
(3) CRC for everything else. When this fails, you just send this "chunk".

I don't know how much of the save file consists of 1 and 2, versus 3. But it could save some bandwidth, I think.

Of course, if the devs feel like a totally deterministic simulation is a reachable goal, then it's probably best to focus on squashing non-determinism bugs rather than working harder to tolerate them. They're the only ones who will know how to strike that balance.