Technical solution to eliminate desync in single-player sessions

Wow, I must say all the developer posts in this thread are excellent.

Thank you Mark_GGG and Rhys for all those really clear explanations of the behind the scenes technicalities. Props to you for taking the time and offering so much insight!

"

It's a hash. There is no room for leniency. This simply doesn't work. And if it did, it would allow cheating.

You would still hash it with the seed, but the server can provide leniency for the resulting value. In other words, the seed may be 0.7, the 'randomly generated' value may be 2.55558 which the client rounds up. The server will see the 2.5556 and provide leniency to the client. In other words, the server would accept the hash, thereby replacing its own.

"

Also, the server cannot resync the client by sending a state hash. Doing this would make the client "rewind" back to that valid state, yes.

Exactly, once the server sends a state change, the client indeed rewinds back to the clean state.

"

But the simulation is still deterministic, so the client will just desync itself again at the same point in the same way. So you have to have the server run forward without the client to get it past the desync point.

The client will only desync itself if it is using a hacked state hash. Why would it happen again at the same point? These things should only happen in the event of hacks or extreme latency. So yes, if the client maintains hacks/latency, the server will need to continually desync or disconnect him.

"

The client isn't streaming the results of every calculation. The server can't validate every calculation. It's just checking periodic state hashes. There could be 100,000 RNG spins in between each one. The server has no idea which ones are accurate. The only thing it can know is that an error occurred somewhere.

We have a misunderstanding somewhere then. You have been calling it a 'state hash', I have been calling it a 'snapshot'. I called it a snapshot because it is literally a list of actions (similar to how you have now I imagine). The server can read the full snapshot, it's not a serialized hash. The snapshot contains all of the actions/input since the last snapshot so that the server can run the same simulation and completely validate it.

Example in JSON format:

[
"action": {
type: "attack",
target: "23497",
damage: 15,
timestamp: "2748827722"
}
]

You can validate this by using the timestamp, seed, and target to calculate the random number and ensuring that it's within the lenient range of the damage value. In other words, the lenience occurs on the damage calculation, after the random numbers have been generated.

Once it is validated, the server can persist the new state. It will use this state to validate future states.

"

Because of floating-point errors in a deterministic system.

As long as the server runs the simulation while providing leniency on each calculated value, there won't be any errors. =)

The issue of FP calculations in deterministic online games/simulations is a *well known* issue, see e.g.

http://gafferongames.com/networking-for-game-programmers/floating-point-determinism/

As many developers, I would suggest to use fixed point math to do that calculations. [http://en.wikipedia.org/wiki/Fixed-point_arithmetic]

Asyncronous loot would cause desync: this is true if not handle properly. The solution is that the client send back to the server a commandlike "i get loot #xyz at timestamp #abc". Similar for crafting, and for vendor recipes.

Turn based requirements. As long as the timestamp of commands is discrete, the game is actually turn based.

I would suggest also to insert an ordinal number next to the timestamp, which is increased++ for each client commands.

There is no need of 'cryptographic hash seed' for rng rolls (i actually still do not understand its meanings). Just take a new random number from the rng whenever you need to roll a dice. If needed, you can scramble more the rng by making it interacting with the gameplay (i think this is the OP suggestion). Keep the rng as simple as possible, for saving server cpu.

I think you're really close to an 'AH-HA!' moment here. Believe me, this stuff blew me away when I first learned about it, and it changed everything I thought I knew about multiplayer game programming.

"

Besides, what does leniency even mean? A difference of 0.00001 in part of a calculation can easily result in a difference of 1000 just slightly further along. The client can't stream the result of every calculation.

The client doesn't need to send every calculation, but he does need to send the value of the outcomes that the server needs to provide error checking for. The server can implicitly fill in the blanks using the explicitly provided values. Here's an example:


** My character hits a creature three times. **


So how many calculations are involved with this? Lets say 100 calculations were necessary. You don't need to send these calculations, because the server can -deduce- them from the 'end result'. In other words, the outcome is three hits. The server will simulate three hits, which means it will be re-rolling the seed for each random number involved. The server should arrive at the same values, despite the fact that many re-seeds are needed.

In other words, the client provides enough data that allows the server to rebuild and validate the state implicitly.

Other things may be happening too, such as mob pathing. But the server can already deduce this! The client doesn't need to send this sort of data because the server already knows where they are going to be. =)

The same goes for mob pathing. The client will send the locations/attacks of the mobs, and the server will be able to reproduce their position/AI. However, even if the client did not send the mob locations, the server can deduce their positions based on the timestamp. In other words, the client does not need to send the mob locations as frequently as other things (or at all, because the server can gather that data implicitly if it had to).

It's like a crossword puzzle. If the client sends enough state, the server can easily fill in blanks to evaluate whether the state is authorized.

You would be amazed at how much you can actually optimize this. Suddenly you start to discover that all your calculations can be done by the client and server with very little exchange. The implicit values fill themself in automatically.

Instead of the server responding with values, the server does not need to send anything back. You save a lot of bandwidth on the fact that the server doesn't need to tell the client what happened.

This gets even more exciting with the fact that the client does not need to send data as frequently as currently do. This allows you to employ greater compression opportunities. In other words, the client may be sending more data, but the compression advantage becomes significant over time.

"

qwave wrote:

In a video game, mob movement based on a deterministic seed is deterministic. That's all that matters for this particular proposal.

Hooray for your proposal meaning that mobs never react to what you do.

Deterministic = following a pattern. Move out of the pattern/discover and exploit the pattern = congratulations, you now won the game, because it can't adapt to you!

I want to know where qwave works so I can apply for his job.