   Client Side Prediction Issues...
  My senior project is coming along right on schedual but im running into some issues with the networking. The game will be a capture the flag type spinoff so getting the players to move smoothly is extreamly important. My team implimented alpha build over the weekend and the network layer was set in place. This is probably a good point to stop and explain the engine design as being i am very new to networking some of you may be able to forewarn me of issues. Archetecture: Server-ClientServer-------The server runs two threads. The first thread is the listen thread. The listen thread waits for new connections and when one is made it creates a new client in a static array and sets it up for sending and recieving data. After the client structure is created it immediatly sends all connected clients a notification through tcp of a new player. It also sends the new client notifications of all existing clients. The final step to the connection process is the sending of a port confirmation to the new client. Each client structure on the server has a stream socket and a datagram socket dedicated entirely to the client. The second thread uses these connections to recieve messages. It first queries all active client structures on the server to recieve any data from each clients stream or datagram sockets. Chat data is put into a queue and later relayed to all connected clients. All other messages get put into a seperate queue if and only if they pass the timestamp (UDP) and they are complete packets (no partial packets, the server throws them out). This thread continues to loop through the clients recieving, sending chat, and queueing data without interaction of the game.When i mention no interaction with the game thats not entirely true. Since multiple threads are running I create a lockinstance and release instance function that are wrapped in critical sections. The gameloop locks the server instance once per frame freezing all activity on the queue. It does this so that the queue may be safely accessed and all messages can be handled.Client-------The client is setup in a similar mannner to the server. It runs one thread that recieves messages from the server and puts them in a queue to be dealt with by the game loop. All outgoing and incoming UDP packets are timestamped and verified. The client has an ID that the server assigns it when connected (the id is just the index in the servers array of client structures). Game-----The game loop is the final piece to the puzzle. This is where all messages get processed in the queue. It is also responsible for sending data to update the server. Every 100ms (subject to change) it sends a position packet that contains a vector that represents world position and a vector that represents velocity. This packet is confirmed and updates the server gamestate. The server game loop sends position data every 100ms as well, the difference is that it sends to each connected client, positions of all other clients. *** So now the problem ***I hope that wasnt too boring, but I think it was needed before I describe the issue at hand. Each client is "predicting" the other clients by them having a position and a velocity. Between packets they continue to move from the last known position with the velocity given. Packets from the server are used to update the position and velocitys. The only exception to this is when a position packet is recieved from the server pertaining to the actual player that belongs to that client it is ignored. Im going to have a seperate packet that fixes the position only if the server detected a problem with one of the requested movements. That may have been confusing but here is a break down of how it goes....Client 0: Server here is my latest position.Server: Client 0 position updated.Server: Client 0. Here is position data for everyone connected.Client 0: Updating positions and velocities of all other players and ignoring my own.Client 1: Server, you do not know i have a hacked game copy but im going to move through this wall. Position data sent.Server: Client 1 position update failed. Sending a notification to him.Client 1: Recieved notification. Damn.I know that the client should probably just be updating its position and velocity from the servers updates as well but when i tried that i found that the client was not able to move. The server had his initial velocity as 0 and by the time the client tried to updated the server he had already recieved a packet setting it back to zero. The real problem that im having is the client side prediction. It correctly predicts the positions but when a server sends a packet to sync the clients the time it takes to get from the server to the client and processed is lost. This means the server sends a packets and by the time it gets to the client it is "old" or a tad behind. Since prediction is always running during this lost time the client ends up where he should be but the packet whips him back ever so slightly. example...Client 0: Predicting client 1...hes on the moveClient 0: Predicting client 1...hes on the moveServer: Sending update....**here there is a small time slice while the packet is in travel**.Client 0: Predicting client 1...hes still on the move Client 0: Recieved update..adjusting position and velocity. **the player is whiped back a small amount (due to time loss)I have a few ideas of how i might solve this but they all have a downside. I was thinking about only adjusting position if the velocity has changed. I think that this would still get a whipping effect when velocity is changed though and it also means that if a player moved in one direction for a long time he could get way off sync. I was also thinking of scaling the velocity somehow using the difference in the distances of the recieved packet and current position. Any ideas or advice would be HIGHLY appreciated. You can check out the project at www.fatesforgiven.com to see its status.Thanks, Daniel Doptis 
  You mention the packets are timestamped.You should take this into account. So if the client receives a position packet, it says ''player 3 is at 6,7,1 moving in direction 0,0.8,0.3 velocity 2 at time 2376234''.The client is synchronized to the server''s clock, and he knows the time is already 2376723 (assuming milliseconds), and updates the position using position, direction, velocity and time passed. This should solve the pushing back problem.The server does the same, the client dates his position update, and the server calculates a predicted position (and corrects it for walking through walls).The only problem with this is that (in a shooter) a hacked client could backdate his shots or movements by 200ms and be able to duck and strafe to avoid all bullets just in time. ;  When i said timestamped i should have clerified that its not actual times. I use an unsigned char that just keeps a count. If someone could tell me a good function for getting the time in c++ i could try that but if the clocks were off it would cause huge problems i think.Daniel Doptis ;  The client can synchronize with the server when connecting. The client sends his time (gettickcount()), the server sends ''my time is x, you said y'', the client says ''my time is now z, you said x'', a few of those and you can have them reasonably synchronized.  There should be articles about this in the articles section. ;  Thanks a bunch, I actually just fired up a few articles and am going to attempt a synchronized clock. If i can get it to a reasonably close value it should be a gift from gods when it comes to client side prediction.Daniel Doptis   [edited by - Jasten on February 10, 2004 2:59:06 PM];  sending actual time values wont work since there''s a good chance they might not be synchronized (the player might even be in a different time zone).instead you should try to estimate the lag (roundtrip) by measuring the time it takes for a single packet to be acknowledged and dividing it by two. it won''t work perfectly, esp. for asymetric connections, but it''ll be close enough and atleast an order of magnitude better than real time values.hope this helps.. ;  Thanks for the input!As a quick update I just the client clocks to Sync with the server. No actual times but rather the client stores and maintains a copy of the servers tick count and updates it accordingly. Every five seconds i have the clients ping the server and the server replies immediatly with a pong message. I log the time the message left the client, the time it arrived on the server, and the time it made it back to the client all based on the servers clock and the clients estimate of the servers clock. When the pong message returns I check to see if the round trip time was at or below the average (I store the last 32 pings in an array). If it was average or better i check the clients clock against what the pong packet said it should be and if its off by more then 5ms I fix it. There was a great article i found on this topic, below is a link. The only thing thats a real pain is testing it since when i output the timers value on two seperate machines the outputs are not in sync, But it seems to be pretty accurate. Networking: Synchronizing Network Clockswww.codewhore.com/howto1.htmlCopyright (c) 1999-2003 Matt Slot and Ambrosia Software, Inc.Thanks Again, Daniel Doptis   [edited by - Jasten on February 11, 2004 6:10:25 PM];  Now THIS was one of the more useful threads I''ve seen on gamedev! ;  Glad you found the article helpful. One change I''d suggest is using the median value instead of the average for your cutoff. Consider the following sequence of ping times: 50, 40, 60, 50, 2000, 40,... Even one bad ping in 32 will skew your average (in this case it changes an average of 50 into an average of 110).On the other hand, make a sorted copy of the ping array and pick the middle entry (sorted_ping[num_entries / 2]). This is the median value, which means that half of the pings are less than or equal this number and half are greater than it. This is much more useful for network pings, where the results have a pretty firm lower bound (speed of light) but any number of errors can arbitrarily increase the latency. You''ll often get a couple screwball results, but most will be clumped toward the lower end.Another note: if your physics are based on this clock, you need to make sure that the clock only reports increasing values. Imagine that you roll the clock back 5ms to correct for some drift, causing the falling object on screen to actually go up for a frame. The solution is simple: unsigned long GetSafeNetworkTime(){static unsigned long saved = 0;unsignd long timer = GetRealNetworkTime();// Never return a timestamp older than the previous oneif (timer < saved) timer = saved;else saved = timer;return timer;}  Your simulation may stall for a frame while the clock sorts itself out, but it won''t actually hiccup.;  Thank you for the advice. I have updated the timer to use the median instead like suggested. Unfortionatly were having some problems with cleaning up some bugs in our alpha so I have not been able to test out the networking properly yet. Im sort of at a bottleneck in production and am trying to utilize the time to do some optimization. I was wondering where i should draw the line between packet size and packet amount. In the current design i broke the packets down to relatively small and specialized. What i notice is that the hardware tends to combine smaller packets being sent out. This is dealt with in the engine but im thinking that i may save some cpu time by pushing more data into a tad larger packets. Anyone have any suggestions on the balance between packet size and amount ?Thanks, Daniel Doptis  