Extrapolator algorithm

Networking and Multiplayer Programming

Started by Tispe October 10, 2013 05:22 AM

4 comments, last by Tispe 10 years, 6 months ago

1,468

Author

October 10, 2013 05:22 AM

Hi, I wanted to ask if anyone (tried to PM hplus0603) could elaborate on the EPIC extrapolator algorithm. http://www.mindcontrol.org/~hplus/epic/

I studied the EPIC extrapolator source and I it seems that only two samples of Pos and Vel is used in calculating a new position and velocity vector. I tried to draw things out but I can't quite see what is being calculated. Here is a drawing of samples (2D):

When the direction does not change the error is zero. But when it starts to turn the estimate overshoots, I get the mechanics behind this.

What I want to know is, how does the algorithm work in order to get back on track quickly.

The estimated position where the entity is drawn must "catch up" with the next estimated position, does this mean the velocity increases beyond the real velocity?

Where exactly do we aim our new estimated velocity vector, if you would look at the image? Do we compensate by speeding up and overshooting the "real velocity vector" (last red line)? Or do we use a smooth cubic method of narrowing in? Or do we just point the corrected estimated velocity vector at the same point the real sample points? What is the vector math here?

What is it meant by "snap" and "aim" velocities/pos in the EPIC source?

Cheers!

hplus0603

11,916

October 10, 2013 03:53 PM

The estimated position where the entity is drawn must "catch up" with the next estimated position, does this mean the velocity increases beyond the real velocity?

Yes, you will get a faster linear speed than the actual movement.

The idea behind EPIC is actually pretty simple. It answers a question somewhat like:
"Given what I know about the position 200 milliseconds ago and 100 milliseconds ago, how would that extrapolate to 100 milliseconds from now?"
And a second question:
"Given where I am now, locally, how do I move to be at that predicted position 100 milliseconds from now?"

So, the answer to question #1 tells us where to go. The answer to question #2 tells us how to get there. Because the extrapolation is always "how do I get from where I am currently, locally, to where I should be, based on network data," the extrapolation will always do a continuous movement.

It's been a while since I was in the code, but IIRC, "snap" is when the timing data is off such that there's no recent history to work with, so the extrapolator has to "make something up" which may generate a non-contiguous movement trajectory.

enum Bool { True, False, FileNotFound };

Tispe

1,468

Author

October 10, 2013 04:31 PM

But what exactly is the vector math here.

1. We get a packet from the server Pos=s0 and Vel=v0, we draw our model each frame using s1+v0*t.

2. We get a new packet from the server Pos=s1 and Vel=v1, our current position is slightly off s1, we don't want to snap over to s1, rather walk towards s1+v1*t such that we will meet up. The velocity vector from where we are now, where does it point? Does it point to the same point s1+v1 is pointing? Does the calculated velocity vector we move along change before we get a new packet or does it stay the same? In the above image I tried to suggest 3 different velocity vectors for this, is any of them correct?

hplus0603

11,916

October 11, 2013 02:08 AM

I checked out the code, and the meaning of the words you ask for are slightly different:

"snap" is the position that is used as a baseline for the vector to move along.

"aim" is the position that the vector aims towards.

"snapTime" is the time at which the snapshot position was established.

So, "aim" is calculated each time you get a new sample, and "snap" is a snapshot of the interpolator output as of the time you received the next packet.

"aim" is calculated as the point extrapolated from the incoming position/velocity to the "target time," which runs ahead of the "current time."

The vector used is always linear, and always goes from the snapshot position (output of interpolator based on old data at the time of receiving the next packet) to the aim position (output of forward extrapolating the new data to the target/aim time.)

It's hard to read your graphic, but if I assume the lines are really velocity vectors, then the vector that looks like what EPIC will do is the "corrected" vector, as it aims towards the same point-in-the-future as the received packet position/velocity aims towards at that same point in time.

enum Bool { True, False, FileNotFound };

hplus0603

11,916

October 11, 2013 02:19 AM

FWIW, I put the code on GitHub now. Only seven years late :-)

enum Bool { True, False, FileNotFound };

Tispe

1,468

Author

October 11, 2013 07:07 AM

Ah, I drew it out again and now it makes sense.

We always move towards the place where we think the position will be next time we recieve a packet so when the packet arrive we will be at that place.

Extrapolator algorithm

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Extrapolator algorithm

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines