Technical solution to eliminate desync in single-player sessions

"

Rhys wrote:

Spoiler

As the programmer responsible for maintaining the client/server synchronization of the random level generation, I can tell you that this sounds like a nightmare, for a few reasons.

1) The server must validate the snapshots in real-time, not once the client leaves the instance. This is because the client can potentially muck around in one instance for huge lengths of time. Hours, days, weeks even, if the realm stays up. Processing so much all at once would lag the instance to hell and back, and changing areas has to wait on this task. Also, you will still need the ability to resync players to a recent state, when desync inevitably occurs (see next point). Also also, you need to be able to save the player's data at a moment's notice to prevent item dupes with trading.

2) Floating-point calculations will still cause desync. Suppose the client needs to perform a mathematical calculation, such as 37 / 13. The client determines the result to be 2.84615384. But when the server performs the same calculation, with the same values, the exact same bit-patterns inputs, it might instead return 2.84615385. The numbers are slightly different. Why would it do this? There are several reasons: Windows client vs. Linux servers. Different CPU architectures. Different optimizations compiling the servers vs. client. Different system drivers. Whatever the cause, you now have a divergence point, where the simulation may or may not diverge, depending on how those values are used and rounded. In that example, rounding to an integer afterwards isn't a problem, but what if the two values were 7.499999 and 7.500001? One will round to 7 and the other will round to 8. Suddenly the tiny difference isn't so tiny, and so even legit players can end up desynced.

3) The client would effectively have the ability to see into the future. A hacked client could predict when hits, crits, evades, and dodges will occur, so a player could alternately attack minions/bosses, or even just pause a certain number of milliseconds, to ensure they are almost never hit by strong attacks and almost always crit against the boss. In both of these cases, the final simulation is perfectly legitimate, so the server cannot know the client is cheating, unless you want some statistical system that punishes players for being "too lucky", which will harm legit players who get an actual lucky streak.

If item creation and currency use is done from the server, then you have monsters only dropping items 2-3 seconds after they die, and waiting 2-3 seconds for every currency item to take effect, since you have to wait for the next snapshot to be verified (and on a turbulent connection, that could be a while). Using (say) 1000 Fusings to try for a 6-link would take forever (you couldn't spam shift+right-click).

4) How do you detect death? You can't rely on the client sending the "Oops I died" packet. Otherwise hacked clients would never die. The server must be able to continue the simulation without the client, and determine when a player dies. This means that the server must keep simulating "the future", and client commands occur in "the past", which then changes the simulated future (like what Valve's Source Engine does). Now, you suddenly need the ability to effectively "rewind time" as far as the simulation is concerned. This is not a trivial task, at all.

5) This entire system breaks down completely as soon as you have more than one player. Anytime one player moves or hurts a monster, everyone else is automatically desynced and must be jolted back to the last verified snapshot. This is because you cannot recover from small amounts of desync, since even tiny differences completely change the RNG and state hash.

The "rewinding time" mechanic would somewhat solve this, but you would STILL get desync (just like in Team Fortress 2 and other Source Engine games). The classic example is being headshotted through a wall, because even though you successfully took cover on your screen, you didn't on the sniper's.

Also, what happens when the level geometry is different for different players? For example, if one player has destroyed the Undying Blockage in the Sewers, then the corridor is clear for them, but another player who hasn't done that will have the corridor blocked. The simulations for projectiles and movement will be VERY different on each client, so which one does the server think is correct?

6) Maphack would be even easier, and better, because it could show all the monsters and chests and items on the map, too.

Just my 2c.

"

qwave wrote:

"

Now, you suddenly need the ability to effectively "rewind time" as far as the simulation is concerned.

This has been brought up several times. I indicated that the game would need a delay on town portal / logout of 2-3 seconds. As long as the snapshots are very frequent (a second or less), then you could not reliably prevent death.

"

And this seed that is sent to the client is in no danger of being figured out? This seed needs to go into the PRNG unencrypted to get the process started, no?

"

At first you said snapshots are sent in 1 second intervals, meaning the client could only store snapshots in 1 second intervals, else the random number generators will get out of sync.

"

If mob movement is based on a seed value, then the player can have no affect on the mob.

"

...but a seed cannot determine where the player will go

"

If I can manipulate the snapshot being sent or the client itself, the server has no choice but to trust me.

"

How and when are interactions between mobs and players calculated. Who does the calculation?

"

You claimed seed values could represent entire game states, I'm 100% positive that they cannot, because calculations for player/mob interactions will have to be made at some point.

"

Eep wrote:

I love reading shit like this as a CS student. Dat programming PoV

"

So if I have the seed, even if the client is sending snapshots every second, I could calculate the best move every second by calculating the outcome for every variation before I send the snapshot.

"

Rhys wrote:

Amazing post

As the programmer responsible for maintaining the client/server synchronization of the random level generation, I can tell you that this sounds like a nightmare, for a few reasons.

1) The server must validate the snapshots in real-time, not once the client leaves the instance. This is because the client can potentially muck around in one instance for huge lengths of time. Hours, days, weeks even, if the realm stays up. Processing so much all at once would lag the instance to hell and back, and changing areas has to wait on this task. Also, you will still need the ability to resync players to a recent state, when desync inevitably occurs (see next point). Also also, you need to be able to save the player's data at a moment's notice to prevent item dupes with trading.

2) Floating-point calculations will still cause desync. Suppose the client needs to perform a mathematical calculation, such as 37 / 13. The client determines the result to be 2.84615384. But when the server performs the same calculation, with the same values, the exact same bit-patterns inputs, it might instead return 2.84615385. The numbers are slightly different. Why would it do this? There are several reasons: Windows client vs. Linux servers. Different CPU architectures. Different optimizations compiling the servers vs. client. Different system drivers. Whatever the cause, you now have a divergence point, where the simulation may or may not diverge, depending on how those values are used and rounded. In that example, rounding to an integer afterwards isn't a problem, but what if the two values were 7.499999 and 7.500001? One will round to 7 and the other will round to 8. Suddenly the tiny difference isn't so tiny, and so even legit players can end up desynced.

3) The client would effectively have the ability to see into the future. A hacked client could predict when hits, crits, evades, and dodges will occur, so a player could alternately attack minions/bosses, or even just pause a certain number of milliseconds, to ensure they are almost never hit by strong attacks and almost always crit against the boss. In both of these cases, the final simulation is perfectly legitimate, so the server cannot know the client is cheating, unless you want some statistical system that punishes players for being "too lucky", which will harm legit players who get an actual lucky streak.

If item creation and currency use is done from the server, then you have monsters only dropping items 2-3 seconds after they die, and waiting 2-3 seconds for every currency item to take effect, since you have to wait for the next snapshot to be verified (and on a turbulent connection, that could be a while). Using (say) 1000 Fusings to try for a 6-link would take forever (you couldn't spam shift+right-click).

4) How do you detect death? You can't rely on the client sending the "Oops I died" packet. Otherwise hacked clients would never die. The server must be able to continue the simulation without the client, and determine when a player dies. This means that the server must keep simulating "the future", and client commands occur in "the past", which then changes the simulated future (like what Valve's Source Engine does). Now, you suddenly need the ability to effectively "rewind time" as far as the simulation is concerned. This is not a trivial task, at all.

5) This entire system breaks down completely as soon as you have more than one player. Anytime one player moves or hurts a monster, everyone else is automatically desynced and must be jolted back to the last verified snapshot. This is because you cannot recover from small amounts of desync, since even tiny differences completely change the RNG and state hash.

The "rewinding time" mechanic would somewhat solve this, but you would STILL get desync (just like in Team Fortress 2 and other Source Engine games). The classic example is being headshotted through a wall, because even though you successfully took cover on your screen, you didn't on the sniper's.

Also, what happens when the level geometry is different for different players? For example, if one player has destroyed the Undying Blockage in the Sewers, then the corridor is clear for them, but another player who hasn't done that will have the corridor blocked. The simulations for projectiles and movement will be VERY different on each client, so which one does the server think is correct?

6) Maphack would be even easier, and better, because it could show all the monsters and chests and items on the map, too.

Just my 2c.

"

MeltingPoint wrote:

"

Eep wrote:

I love reading shit like this as a CS student. Dat programming PoV

I've always enjoyed the challenges of programming, but I'm too old to really make it anything other than a hobby. Still love talkin about it though.

"

qwave wrote:

Rhys definitely has one of the hardest jobs in game development. He has to consider countless factors that may impact gameplay. That being said, I think the GGG development team needs to spent more resources on this effort. I think some huge gains can be made.