Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Dead-Reckoning for Dummies.

techlordtechlord Overland Zark, KSPosts: 220Member

Dear Network Programming Gurus,

I've come to a point in my Semi-Massive Multiplayer First Person Shooter Role Playing Game development where its time to implement Dead-Reckoning. Unfortunately, I have a mental block (of some sort)  preventing me from grasping techniques I've read about in several articles to include gamasutra.com and many others.

Any explanation in LAYMAN terms / Psuedo Code on techniques for Client-side Predition, Network Interpolation/Extrapolation, and Smoothing Algorithms would be greatly appreciated. I've elected to go with a Server-Client Network Model and combat is typical of the First Person Shooter genre.

Sincere Thanks in Advance.

Comments

  • VagelispVagelisp AthensPosts: 448Member Uncommon

    http://creators.xna.com/en-us/sample/networkprediction .Please read the html documentation included with the source code and then have a look at the RollingAverage class. Also http://en.wikipedia.org/wiki/Moving_average. Then please notice the implemenation of this algorithm in the tank class.

    Timing in XNA is usually per a fixed time step (updates data 60 times/sec). Please note this before attempting to use this code for your own needs. In our case the Networksession is updated 10 times per sec since the integer framesBetweenPackets equals 6 at the start of the game.

    Good luck.

        ///<summary>

        /// To compensate for network latency, we need to know exactly how late each

        /// packet is. Trouble is, there is no guarantee that the clock will be set the

        /// same on every machine! The sender can include packet data indicating what

        /// time their clock showed when they sent the packet,
    but this is meaningless

        /// unless our local clock is in sync with theirs.
    To compensate for any clock

        /// skew, we maintain a rolling average of the send times from the last 100

        /// incoming packets. If this average is, say, 50 milliseconds, but one specific

        /// packet arrives with a time difference of 70 milliseconds, we can deduce this

        /// particular packet was delivered 20 milliseconds later than usual.

        ///</summary>

        class RollingAverage

        {

            #region Fields

     

            // Array holding the N most recent sample values.

            float[] sampleValues;

     

            // Counter indicating how many of the sampleValues have been filled up.

            int sampleCount;

     

            // Cached sum of all the valid sampleValues.

            float valueSum;

     

            // Write position in the sampleValues array. When this reaches the end,

            // it wraps around, so we overwrite the oldest samples with newer data.

            int currentPosition;

     

            #endregion

     

     

            ///<summary>

            /// Constructs a new rolling average object that will track

            /// the specified number of sample values.

            ///</summary>

            public RollingAverage(int sampleCount)

            {

                sampleValues = new float[sampleCount];

            }

     

     

            ///<summary>

            /// Adds a new value to the rolling average, automatically

            /// replacing the oldest existing entry.

            ///</summary>

            public void AddValue(float newValue)

            {

                // To avoid having to recompute the sum from scratch every time

                // we add a new sample value, we just subtract out the value that

                // we are replacing, then add in the new value.

                valueSum -= sampleValues[currentPosition];

                valueSum += newValue;

     

                // Store the new sample value.

                sampleValues[currentPosition] = newValue;

     

                // Increment the write position.

                currentPosition++;

     

                // Track how many of the sampleValues elements are filled with valid data.

                if (currentPosition > sampleCount)

                    sampleCount = currentPosition;

     

                // If we reached the end of the array, wrap back to the beginning.

                if (currentPosition >= sampleValues.Length)

                {

                    currentPosition = 0;

     

                    // The trick we used at the top of this method to update the sum

                    // without having to recompute it from scratch works pretty well to

                    // keep the average efficient, but over time, floating point rounding

                    // errors could accumulate enough to cause problems. To prevent that,

                    // we recalculate from scratch each time the counter wraps.

                    valueSum = 0;

     

                    foreach (float value in sampleValues)

                    {

                        valueSum += value;

                    }

                }

            }

     

     

            ///<summary>

            /// Gets the current value of the rolling average.

            ///</summary>

            public float AverageValue

            {

                get

                {

                    if (sampleCount == 0)

                        return 0;

                   

                    return valueSum / sampleCount;

                }

            }

        }

     

     

    Network Prediction Sample

    This sample shows how to use prediction and smoothing algorithms to compensate for network lag, making remotely controlled objects appear to move smoothly even when there is a significant delay in packets being delivered over the network.

     

    Sample Overview

    The Peer-to-Peer and Client/Server samples demonstrate two different network topologies, using an example of a tank that the player can drive around the screen. In both samples, tank data is sent over the network every frame, 60 times per second. That's a lot of data! When playing over a local network, these packets are delivered quickly enough to achieve smooth and continuous movement, but things do not work so well over the Internet. Most Internet connections do not have enough bandwidth to send data so often, and are slow enough that players will see delays and jerkiness in the movement of the tank.

    This sample shows how to make the tank example from the Peer-to-Peer sample work over the Internet. It uses the NetworkSession.SimulatedLatency and NetworkSession.SimulatedPacketLoss properties to artifically emulate a typical Internet connection, so you can see the effects of lag even when testing over a fast local network. It then applies prediction and smoothing algorithms to compensate for this lag, making the tanks move smoothly even though the underlying network data is far from smooth.

    How the Sample Works

     

    Problem #1: Bandwidth

     

    Bandwidth refers to the amount of data that can be sent over a network connection. The XNA Framework measures bandwidth in bytes per second, but you will sometimes also see this measured in kilobits per second (kbps). A kilobit is 128 bytes.

    If you try to send more network data than there is available bandwidth, some of that data will be discarded. If you keep sending way too much data, eventually your connection will be dropped entirely and the network session will end.

    So how much is too much? That depends on how good your network connection is, but as a rule, you should assume a worst case of 8 KB (64 kilobits) per second. Many people will have better connections than this, but if your game requires more than 8 KB, some people will be unable to play it.

    It is surprisingly easy to use too much bandwidth. For example, the Peer-to-Peer sample sends the following data over the network.



    Data


    Type


    Size (bytes)


    Position


    Vector2


    8


    Tank Rotation


    float


    4


    Turret Rotation


    float


    4

    That may not seem like much: it is only 16 bytes in total. But things quickly add up. Every time we send a network packet, approximately 50 more bytes are used for the packet header (28 bytes for a standard UDP packet header, plus ~22 for LIVE and the XNA Framework). Including this header data, our packets are now 66 bytes. We are sending 60 packets per second, which makes 3960 bytes per second. Finally, we must send packets to every other player in the session. If there are three players in total, each of them sends packets to both the others, making a total bandwidth usage of 7920 bytes per second. We have used almost all of our 8 KB total bandwidth, with only three people in the session! The Peer-to-Peer sample is therefore not efficient enough to support even a four-player game over a typical Internet connection.

     

    The best way to reduce bandwidth usage is to send packets less often. Rather than sending every frame, most games send packets only 10 or 20 times per second, and in some cases even less. It might seem as though you could achieve a similar result by compressing your packet data, but that tends to be less useful when you think about the packet header overhead. The Peer-to-Peer sample sends 66-byte packets, which contain 16 bytes of game data plus 50 bytes of header. Even if we could halve the size of our game data, that would only reduce the packets from 66 bytes to 58: not much of an improvement. Decreasing the send rate has a bigger impact because this cuts down on the number of packet headers as well the amount of game data.

     

    When you send packets less often, remotely controlled objects will of course move less smoothly, hence the need for smoothing algorithms to cover up the resulting jerkiness.

    To see the effect of a low packet send rate without any latency or correction algorithms, press X and Y to disable prediction and smoothing, press A twice to change the "Network simulation" setting to 0 ms, and then use B to cycle through the available "Packets per second" settings. Notice how locally controlled tanks always remain smooth, but if you join a second machine into the session, then drive a tank on the first machine while watching the screen of the second, this becomes increasingly jerky the less often you send packets.

     

    Problem #2: Latency

     

    Latency refers to the time delay between a packet being sent and when it is received. Local networks have low latencies (small enough to completely ignore), but the lag can be much higher when playing over the Internet.

    Latency comes from many sources. Firstly, the speed of light, which is 186,282 miles per second. From Seattle to New York is 2413 miles, so even if everything else was perfect, data sent from one side of the United States to the other cannot possibly arrive in less than 13 milliseconds. Also, network data usually travels down fiber optic or copper cables, in which light slows to only 60 percent of its speed in a vacuum. Finally, every piece of hardware along the way causes additional latency. A modem typically adds around 10 milliseconds (there will be two modems, one at each end), while a router (of which there could be several, depending on your ISP) adds between 5 and 50 milliseconds. As a rule, you should assume a worst case of 200 milliseconds latency.

     

    To see the effect of poor network latency without any correction algorithms, press X and Y to disable prediction and smoothing, press B twice to change the "Packets per second" setting to 60, and then use A to cycle through the available "Network simulation" settings. Notice how locally controlled tanks always remain smooth, but if you join a second machine into the session, then drive a tank on the first machine while watching the screen of the second, this becomes increasingly delayed and jerky the more latency you introduce. Unlike the evenly spaced jerks caused by a low packet send rate, the effect of latency is more random, as every packet will be delayed by a different amount of time.

     

    Solution #1: Smoothing

    Although limited bandwidth (which causes you to send packets less often) and latency (which delays the delivery of packets) are different problems, their symptoms are similar: both prevent network data from arriving in time to produce a smooth movement. Fortunately, the same solutions can be used to fix both problems.

    Take this example of a game that sends packets every 0.2 seconds. If the tank drives upward, then turns to the right, following the blue line, it will send three packets at the times and positions shown in this diagram.

     

    If latency delays each packet by 0.1 seconds, a network client will see the tank behaving as follows.

     

    The dotted red lines represent jumps, where the tank moves instantly to the position described in the most recently received packet. Note how the motion is not only jerky, but also delayed. The tank does not move at all for the first 0.3 seconds, as it must wait first for a packet to be sent at 0.2 seconds, plus another 0.1 seconds for that packet to be delivered.

    Smoothing is a simple concept. When a network packet is received, rather than teleporting immediately to the new position, we can interpolate gradually from the previous position toward this new location, giving the illusion of continuous motion. With smoothing in place, our remotely controlled tank will move as follows.

    The jerkiness has been removed, but this is still not perfect. The main problem is that the movement is delayed even worse than before. Not only must we wait for packets to arrive, but now we must also wait while we smooth the tank gradually toward the new position, even after the network has told us what position that is.

    Smoothing without prediction is simple to implement (see the Tank.UpdateRemote and Tank.ApplySmoothing methods in this sample), and may be adequate for some game objects, but objects controlled in this way are always going to be slightly delayed.

     

    Solution #2: Prediction

     

    Prediction algorithms attempt to remove the delay caused by more naive smoothing implementations. Because packets do not arrive instantaneously, it is impossible to ever know exactly where an object is located, but if we know where it was a short while ago when the packet sent, and also know which direction it was moving and whether it was turning, we can make a good guess as to how it is likely to have moved since that time.

     

    To implement prediction, we must include more data in our network packets. If we only sent the tank position, it would be impossible to predict how that might move, so we must also send the velocity and user input controls. Using this extra data, we can make some guesses. For instance, if the first packet tells us "the tank is facing upward, and is not moving, but the user is pressing Up", we can predict it will accelerate upward along this blue line.

     

    After 0.3 seconds, at the same time as our locally simulated tank reaches the end of the blue line, we receive a new network packet. The position in this new packet is somewhat behind where we predicted the tank should be, because the packet took 0.1 seconds to arrive, so our prediction has already moved on past the position where the packet was sent. Also, the new packet contains updated input values, telling us the player is now providing a steer input that will make them curve to the right. Using this new information, we can reset our simulation to the state described in the new packet, and predict the tank will curve to the right along the green line.

     

    But here we have a problem. We have already moved our local tank prediction all the way to the end of the original blue line! That prediction turned out to be close, but slightly wrong. If we move the tank backward to the position described in this second packet, the user will see an ugly jerk, so we cannot directly use this new position. That tells us where the tank was at 0.2 seconds, but we are now at 0.3 seconds, and we don't want to jerk backward. Instead, we assume the tank has been moving along the green line since this packet was sent 0.1 seconds ago, so we take a point 0.1 seconds forward along the green line, which is only a small distance to the right of our original blue prediction. Rather than just teleporting the tank from our old and slightly wrong blue prediction to the newer and hopefully more accurate green prediction, we can use the same smoothing technique described earlier to gradually interpolate from the old position toward the new, covering up this minor misprediction in hopes that nobody will notice it.

     

    This process repeats every time a new packet arrives. For instance, at 0.5 seconds, we get a packet telling us the user is now steering straight to the right.

     

    We incorrectly predicted the tank would continue turning downward along the green line, so we update that guess with the new and more accurate orange prediction, and gradually smooth our position from the incorrect green guess toward the new orange version.

     

    The great thing about prediction is that the object is no longer delayed. When the prediction works well, it will move smoothly and be in the right place at the right time. When things work less well, you may notice the adjustment after a prediction that turned out to be inaccurate. The easiest way to demonstrate this is to move in a straight line, then stop suddenly. The prediction assumed the tank would continue moving, but then a network packet says it has stopped, so the smoothing must move the tank slightly backward to correct for this mistaken guess. Network programming is all about compromises, and even the best prediction algorithms cannot be right 100 percent of the time!

     

    So far we have skimmed over the details of how to actually implement a prediction algorithm. This turns out to be trivially easy for most games, because you can simply reuse your existing object movement code. You already have a method that updates the movement of your locally controlled objects. What better way to predict how a remote object is likely to move, than by running the exact same code that is controlling that movement in the first place? This occurs in two places:
    • When a new network packet is received, Tank.ReadNetworkPacket calls ApplyPrediction. This calls the UpdateState helper method however many times are necessary to compensate for the packet delivery latency. In order to know how much compensation to apply, ApplyPrediction must estimate how long each packet took to arrive. The XNA Framework provides an estimated average network latency via the NetworkGamer.RoundtripTime property, but not all packets will take exactly this average amount of time to arrive. To handle varying latencies per packet, we include the send time as part of our packet data. Trouble is, there is no guarantee that the clock will be set the same on every machine! The sender told us what time their clock showed when they sent the packet, but this is meaningless unless our local clock is in sync with theirs. To compensate for any clock skew, we maintain a rolling average of the send times from the last 100 incoming packets. If this average is, say, 50 milliseconds, but one specific packet arrives with a time difference of 70 milliseconds, we can deduce this particular packet was delivered 20 milliseconds later than usual.
    • Tank.UpdateRemote also calls the UpdateState helper, keeping the tank moving smoothly along its predicted path during the gaps between one packet and the next.
    One of the many paradoxes of network programming is that prediction algorithms can reduce our total bandwidth usage, even though they require sending more data over the network. Remember how the Peer-to-Peer sample sent only the position and rotation (a total of 16 bytes), but had to do this 60 times a second, making a total of 3960 bytes per player per second? To implement prediction, we must also send time, velocity, and controller input data, but thanks to the prediction, we can now get away with sending packets less often. Look how the math works out.



    Data


    Type


    Size (bytes)


    Packet Send Time


    float


    4


    Position


    Vector2


    8


    Velocity


    Vector2


    8


    Tank Rotation


    float


    4


    Turret Rotation


    float


    4


    Tank Input


    Vector2


    8


    Turret Input


    Vector2


    8

    That is 44 bytes of game data. Adding a 50-byte packet header, and multiplying by 10 packets per second, this yields a total of 940 bytes per player per second, so we can now support up to 9 players within our 8 KB total bandwidth.

     

    Extending the Sample

    You can further reduce bandwidth usage by using smaller data types to transmit the tank state. For example, you could convert the position and velocity to HalfVector2 format, the input vectors to NormalizedByte2, and then scale the rotations to fit into a single byte. This would reduce the game data to only 18 bytes, letting you fit 13 players into your total 8 KB.

    © 2007 Microsoft Corporation. All rights reserved.

    Send feedback to xnags@microsoft.com.

     

  • techlordtechlord Overland Zark, KSPosts: 220Member

    WOW! This is the best Article on Dead-Reckoning I've read yet.

    Thanks Vagelisp

  • VagelispVagelisp AthensPosts: 448Member Uncommon

    You are welcome.

    People behind the XNA team are doing a great job imho. I have read many articles about almost every aspect of gaming but it's not easy to find better samples and documentation than the ones posted at the XNA creators club. I think they are a good read even if you don't use the XNA framework.

  • techlordtechlord Overland Zark, KSPosts: 220Member
    Originally posted by Vagelisp


    You are welcome.
    People behind the XNA team are doing a great job imho. I have read many articles about almost every aspect of gaming but it's not easy to find better samples and documentation than the ones posted at the XNA creators club. I think they are a good read even if you don't use the XNA framework.



     

    I agree and registered on XNA. I really like the concept behind it. I'm currently programming with DarkBasic Pro, but, I'm looking C# during breaks. I'll take a look some of the other tuts. Once again, thanks.

     

  • BarrikorBarrikor Phoenix, AZPosts: 330Member Uncommon

    @ Vagelisp

    Now that's Impressive,
    And it's Readable :) thanks for coloring the syntax for us too :)

  • sosjanikasosjanika sfghghPosts: 1Member
    Hi, where can we find the illustration and the diagrams? Thank you.
  • l2avisml2avism Posts: 386Member Uncommon

    Basically, each movement/position message sent contains the position AND the velocity.

    You can find the position in any given frame by taking the last position and using time elapsed since last update and the velocity. Its like those math problems you had in physics class.

    When you receive the next update the timing will be off so if you set the new position immediately it would cause rubber-banding. You would do smoothing against the old position to slowly over time bring the current position back inline.

     

    I do this by having the incoming network position unsmoothed, and just smoothing the per frame position computed from velocity like so:

    frame_pos = net_pos_after_velocity * 0.3f + frame_pos * 0.7f;

    Since you do that every frame, it would look like the object curves its path. Its usually completely unnoticeable and easy for novices to code. It doesn't appear to be common practice but it works for me and it looks good. The downside is handling rotation- you may have to use the angle between the old frame position and the new position to avoid the object from facing one direction and moving another when smoothing takes effect.

     

    Many online games take this further and only send movement/position messages when the velocity changes. If you ran in the same direction for an hour, the game would only need one message to represent that. Then when you stopped it would send one more. Typically only FPS style games send out packets at regular intervals, MMO's use the method I just described to be able to handle as many players as possible on any given network.

    The key of network coding is knowing what not to send and when to not send it.

    Another problem arises when you send messages only when someone changes velocity: what happens when someone new logs in or enters range after the change happened? Since you aren't throwing messages out 6 times a second they would not see anyone that doesn't move after they arrive. What I do is basically iterate through the list of players every so many tens of seconds and just resend the last movement message to everyone in range. This is probably why players appear slowly over time in many MMOs when you first enter world.

     

Sign In or Register to comment.