Archived

This topic is now archived and is closed to further replies.

Memir

How do you keep a game in sync? (multiplayer)

Recommended Posts

I''ve got a problem that has been plaguing my Online Snooker (Pool) game ever since I''ve begun six months ago... When people play online and take shots, sometimes one of the players/watchers in the table experiences a different outcome. We''ve been thru the code and combed out all the bugs that could cause an incorrect simulation. Eventually, we found out that when you do simple floating point calculations e.g. y = a+b; Certain computers calculate the result ever-so slightly differently. e.g. 5*5 = 25.000000 on one person''s processor, and on another''s 5*5 = 25.0000001. Now that small difference becomes bigger and bigger, eventually resulting in one player seeing the balls in different positions. Our current solution is to update all the balls'' positions at the end of each shot. That solves the problem of players going out of sync and staying out of sync. However, it also causes people to say "Hey this game has bugs, cause the balls are moving after the shot has been completed". What I want to know is is there a way to use floating point math without causing this problem? Is there any ''Emulation'' mode floating point that I can use which gaurantees that all players across the world, regardless of CPU/FPU/Hardware/OS will carry out floating point calcs the EXACT same way. The only other solution I can think of is changing the ***WHOLE*** thing over to fixed point, and thats gonna be a mission. Especially figuring out how to convert the 4x4 Matrix calcuations, 3D ball/table detections etc. over to Fixed point. There''s gotta be an easy way out? Anyway, if you''re curious to see what my Snooker game looks like click the following url & download, you can play as a guest for free: TheSnookerClub /Memir

Share this post


Link to post
Share on other sites
hm...thats weird. how can 5*5 = 25.000000000001? anyways, the best answer i can give you (i have virtually no idea of networking) is to keep original values so as to keep the effects of erroneous values from adding up... sorry for lame answer but its the best i can give you...


Check out our website!
Clicky!

I am Ciph, and that is what I am

Share this post


Link to post
Share on other sites
What about having one computer designated as server and one as client.. and one does the calculations and sends the results to the other.. or perhaps they alternate?

Share this post


Link to post
Share on other sites
Problem is... this is a Snooker game, i.e. like Yahoo Pool! ...

Means there are a lot of balls that collide into eachother when someone breaks & smashes the pack. Not only does the person taking the shot see what''s going on live, but his/her opponent and all the people watching in the game see this live.
Now I''m not gonna send over the coordinates of 20-odd balls * float(X,Y,Z) * 60*say 5 seconds (20*12*300 bytes) to all the players watching me take a shot! - At present I only send over the strike vector and target ball, aswell as a 32-bit CRC value of the current table state (present ball coordinates) - i.e. to detect out of syncs.

I read an article on Gamasutra about Reproducibility, by Peter Lindcroft (dude who helped develop X-Wing vs TIE Fighter). His answer was the easy "Just use fixed point math" OR "Do a complete update every now and then".

Looks like no one knows how to "beat the float" head on.

If the game was a simple Snooker/Pool game like the rest of the online games, then I would''ve just coded it all fixed point (especially if I knew that floats+networking doesn''t mix), but this game has a lot of complex vector & matrix calculations as we tried to make it as realistic as possible.

I guess I''ll have to just go over the code line by line, function by function changing it.

/Memir

Share this post


Link to post
Share on other sites
Just do the shots like you normally do, then at the end of the turn, sync all the ball positions to that of one computer. If you do this every turn, the balls will only move minutely after the turn is done.

This will avoid having to send constant details about the motion of the balls, and it will keep the game in-sync.

Share this post


Link to post
Share on other sites
I suspect a bigger problem is timing differences between computers. Would a different frame rate result in different collision results or different integration results (because the time-step is different)? If so, then fixed-point won''t make a difference.

Share this post


Link to post
Share on other sites
glassJAw: That''s what we do already! - The thing about this problem is that it doesn''t always come out, it''s pretty rare, and most times when it does come out, it only causes the balls to move a little at the end of the shot. But sometimes, you can clearly see that the balls have move a lot. It really depends on the shot, and how the balls interact with eachother. So when someone smashes the pack, theres lots of ball collisions, meaning a small error can quickly propagate up, and become quite noticable.

JohnBolton: The timing differences doesn''t matter in this game, coz it''s like a "You take a turn, Then I''ll take a turn" game. And everyone waits until everyone has completed the simulation of the shot.

At one point a few months ago, we did find a solution to the floating point problem, and that was to simplify the operations.

e.g. instead of having y = (a+b)*c;
we would do y = a;
then y+=b;
then y*=c;

and somehow doing this made all math processsors (FPU) produce the same result.

I think it has something to do with the fact that the FPU does calculations at 80bit. and these values are stored as 32bit floats.
so when you''re doing:

1) y= (a+b)*c [32bit = FPU((a+b)*c)]
2) y= a; [32bit = CPU(a)]
y+=b; [32bit+= CPU(b)]
y*=c; [32bit*= CPU(c)]
Basically I think the compiler realises that a complex one liner, will be calculated faster by converting the 32-bit floats into 80bit FPU values, then calcuated by the FPU, then converted back into 32-bit floats.
Whereas simple operations on seperate lines, can be evaluated faster just using the CPU''s own math processor, rather than converting the 32bit values into 80bit then firing up the FPU then converting back to 32bit.

It''s a small problem in my game, not one of the high priorities, as it doesn''t happen that often, and when it does, it usually only happens to one person in the game. But nevertheless I''d like to get rid of it completely, without having to just avoid floats.

/Memir

Share this post


Link to post
Share on other sites
quote:
Original post by Memir

JohnBolton: The timing differences doesn't matter in this game, coz it's like a "You take a turn, Then I'll take a turn" game. And everyone waits until everyone has completed the simulation of the shot.



Hmmm, that sounds extremly strange I think that timing does not affect the movement... Unless you use frame dependent animation, the timing will of course affect the movments, even if you have a turned based game. That it is turned based has nothing to do with it.

However, maybe I have misunderstood something here, but the fact that one computer might calc a collision 3 times over 60 ms (1 time each 20 ms) and another 2 times over 60 ms (1 time each 30 ms) will of course affect all the calculations due to round offs. Of course, in general, a ball that moves from A to B with a certain speed and direction and acceleration/deacceleration will move from A and end up in B even if the ball moves in 2 steps or 3 steps over 60 ms... However, in your case where you have a lot of floats you will get a lot of round offs and those round off will differ if you use 1, 2, 3, 4....n steps and will in the end cause different results. So timing is for sure an issue here I think.

However, is you lock your framerate to for example 30 FPS and do calcs each frame then all should be in sync. But I assume you to calculations based on time that has passed and then you will be affected by the above facts.




[edited by - calvincoder on July 27, 2003 8:37:14 AM]

Share this post


Link to post
Share on other sites
Try using doubles instead of floats.

If push comes to shove do all the ball calculations in assembly using the highest precision registers and the least amount of conversions.

------------
- outRider -

Share this post


Link to post
Share on other sites
What I can suggest is to have one computer designated as the computational master doing all of the floating point math ahead of time and to then relay that information to the other computers.

Besides that, I can say you could try using doubles (you might end up with the same problem). However, if you check regularly to make sure the game is in sync then at most the balls would move like a single pixel. It shouldn''t be detected by the human eye.

Share this post


Link to post
Share on other sites
I''m pretty sure that some of the calculations has to do with TIMING. i.e. A ball slows down so and so much per time-unit. And time unit being actually a real gettickcount() or whatever, instead of having time as a variable that you increment yourself.
Am I wrong?

Share this post


Link to post
Share on other sites
quote:
Original post by Caminman
I'm pretty sure that some of the calculations has to do with TIMING. i.e. A ball slows down so and so much per time-unit. And time unit being actually a real gettickcount() or whatever, instead of having time as a variable that you increment yourself.
Am I wrong?


Yes, you are absolutly right Caminman, as I also explained in my previous post.

That two computers or two different FPUs on two different computers calc different I have very very hard to believe.

If all calculations are done according to how much time has past since last update, which I am pretty sure he do since he is dealing with a lot of physics here, faster computers, i.e. computers that can do the updates more often, will have more accurate calculations than computers that do not manage to updates that often. To illustrate an example, we can use 2 simple forumlas for simulating motions:

v = v0 + a * dt
p = p0 + v * dt

The last formula, which calcs the position, acts different according to how big dt is. However, they are accurate enough for their purpose in games, however, they cause sync problems in multiplayer games because they are not accurate enough.

If we start with p=0 (postition), v=0 (velocity) and a=1.56 (lets say it moves 1.56 pixels pr. 10 ms).

If we measure movment over a time period of 60 ms, the end result (i.e the end position) will be different on a computer that updates every 20 ms than a computer that updates every 30 ms:

With 20 ms update:
-----------------------------
After 20 ms velocty and position will be (dt = 20 ms):
v = 0 + 1.56 * (20 / 10) = 0 + 3.12 = 3.12
p = 0 + 3.12 * (20 / 10) = 0 + 6.24 = 6.24
^^^^^^^^ div by 10 because each time unit is 10 ms

After 40 ms velocty and position will be (dt = 20 ms):
v = 3.12 + 1.56 * (20 / 10) = 3.12 + 3.12 = 6.24
p = 6.24 + 6.24 * (20 / 10) = 6.24 + 12.48 = 18.72

After 60 ms velocty and position will be (dt = 20 ms):
v = 6.24 + 1.56 * (20 / 10) = 6.24 + 3.12 = 9.36
p = 18.72 + 9.36 * (20 / 10) = 18.72 + 18.72 = 37.44

=====================================

With 30 ms update:
-----------------------------
After 30 ms velocty and position will be:
v = 0 + 1.56 * (30 / 10) = 0 + 4.68 = 4.68
p = 0 + 4.68 * (30 / 10) = 0 + 4.69 = 14.04

After 60 ms velocty and position will be:
v = 4.68 + 1.56 * (30 / 10) = 4.68 + 4.68 = 9.36
p = 14.04 + 9.36 * (30 / 10) = 14.04 + 28.08 = 42.12

As you can see, with 3 even updates over 60 ms the end position is 37.44, while with 2 even updates over 60 ms the end positon is 42.12

If we did one update only over 60 ms, the result would be:
v = 0 + 1.56 * (60 / 10) = 0 + 9.36 = 9.36
p = 0 + 9.36 * (60 / 10) = 0 + 56.16 = 56.16

Also a different result.

The more often the updates are, the more accurate the answer is.

On top of this, if you do a lot of conversions (whicih I assume you really dont, but anyway) inbetween your updates, you will also get different results from a faster update to a slower due to round offs.

The solution to this is to sync the game to the slowest computer that are in the game. This is a very common way to sync games. This is the reason also why a slow computer can "lag" a multiplayer game as often seen in many multiplayer games played on Internet.


[edited by - calvincoder on July 27, 2003 7:44:07 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by Lord Hen

Isn''t a double a floating point value?

Lord Hen



Yes, a double is also a float, but a double has better precision and takes up 8 bytes of memory, while float only takes 4 bytes.

Share this post


Link to post
Share on other sites
I believe that you (or Peter Lindcroft) have already answered your own question. Different FPUs might calculate slightly differently, and using a bigger float will not change this. It might of course still solve the problem if the differences become insignficant, but I assume you have already tried it. Since you have already tried complete updates I would suggest using fixed point calculations.

Share this post


Link to post
Share on other sites
I''d just use one machine as a server (i.e. the machine that plays the shot), and send the packets to every other players. You don''t need to update at 60 fps, and you don''t need to update all the balls either, only the ones that move. Of course, at first, all will move. And also, you can pack all coordinates into 32 bits or whatever (you only need x,z coords really, unless the ball jumps, in this case, you can send a special packet). When you send updates at 20 fps, you''ll need to linearly interpolate from the previous positions, to make the movement smooth at 60 fps. Or you can apply physics on the current state of the game, and interpolate between what the client calculated, and what the client receives from the server. You obviously need to time your packets with the server time, so the linear interpolation works in the case when a packet gets delayed.

so, say 16 balls, times 12 bytes, times 20 = 3.8k/s. Broadcasted to 4 players, gives about 16k/s from the server. That''s still quite a lot, with no overheads considered.

16balls * 4bytes * 20fps = 1.3k/s * 4 = 5.1k/s which is a lot more manageable. And that would be for maximum traffic. Also, 20 fps is quite a good framerate for network gameplay, you might want to bring it down a bit, to like 15 fps. With the linear interpolation, it should make very little difference. For the clients, it''s only 1.3k/s. A mere trickle.

with 32bit value for x and z, you have an accuracy of worldsize/65536.0f, which is pretty damn good. say the table is 3.0 meters by 1.5 meters, you''ll have an accuracy of a 45.7 microns along the length of the table, and 22.9 microns along the width . so you can pack the floating point value into even less, like 12 bytes for each coordinates (0.732->0.366 milimeters accuracy), and use the extra byte to store, say, the index of the ball and other flags.

When the shot is finished, send a complete update packet, with ensured delivery, and let another machine take over (or use the machine with the best connection as a server). And I hope you use UDP, not TCP/IP.

Share this post


Link to post
Share on other sites
quote:
Original post by Erik S. Andersson
I believe that you (or Peter Lindcroft) have already answered your own question. Different FPUs might calculate slightly differently, and using a bigger float will not change this. It might of course still solve the problem if the differences become insignficant, but I assume you have already tried it. Since you have already tried complete updates I would suggest using fixed point calculations.


You have any proof of that ? I have never experienced that two different FPUs perform its calculations different. If they do, one of them must not following the rules of the artimetch calculation (or whatever calculation the FPU performs). Ergo, one of the FPUs must contain a bug, similair to the bug one of the first Pentiums contained.

I just made a test now on 5 different machines with heavy calculations, logging all results into a file and comparing those files. None of them differs from each other or give different results. All of the computers have Intel based CPUs ranging from Pentium MMX to P4, so I assume that if its true what you are saying, the difference would appeare on these machines.

I cant understand that people come up with all this suggestions like using double instead of float as the problem is not directly the precision etc. I am pretty sure this problem is the typical problem I described earlier, that when you do not sync the game to the lowest denominator, i.e. the slowest computer in the game. That is a well know and common problem, that different time updates gives very different results on different computers.

EDIT: So I doubt that the problem will go away by changing to double or fixed point as the time difference and therefore the motion simulation will still differ on the different computers

[edited by - calvincoder on July 27, 2003 9:12:34 PM]

Share this post


Link to post
Share on other sites
Now I''m not gonna send over the coordinates of 20-odd balls * float(X,Y,Z) * 60*say 5 seconds (20*12*300 bytes) to all the players watching me take a shot!

why not just send the vector of each ball ... when that vector changes ... send the change and an updated position from the player taking the shot. You can do some prediction on the client side unitl the next update


Share this post


Link to post
Share on other sites
quote:
Original post by Jenison
Now I''m not gonna send over the coordinates of 20-odd balls * float(X,Y,Z) * 60*say 5 seconds (20*12*300 bytes) to all the players watching me take a shot!

why not just send the vector of each ball ... when that vector changes ... send the change and an updated position from the player taking the shot. You can do some prediction on the client side unitl the next update





I am pretty sure that this is what he is doing already or something similiar, which should be quite obvious.

However, this still wont fix his syncing problem as the timing is for sure the problem. Even with a prediiction system it will be worng, and it should also be uncessary to use prediction at all if he sends vector for each ball. Then he has all the necessary information he needs to do a simulation through physics without doing and prediction at all.

/me wonder if anyone at all reads the replies posted here before they are posting their reply?

Share this post


Link to post
Share on other sites
quote:
Original post by CalvinCoder

You have any proof of that ? I have never experienced that two different FPUs perform its calculations different. If they do, one of them must not following the rules of the artimetch calculation (or whatever calculation the FPU performs). Ergo, one of the FPUs must contain a bug, similair to the bug one of the first Pentiums contained.


No, IEEE compliant FPUs can produce marginally different results for some calculations. You could try reading the Lindcroft article if you want, or this one: http://www.gamasutra.com/features/20010713/dickinson_03.htm .

quote:
Original post by CalvinCoder
I just made a test now on 5 different machines with heavy calculations, logging all results into a file and comparing those files. None of them differs from each other or give different results. All of the computers have Intel based CPUs ranging from Pentium MMX to P4, so I assume that if its true what you are saying, the difference would appeare on these machines.



No, that''s not what I or anyone else is saying.

quote:
Original post by CalvinCoder
I cant understand that people come up with all this suggestions like using double instead of float as the problem is not directly the precision etc. I am pretty sure this problem is the typical problem I described earlier, that when you do not sync the game to the lowest denominator, i.e. the slowest computer in the game. That is a well know and common problem, that different time updates gives very different results on different computers.



I am not at all sure that the problem has anything to do with what you suggest. He doesn''t have to do any calculations per frame at all, and I don''t think he does.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
What could be happening, might be some error from the inital contact event from cue/ball due to perhaps a timming error or perhaps the innate update function of the physics engine. And from that small error, it proprogates until the error grows large enough for the systems to diverge noticablly.

Fix time steps are nessecary for this kind of distributed simulation, if you want to syncrhonize them. Here is another gamastura article which might help :

http://www.gamasutra.com/features/20010713/dickinson_01.htm

Bascially your creating a replay system on the client side. Given the input of the inital cue/ball impact, simulate the outcome to +1000 steps, etc.. Any use of the system clock will result in divergence between the simulations, as explained by the article. You need to synchonize onto a fixed time step, and isolate possible extenral inputs, which in your case should be simply just the cue movement.

I dont think its difference of floating point calcuations.

Good Luck!

-ddn

Share this post


Link to post
Share on other sites
quote:
Original post by Erik S. Andersson

No, IEEE compliant FPUs can produce marginally different results for some calculations. You could try reading the Lindcroft article if you want, or this one: http://www.gamasutra.com/features/20010713/dickinson_03.htm .




Very interesting article, thank you

quote:
No, that''s not what I or anyone else is saying.



Yes, this is what you are saying, that 2 different FPUs can produce 2 difffent results... A Pentium 200 MMX uses another FPU than Pentium III 1.0 GHZ which again uses a different FPU than P4 2.4 GHZ... You directly say that 2 different FPU might produce different results and you then indirectly say that these FPUs I am refering to might compute different results.

And you are right, at least according to the article you refere too. A very interessting article btw, I have never seen it nor have I in my 13 years as a game developer experiencded the problem either. It might have been there but at least not made a problem for my calculations. Maybe I havent made good enough games

Thats why I was trying to reconstruct the problem on the platform the article is refering to, which is also the platform I assume the pool game is made for without checking if thats true, and that platform is PC. Most PCs runs on Intel architechture, with also many intel clones as AMD for example. And according to the article, all of those are to consider as different FPUs.

I have now tried to reconstruct this error on different PCs with different CPU from Intel and AMD, i.e. they run on different FPUs all of them.

I believe of course the article and your word, but I have still hard to believe that this can be such a common problem. I havent been able to reconstruct this different marginal results with neither simple calculations nor heavy calculations... I got only the same result on all platfomrs I was trying

But it is probably something in it and it is very good to know about for the future.

And please do not misunderstand me, I of course clearly see the problem for him if it is really that. I am just in the opinion that he havent synced his game at all, i.e. using the same time reference on all computers, but I might be wrong.

quote:


I am not at all sure that the problem has anything to do with what you suggest. He doesn''t have to do any calculations per frame at all, and I don''t think he does.



Well, still I am pretty sure in my case, I will not disagree with you and I will therefore agree that it might not be 100% sure if it is a timing issue....

And ff course he doesnt have to do calculations pr. frame, this is what I am saying. With physics you often want to do this frameindepented and use only time as a reference.

Since he is making a pool game that uses a lot of physics, he of course needs to take the time into consideration for many of his calculations, thats quite obvious. And it is a really common problem to not sync a network game to the lowest denominator which is the slowest computer. There exists other solutions to, but this is the most common way to do it... If you have ever played a multiplayer game and a player that has a really slow computer enters the game, you relly see the lag and know what this is all about: The game syncs to the slowest computer and even the most super hyper fast computer will run at the same speed as the slowest one, because time needs to be synced... It doesnt mean that the rendring is slow, no, it means that objects do not get updated as quiclky as before since the time reference now is very high.

To simulate motion you MUST have time as a reference. If he updates all states on all computers each 30 ms, INDEPENDENT OF THE FRAME, the game will be in sync. If he does not use 30 ms on all computers the game will become out of sync when it comes to motion.

As he stated in an earlier post here if I am not mistaken (did not read through one more time), he only sends off the vectors of the ball..... So when a player hits the ball with the cue, for example the force and direction is sent to the other player(s) and all calculations are made local... If not the calculations on each computer uses the same time reference in their calculations, the ball will end up in 2 different locations on those two computers... As far as I understood, it is exactly this what is his problem.

Of course, if he uses the same time difference on each computer, the problem might be what he (and you) are refering too, the problem with different FPUs. However, why I assume it is the sync problem I am explaining is because he wonders how he should sync he game and he therefore apparently hasent synced it.

I want to add that maybe I have missed his point, but I understood it as that he has made this pool game and that balls do not move the same on different computers and that it happens all the time... I assume that he do all calculations local on each computer. Out of these, I only see one thing: TIMING....

Share this post


Link to post
Share on other sites
quote:
Original post by Anonymous Poster
What could be happening, might be some error from the inital contact event from cue/ball due to perhaps a timming error or perhaps the innate update function of the physics engine. And from that small error, it proprogates until the error grows large enough for the systems to diverge noticablly.

Fix time steps are nessecary for this kind of distributed simulation, if you want to syncrhonize them. Here is another gamastura article which might help :

http://www.gamasutra.com/features/20010713/dickinson_01.htm

Bascially your creating a replay system on the client side. Given the input of the inital cue/ball impact, simulate the outcome to +1000 steps, etc.. Any use of the system clock will result in divergence between the simulations, as explained by the article. You need to synchonize onto a fixed time step, and isolate possible extenral inputs, which in your case should be simply just the cue movement.




Yes, this is the exact thing I am trying to explain. If you do not use fixed time step, motion will be differnet on each computer. Thank you AP

Share this post


Link to post
Share on other sites