Deterministic simulation using floats?
Author
Is this feasible/possible? I read in the gamesutra article "1500 archers" (googlable) that the way Age of Empires did multiplayer is to have every player simulate the game separately & just transmit player orders/commands to the other clients. No synchronization at all so far as I can tell.
This relies 100% on a completely deterministic simulation, with very strict regulation of calls to random number generator etc.
But I have also read that floating point numbers are represented differently on different architectures, with hidden precision bits & stuff. Is it possible to get a completely deterministic sim with floats? Or is there some other way to do this?
Thanks for your advice.
If you need to support multiple architectures then you're pretty much screwed. You might try a software floating point implementation, and some systems have nice language support for this kind of thing (e.g. Java's strictfp modifier) but the performance will still be atrocious on many platforms.
Tecnically a computer is a deterministic state machine.
Isn't there an IEEE standard for float?
Besides that, the internal representation of the value should not affect the way it behaves from external viewpoint.
Like two different objects performing a same task. Both have same accessories but both are completely differently implemented.
I would put my uneducated guess on yes.
Edit: Java of course would offer emulated solution. Are we by the way talking about real implementations, or is this just a theoretical discussion?
Isn't there an IEEE standard for float?
Besides that, the internal representation of the value should not affect the way it behaves from external viewpoint.
Like two different objects performing a same task. Both have same accessories but both are completely differently implemented.
I would put my uneducated guess on yes.
Edit: Java of course would offer emulated solution. Are we by the way talking about real implementations, or is this just a theoretical discussion?
Actually, most platforms are compliant with IEEE 754, which is the standard for floating point representations. So regardless of what you're running on, if it does IEEE 754, you know the layout of your floats and the available precision, what rules are being followed to do the math, etc.
Despite all that, you may get inconsistent results due to mismatched rounding modes, slight implementation differences, etc.
If you're on weird embedded devices, they may not have IEEE float support, which will be a problem.
In general, though, what you need to do is add a mechanism to detect inconsistencies and resynchronizes with the server or other players. If you're doing an RTS then minor floating point imprecisions aren't going to be a big deal, since most game logic is pretty granular. If you design your game logic to avoid finicky floating point calculations then you should be able to get 100% consistent results. Contrariwise, if you do weird things like update arrow positions per-frame in tiny increments, then you'll get tons of indeterminate results.
You don't need to write your own math routines to solve this problem. Just write smart, robust code and don't push the limits of the system's floating point implementation.
Despite all that, you may get inconsistent results due to mismatched rounding modes, slight implementation differences, etc.
If you're on weird embedded devices, they may not have IEEE float support, which will be a problem.
In general, though, what you need to do is add a mechanism to detect inconsistencies and resynchronizes with the server or other players. If you're doing an RTS then minor floating point imprecisions aren't going to be a big deal, since most game logic is pretty granular. If you design your game logic to avoid finicky floating point calculations then you should be able to get 100% consistent results. Contrariwise, if you do weird things like update arrow positions per-frame in tiny increments, then you'll get tons of indeterminate results.
You don't need to write your own math routines to solve this problem. Just write smart, robust code and don't push the limits of the system's floating point implementation.
Unfortunatly Stoo, that just isn't the case. The internal precision of the float determines the outcome of the answer that gets
rounded into your 32bit value. This means that error accumulates into your floatingpoint calculations faster on some machines than others.
Differing operations (add, multiply etc) will all cause rounding errors to show up at different rates on different machines.
All in all this leads to your simulation quickly diverging between different computers.
Mostly this means you need to switch to fixpoint math for any calculation that the simulation relies on.
(there was a thread just recently though that mentioned some assembly op you could put in to force the floatingpoint unit into
some compatability mode, but I never looked into what that really does)
rounded into your 32bit value. This means that error accumulates into your floatingpoint calculations faster on some machines than others.
Differing operations (add, multiply etc) will all cause rounding errors to show up at different rates on different machines.
All in all this leads to your simulation quickly diverging between different computers.
Mostly this means you need to switch to fixpoint math for any calculation that the simulation relies on.
(there was a thread just recently though that mentioned some assembly op you could put in to force the floatingpoint unit into
some compatability mode, but I never looked into what that really does)
There is synchronization:
Each order is delayed by some amount. If the order doesn't get to every client in that delay period, maintaining the simulation properly is very difficult, and often you get things like "out of sync". Similar things happen if people cheat in certain ways.
Note that this approach has other advantages: replays are a matter of recording user input.
This also lets you record a game session that (say) causes an infinite loop in your game logic, which makes many things far easier to track down during development!
Each order is delayed by some amount. If the order doesn't get to every client in that delay period, maintaining the simulation properly is very difficult, and often you get things like "out of sync". Similar things happen if people cheat in certain ways.
Note that this approach has other advantages: replays are a matter of recording user input.
This also lets you record a game session that (say) causes an infinite loop in your game logic, which makes many things far easier to track down during development!
Author
I was afraid of that... I might just see if I can rely on fixed point arithmetic using integers. I don't want to rely on resynchronization because first of all it would be a lot of data & have already worked into my design a way to do a deterministic sim, & I want to be able to rely on checksums in the deterministic sims to detect hacking/cheating.
I found a library called STREFLOP which claims to standardize the rounding/representation of floating point formats in c++, but at first pass it seems overly complicated for what I'm after (seems more aimed at scientific experiments which need pinpoint reproducible accuracy) & I might just rather use fixed point... I don't need accuracy just reproducibility :)
Thanks for the commentary guys.
I found a library called STREFLOP which claims to standardize the rounding/representation of floating point formats in c++, but at first pass it seems overly complicated for what I'm after (seems more aimed at scientific experiments which need pinpoint reproducible accuracy) & I might just rather use fixed point... I don't need accuracy just reproducibility :)
Thanks for the commentary guys.
I'd put my money on IEEE 754. Most platforms follow this standard, so you'll have optimal speed on them. You can worry about emulation when you actually need to port your game to obscure platform XY, but I doubt that need will ever arise.
Still, I've always wondered how exactly these games manage to keep the states in sync.
Of course, you need to use fixed time frames (eg. always advance the game state in 1/100th of a second steps) so that the rounding errors are the same for all players. Otherwise, due to different frame deltas between fast and slow PCs, the game states would inevitably drift apart.
But how do you ensure a command is executed in the same time frame on all connected players? Does the peer issuing a command ask everyone "I'd like to send this tank there in time frame 142345" (where 142345 is calculated as now + network latency * 2 or something) and then everyone queues up the command for execution at exactly that time frame?
Still, I've always wondered how exactly these games manage to keep the states in sync.
Of course, you need to use fixed time frames (eg. always advance the game state in 1/100th of a second steps) so that the rounding errors are the same for all players. Otherwise, due to different frame deltas between fast and slow PCs, the game states would inevitably drift apart.
But how do you ensure a command is executed in the same time frame on all connected players? Does the peer issuing a command ask everyone "I'd like to send this tank there in time frame 142345" (where 142345 is calculated as now + network latency * 2 or something) and then everyone queues up the command for execution at exactly that time frame?
Even if two PCs are running on the exact same hardware, and are executing the exact same simulation, you can still get different floating point results from them.
Floats can be represented differently in CPU registers than in RAM, which means that errors may be introduced when moving between these two types of memory.
Initially, you wouldn't think that this is a problem, as both computers are going to be moving between CPU and RAM at the same times right?
However, factors outside of your control may affect when data is copied from CPU and RAM. For example, a virus-scanner might be running on the computer, causing it to perform CPU context-switches more often, increasing the chances of CPU registers having to be copied to RAM, increasing the chances that you might lose a few bits of accuracy in one of your variables....
For example, the value of z in this following snippet depends on how much work happens at the ... section! If neither x or y have been swapped out of the CPU yet, z will likely be true, but if only one was swapped out to RAM and back then z will likely be false.
Despite all of this, I've heard that RTS games have shipped before using floats for unit positions with absolutely no code written to take care of floating-point errors, or to correct "lost synch" errors. Apparently in some games the errors are too small to actually impact the simulation. YMMV.
Floats can be represented differently in CPU registers than in RAM, which means that errors may be introduced when moving between these two types of memory.
Initially, you wouldn't think that this is a problem, as both computers are going to be moving between CPU and RAM at the same times right?
However, factors outside of your control may affect when data is copied from CPU and RAM. For example, a virus-scanner might be running on the computer, causing it to perform CPU context-switches more often, increasing the chances of CPU registers having to be copied to RAM, increasing the chances that you might lose a few bits of accuracy in one of your variables....
For example, the value of z in this following snippet depends on how much work happens at the ... section! If neither x or y have been swapped out of the CPU yet, z will likely be true, but if only one was swapped out to RAM and back then z will likely be false.
float x = 100.0f / 9.0f;float y = x;...bool z = (y==x);Despite all of this, I've heard that RTS games have shipped before using floats for unit positions with absolutely no code written to take care of floating-point errors, or to correct "lost synch" errors. Apparently in some games the errors are too small to actually impact the simulation. YMMV.
Quote:Original post by Hodgman
Even if two PCs are running on the exact same hardware, and are executing the exact same simulation, you can still get different floating point results from them.
Floats can be represented differently in CPU registers than in RAM, which means that errors may be introduced when moving between these two types of memory.
That sounds highly unlikely, and I can't replicate your scenario. Got a source? It doesn't matter how many times you copy a floating point number; as long as no operations are made to actually change the value of the number, it is not going to change. Every floating point number has one and exactly one representation in computer memory - one and only one sequence of bits. That exact sequence can be copied back and forth as much as you want but as long as no extraordinary error occurs, it is going to stay unchanged.
The problem with floating point precision is not that values magically change when you copy them, it's that not all numbers are possible to represent with floating point data. Sometimes (often, in fact) the number you want will fall somewhere between two numbers that are possible to represent, and rounding will occur. That's the problem, and that doesn't get affected in the least by how often you copy the data.
It also shouldn't be a problem as long as the platforms conform to the same standard as mentioned. In practice, however, there are often control variables introduced for speed, flexibility or whatever that can make the environment violate the standard. Such variables are usually documented, but you have to know what to look for to disable them. Once any such special circumstances have been eliminated, each connected system will give identical result to every floating point operation.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
