Sign in to follow this  

Dealing with Latency...?

This topic is 4589 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Ok, I followed the "Targetting" tutorial on Gamedev for my little spaceship game (think subspace clone), and i'm still getting a little bit jaggedy results (it improved quite a bit, but not all the way). What i'm doing: Before I send out the player update which holds their position and velocity info, I look at a latency variable which gets filled every few seconds (this variable holds my guess at latency by sending out a packet to the server and seeing how long it takes to get a response and dividing that time in half) then I move the ship to where it will be in that in the future after that amount of latency time elapses to make up for the lag from player to server, and send off that packet to the server. The server gets the packet and sends it to all the other players. The other player recieves the original player's update, and looks at it's own latency to the server (obtained in the same way I mentioned first), and advances the ships update position even further according to that latency. Looking at the latency results, it appears one client has around a 15ms latency, the other client has around a 29ms latency. How can I improve upon this implementation to get even smoother results? Right now this is all on a LAN, and i'm kinda surprised the latency is enough to even make the movement jaggedy without interpolation of some sort in the first place. Hopefully my description of how i'm doing it right now made some sense.

Share this post


Link to post
Share on other sites
You should constantly be computing round trip time using a filtered mean-deviation estimator:

RTT calculation.
More info here.

Part of the extra delay could be due to your simulation rate and network update rate. If you are running at 60Hz, there will be an average extra delay of 1/60*.5, or 16.667*.5 = 8.33ms.

See Dead reckoning and Ghosts for networked object motion (smoothly interpolate between object's and their ghosts).
See here for more information.
Smoothing motion.

Share this post


Link to post
Share on other sites
Can you explain the formulas from your first link a bit?

mean’ = (7/8)*mean + (1/8)*(rtt)
sdev’ = (3/4)*sdev + (1/4)*abs(rtt-mean)


mainly, what are the variables 'mean', 'rtt', 'sdev', and how do I get them?

Share this post


Link to post
Share on other sites
I would assume, from context, that those variables are:

rtt: raw round-trip-time sample, as measured on a single packet round-trip
mean: average round-trip-time, as used by the system
sdev: standard deviation of the round trip time

This just runs simple statistics on the round trip time in an attempt to smoothly adapt the program to changing networking conditions.

Share this post


Link to post
Share on other sites
Ok thanks for clarifying it. I know how to get the average, but I forget how to get the standard deviation of a set of numbers. And then what do I do with the results of those formulas? Do I use the mean' or sdev' as the guessed timeframe for moving the object?

Still trying to wrap my head around the cubic spline tutorial, the description of how to implement the formulas didn't make a lot of sense.

Share this post


Link to post
Share on other sites
Quote:
Original post by nPawn
Ok thanks for clarifying it. I know how to get the average, but I forget how to get the standard deviation of a set of numbers. And then what do I do with the results of those formulas? Do I use the mean' or sdev' as the guessed timeframe for moving the object?


See Jacobson's paper for a complete description of the algorithm. The concepts are important, and are a good starting point. However, feel free to modify and change the design once you get an idea for how it works with your particular application. A real-time graph showing network history is extremely valuable in tuning a custom protocol.

An example Graphical Trend Analyzer (if there is any interest, I can provide the rest of the code after E3):


struct TrendAnalyzer {
int historyLength;
FIRfilterDynamic filter;
FIRfilterDynamic filterMin;
FIRfilterDynamic filterMax;
DynArrayNCD<float> sampledHistory;
DynArrayNCD<float> filteredHistory;
float absoluteMin,absoluteMax;
float filteredMin,filteredMax;
float filteredMinMaxRate;
float RANGE_INIT;
int head;
TrendAnalyzer() : sampledHistory(0), filteredHistory(0), historyLength(0) {
RANGE_INIT = 1e6;
filteredMinMaxRate = 1.f/(60.f*2.f);
reset();
}
~TrendAnalyzer() {
free();
}
void free(void) {
sampledHistory.free();
filteredHistory.free();
} // free
void init(int _historyLength) {
free();
historyLength = _historyLength;
sampledHistory.setSizeMaxCount(historyLength);
filteredHistory.setSizeMaxCount(historyLength);
filter.init(_historyLength);
filterMin.init(_historyLength);
filterMax.init(_historyLength);
reset();
} // init
void reset(void) {
for (int i=0; i < historyLength; i++) {
sampledHistory[i] = 0.f;
filteredHistory[i] = 0.f;
} // for
absoluteMin = RANGE_INIT;
absoluteMax = -absoluteMin;
filteredMin = 0.f;
filteredMax = 0.f;
head = 0;
filter.reset();
filterMin.reset();
filterMax.reset();
} // reset
void update(float sample) {
if (sample < absoluteMin) absoluteMin = sample;
if (sample > absoluteMax) absoluteMax = sample;
sampledHistory[head] = sample;
filteredHistory[head] = filter.updateAndGetFilteredSample(sample);
if (++head == historyLength) head = 0;

float currentMin = RANGE_INIT;
float currentMax = -currentMin;

int i;
for (i=0;i < historyLength; i++) {
float sample = sampledHistory[i];
if (sample < currentMin) currentMin = sample;
if (sample > currentMax) currentMax = sample;
sample = filteredHistory[i];
} // for

float filteredMinT = filterMin.updateAndGetFilteredSample(currentMin);
float filteredMaxT = filterMax.updateAndGetFilteredSample(currentMax);
filteredMin = rLerp(filteredMinMaxRate,filteredMin,filteredMinT);
filteredMax = rLerp(filteredMinMaxRate,filteredMax,filteredMaxT);

} // update

virtual void line2D(float x1,float y1,float x2,float y2,ColorARGB color)=0;
virtual void rect2D(float x,float y,float width,float height,ColorARGB color)=0;
virtual void text2D(const char * s,float x,float y,ColorARGB color)=0;
virtual float textPixelWidth(const char * s)=0;
virtual float textPixelHeight(const char * s)=0;

virtual void render(float cx,float cy,
float width,float height,
float borderWidth,
ColorARGB backgroundColor,
ColorARGB historyColor,
ColorARGB filteredHistoryColor,
ColorARGB minColor, // Min value line
ColorARGB maxColor, // Max value line
float minRange,float maxRange, // When both are -1, use dynamic range.
float scale, // Scale the rendered values (scale = frameRate*8/1000, scale*bytesPerFrame = KBits/sec).
const char * units, // f/s, KBit/s, etc.
const char * title) {

rect2D(cx,cy,width,height,backgroundColor);

width -= borderWidth*2.f;
height -= borderWidth*2.f;
float maxOffsetY = height-1.f;

float startX = cx + borderWidth;
float startY = cy + borderWidth + maxOffsetY; // Drawing from bottom up

float scaleX = (width-1.f)/float(historyLength-1);
float scaleY;

float sampleOffsetY,rangeY;

if (minRange == -1.f && maxRange == -1.f) {
rangeY = filteredMax - filteredMin;
sampleOffsetY = filteredMin;
} else {
rangeY = maxRange - minRange;
sampleOffsetY = minRange;
} // if

if (rangeY > 0.f) scaleY = maxOffsetY/rangeY;
else scaleY = 0.f;

float lastX;
float lastY;

// Draw sampledHistory
int pos = head; // Start at oldest sample, move toward newest sample
int i;
for (i=0; i < historyLength; i++) {
float x = startX + float(i)*scaleX;
float biasedY = sampledHistory[pos]-sampleOffsetY; // Bias so min is near zero
float y = startY - clamp(biasedY*scaleY,0.f,maxOffsetY); // Drawing up
if (i > 0) {
line2D(lastX,lastY,x,y,historyColor);
} // if
lastX = x;
lastY = y;
if (++pos == historyLength) pos = 0;
} // for

// Draw filteredHistory over sampledHistory
pos = head; // Start at oldest sample, move toward newest sample
for (i=0; i < historyLength; i++) {
float x = startX + float(i)*scaleX;
float biasedY = filteredHistory[pos]-sampleOffsetY; // Bias so min is near zero
float y = startY - clamp(biasedY*scaleY,0.f,maxOffsetY); // Drawing up
if (i > 0) {
line2D(lastX,lastY,x,y,filteredHistoryColor);
} // if
lastX = x;
lastY = y;
if (++pos == historyLength) pos = 0;
} // for

rangeY = absoluteMax - absoluteMin;
if (rangeY > 0.f) scaleY = maxOffsetY/rangeY;
else scaleY = 0.f;

// Render title
float stW = startX + width - 1.f;
float stYMin = startY-height;
float stX = startX;
text2D(title,stX,stYMin,ColorARGB(127,127,240,240));

// Render average (last filtered history value)
int newestIndex = head > 0 ? head-1 : historyLength-1;
char buff[64];
sprintf(buff,"AVE %3.3f %s",filteredHistory[newestIndex]*scale,units);
text2D(buff,stX,startY-borderWidth,ColorARGB(127,200,200,100));

// Render Absolute Max
sprintf(buff,"AMAX %.3f",absoluteMax*scale);
stX = stW - textPixelWidth(buff);
text2D(buff,stX,stYMin,ColorARGB(127,192,192,192));
stYMin += textPixelHeight(buff)+1.f;

// Render Absolute Min
sprintf(buff,"AMIN %.3f",absoluteMin*scale);
stX = startX + width - textPixelWidth(buff) - 1.f;
float stYMax = startY-borderWidth;
text2D(buff,stX,stYMax,ColorARGB(127,192,192,192));
stYMax -= textPixelHeight(buff)+1.f;

// Render filteredMax line
float lineY = startY-filteredMax*scaleY; // Drawing up
lineY = clamp(lineY,stYMin,stYMax);
line2D(startX,lineY,lastX,lineY,maxColor);
sprintf(buff,"FMAX %3.3f",filteredMax*scale);
float fmaxWidth = textPixelWidth(buff);
stX = stW - fmaxWidth;
text2D(buff,stX,lineY,ColorARGB(127,200,100,100));
float minLineY = lineY + textPixelHeight(buff) - 1.f;

// Render filteredMin line
lineY = startY-filteredMin*scaleY; // Drawing up
lineY = clamp(lineY,stYMin,stYMax);
line2D(startX,lineY,lastX,lineY,minColor);
sprintf(buff,"FMIN %3.3f",filteredMin*scale);
stX = stW - textPixelWidth(buff);
if (lineY < minLineY) stX -= fmaxWidth+textPixelWidth(" ");

text2D(buff,stX,lineY,ColorARGB(127,100,200,100));

} // render

};




Quote:
Original post by nPawn
Still trying to wrap my head around the cubic spline tutorial, the description of how to implement the formulas didn't make a lot of sense.


Skip the spline method for now. To start, just interpolate between the two positions/orientations.

This method adds some positional delay (lag), but it's easy to implement:

alpha = 1.f/15.f // arbitrary. Set to suit desired behavior.

localPosition = lerp(alpha,localPosition,ghostPosition) // vectors
localRotation = slerp(alpha,localRotation,ghostRotation) // quats
(You can do the same for the velocities).

The above is an IIR filter (Infinite Impulse Response filter), and is also a low-pass filter (high frequency motion will be smoothed: this also results in some delay).

Share this post


Link to post
Share on other sites
Quote:
Original post by nPawn
I assume Lerp is just finding the midpoint between the two points? then we multiply that by the alpha?


lerp = Linear Interpolation. Example for a vector:


inline Vec3 lerp(const flt a,const Vec3 & lo,const Vec3 & hi) {
return lo + (hi - lo)*a;
} // Vec3 lerp





http://catb.org/~esr/jargon/html/L/LERP.html
http://ggt.sourceforge.net/html/group__Interp.html

If your game is 2D, you won't need slerp (for 3D rotations). For 2D, just lerp the rotation angles.

See www.google.com and search for lerp, slerp, etc., for more info.

Share this post


Link to post
Share on other sites
using the Lerp is the smoothest i've seen yet. It's really smooth on one computer, but another computer still gets spurts of extra speed (like it's zooming to catch up), but the jerkiness/jumping for it is all but gone. Gonna play with things until I can hopefully get the "catch up" fixed.

Would you mind explaining what the Lerp is doing? Linear Interpolation doesn't mean anything to me, i've heard the term but dunno what it means. Sorry for all the questions but i'm really new with this topic so i'm not sure what is being accomplished other than a smoothing of sorts. Thanks for all your help.

Share this post


Link to post
Share on other sites
The problem with using that alpha is that, if you want to move from point 0 to point 1 with an alpha of 10 (say), you will move:

In the first timestep, from 0.0 to 0.1
In the second timestep, from 0.1 to 0.19
In the third timestep, from 0.19 to 0.271
...

I e, you'll start out going fast, and "ease off" towards the goal.

There are better interpolators/extrapolators pointed at from the Forum FAQ.

Share this post


Link to post
Share on other sites
Quote:
Original post by hplus0603
The problem with using that alpha is that, if you want to move from point 0 to point 1 with an alpha of 10 (say), you will move:

In the first timestep, from 0.0 to 0.1
In the second timestep, from 0.1 to 0.19
In the third timestep, from 0.19 to 0.271
...

I e, you'll start out going fast, and "ease off" towards the goal.

There are better interpolators/extrapolators pointed at from the Forum FAQ.


An IIR low-pass filter (LPF) does an excellent job of smoothing motion. The above analysis shows what will happen for two sample points. This will work fine even if an object moves then immediately stops. I find it can look better than ease-in and ease-out, especially for character motion.

For a constant stream of movement data, the IIR LPF will provide high-quality, smoothed motion (at the expense of added filter delay). If one's code results in jumpy motion, it sounds like the ghost is not being simulated with velocity. That is, it sounds like updates are showing up as descrete locations, where the interpolation is always towards a fixed location. If both the local, visual object and ghost object are moving (classic dead-reckoning), the interpolation will be smooth and seamless (as would be expected from an IIR LPF).

I looked through the FAQ, and found Gaffer's article on networked physics. The smooth() function from Cube.h:

Quote:

/// Smooth physics state towards target.

void smooth(const State &target, float tightness)
{
previous = current;
current = target;
current.position = previous.position + (target.position-previous.position) * tightness;
current.orientation = slerp(previous.orientation, target.orientation, tightness);
current.recalculate();
}


The tightness argument is alpha. This is the exact same IIR LPF I posted above. The demo works fine and shows very smooth motion (I also shipped a commercial game using the IIR LPF: the networked game was reviewed as smooth and having no lag (2002)). I tested various spline and other methods, but the simple IIR LPF always won the comparisons for that particular game (I also considered a predictive filter, such as the Kalman Filter (might help mitigate added filter delay), but since the IIR LPF worked so well, I did not pursue further research and testing). A combined IIR LPF + spline method might work better for some types of motion. Carefully changing alpha/tightness can help in reducing delay, but for a basic test and just getting started, it can be fixed.

What method in the FAQ do you see as having better performance?

Share this post


Link to post
Share on other sites
The question is what you smooth towards. If you smooth towards a goal that evolves each frame, i e you smooth towards the dead-reckoned position of the interpolated object, then you'll have pretty good behavior. However, if you smooth towards a received target point, that stays the same until you receive the next target point, then you will not get the smoothest movement possible -- the single-pole filter you describe just isn't enough to clean up the stair-step signal of discrete jumps in position.

The OpenTNL whitepaper describes a forward extrapolation method where you interpolate between forward-extrapolated positions. The basic implementation of this (for a fixed timestep dt) would be when you receive an update for time T, you forward-extrapolate this update (using dead reckoning) to time T+dt. Then you take your last sample (arrived at T-dt, forward-extrapolated to T) and interpolate between these two points over a time interval of dt.

Share this post


Link to post
Share on other sites
Quote:
Original post by hplus0603
The question is what you smooth towards. If you smooth towards a goal that evolves each frame, i e you smooth towards the dead-reckoned position of the interpolated object, then you'll have pretty good behavior. However, if you smooth towards a received target point, that stays the same until you receive the next target point, then you will not get the smoothest movement possible -- the single-pole filter you describe just isn't enough to clean up the stair-step signal of discrete jumps in position.

The OpenTNL whitepaper describes a forward extrapolation method where you interpolate between forward-extrapolated positions. The basic implementation of this (for a fixed timestep dt) would be when you receive an update for time T, you forward-extrapolate this update (using dead reckoning) to time T+dt. Then you take your last sample (arrived at T-dt, forward-extrapolated to T) and interpolate between these two points over a time interval of dt.


How are you going to dead-reckon an object with an implied zero-velocity: "a received target point, that stays the same until you receive the next target point"?

Can you see that my example, Gaffer's example and demo, and the following from the OpenTNL site:

Quote:

In the Torque Game Engine, player objects controlled by other clients are simulated using both interpolation and extrapolation. When a player update is received from the server, the client extrapolates that position forward using the player's velocity and the sum of the time it will use to interpolate and the one-way message time from the server - essentially, the player interpolates to an extrapolated position. Once it has reached the extrapolated end point, the player will continue to extrapolate new positions until another update of the obect is received from the server.

By using interpolation and extrapolation, the client view can be made to reasonably, smoothly approximate the world of the server, but neither approach is sufficient for real-time objects that are directly controlled by player input. To solve this third, more difficult problem, client-side prediction is employed.


are all classic dead-reckoning (extrapolation) with interpolation between the locally simulated objects and their ghosts? I've implemented many different methods (including the one described on the OpenTNL site where RTT/2 is used to compute alpha), and the IIR LPF between local/ghost is the easiest general+jitter-free solution. You can simulate the "square-wave" motion case with Gaffer's demo: just tap a key to move the cube and watch the motion (server's view turned on): it starts fast and slows toward the target. This looks excellent for most object types (including characters: this is the same method I used in the past for an Xbox Live launch title). When alpha is computed from the RTT (to provide a more linear change in motion, but not smoother motion), extra work must be done to prevent jitter. Smoother start/stop/delta-v motion can be achieved by incorporating an interpolating spline (such as Catmull-Rom).

The most efficient way to handle an object "that stays the same until you receive the next target point" (velocity is known to be zero after target reached) is to send a reliable message telling the object to go to the new location, whereby the object moves to the new location using any preprogrammed/simulated motion behavior.

Share this post


Link to post
Share on other sites
I guess my point is that you can do a better job if you receive position+velocity, instead of just position. As I said, I think the IIR method is much more reasonable if the target of the IIR is a position that, in turn, has been dead reckoned from a P+V update. If you don't have P+V, but you can delay by one update period, then you can extract P+V by using P(t-1) and P(t)-P(t-1) for your P+V at t.

The alternative is to be input-synchronous, and not "interpolate" anything at all. Instead, you co-simulate the same thing on each client. That's what we do, and it works very well (although it was a lot of effort to get to a point where it's robust, efficient and re-usable).

Share this post


Link to post
Share on other sites
Quote:
Original post by hplus0603
I guess my point is that you can do a better job if you receive position+velocity, instead of just position. As I said, I think the IIR method is much more reasonable if the target of the IIR is a position that, in turn, has been dead reckoned from a P+V update. If you don't have P+V, but you can delay by one update period, then you can extract P+V by using P(t-1) and P(t)-P(t-1) for your P+V at t.


I agree, and for slower, character-based motion, the above method of extracting/generating velocity (linear and angular) from position history can work fine (classic dead-reckoning typically requires sending the actual velocities). In cases where such implied velocities can be used, network bandwidth is saved. Additionally, velocity can be generated from known states (such as input position and known object behavior). In any case, as the examples above recommend, the velocities for the local and ghost objects should also be interpolated. Again, in the case of an autonomous object, all that needs to be sent is a moveto command: the object starts, accelerates, travels a predefined velocity, then stops at the target location, all predefined (and only requiring a small moveto command).

Quote:

The alternative is to be input-synchronous, and not "interpolate" anything at all. Instead, you co-simulate the same thing on each client. That's what we do, and it works very well (although it was a lot of effort to get to a point where it's robust, efficient and re-usable).


That's true, lock-step simulations require bit accurate calculations, and are very senstive (via divergence) if even a small error is present. My first networked-physics simulations were lock-step due to bandwidth restrictions (serial/modems: 1990-1994). I used CRC's on state blocks to determine divergence, and then resynchronized state. I remember early online FPS games of that genre that would allow the world to become out of sync, and wondered why they did not provide a means to resynchronize. I now use methods that are extremely fault tolerant while at the same time are relatively easy to develop and support.

Share this post


Link to post
Share on other sites

This topic is 4589 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this