Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm having trouble understanding when to extrapolate and when to interpolate. In gaffer on games, he said to interpolate but then in another article it recommended extrapolating the player. So my question is when is it better to extrapolate and when is it better to interpolate?

share|improve this question
21  
There are two kinds of people. Those who can extrapolate from incomplete data – Almo Mar 11 at 16:41
2  
@Almo and what's the other kind? Please tell me, I must know! – DJ McMayhem Mar 11 at 18:34
4  
@DJMcMayhem ... and those who enjoy eating fish fingers. – immibis Mar 12 at 1:01
4  
I don't understand the question. Can you explain one way to "interpolate" the points {(1, a), (2, b)} to predict c in (3, c)? And how would you extrapolate it? – Mehrdad Mar 12 at 7:37

You interpolate when you know the 'before' and 'after' values.

For example: in a point-and-click game, player is currently at position X, and from his interface, he clicks on spot Y. You must interpolate the displacement between X and Y because you know the two values.

You extrapolate when you guess what's going to be future value, based on what you already know.

For example: in a first-person-shooter game, player is at position X and he's been depressing the UP arrow on his keyboard for the last second, you can suppose that he'll be doing this again for the next second because that's basically the most frequent behaviour in your game; so you extrapolate the position that he'll be next frame. The server sends it to the other game clients, this accounts for the delay in the transmission from the server to the players.

Extrapolation is used mainly for movement prediction. It is not needed by the game server, but the game clients need it to display a somewhat realistic and current vision of the state of the game in order to give a smooth visual experience to the players.

share|improve this answer
    
I understand that part but what I don't understand is when i should use each one. Like for example, if I interpolate a player, there will be a delay for him to actually see movement but if I extrapolate it will be more instantaneous but it may not be accurate and will need to be corrected. Is it usually more desirable to have the instantaneous movement from extrapolating or the more consistent movement from interpolating? – J leong Mar 10 at 18:05
    
@Jleong You want the game presented as smooth as possible to the users. You interpolate the current state of the game, and you extrapolate how it will be in a couple of frame. You send the extrapolated values to the other players to account for the delay in the network transmission. If you were to send the interpolated values, the game would seem to lag and it would not be fun. (I edited my answer. I hope it clears it up a bit more.) – Alexandre Vaillancourt Mar 10 at 18:14
    
oh ok so extrapolating is used when you want it the client to predict what is going to happen? If so then what is the point of interpolation if you can always extrapolate to keep the game close to real time? so for like a FPS, would the player be extrapolated and the other players be interpolated? – J leong Mar 10 at 18:14
    
Generally, the server does everything: it interpolates on what it knows, and based on that, it extrapolates the values and send these to the clients so they arrive in time to be presented to the players. In a FPS, the interpolation is used to display things like projectiles, AI, and such. When performing Frame B (coming from Frame A) it will interpolate values for the state of Frame B; it can also start predicting Frame C by interpolation of the known values, but it will have to extrapolate values it doesn't know about (player inputs). It will then send the "future" state to the client. – Alexandre Vaillancourt Mar 10 at 18:26
    
@Jleong Without thinking about the difference between client and server, I can use interpolation to derive a position somewhere between two known points (for things like checking a collision that may have happened between frames), or further, take that dataset and derive things like velocity/trajectory and acceleration, given a set of points, and given the last known velocity/acceleration/trajectory, I can extrapolate where those objects may be, in the future, assuming a consistent timeframe. For server-client communication, the "optimistic" extrapolated position is used. – Norguard Mar 12 at 20:34

Interpolation is done when you have both a start and end value, and you want to estimate what happens between this start and end value. An example would be to move a player from Position A to Position B in a fluid motion.

Extrapolation, is done when you have a start value, but do not yet have data for the end. You can then extrapolate based on what data you have. For example, based on a player's previous movements, you can determine where he is probably going to be in the next frame.

share|improve this answer

Always interpolate when you can.

When you don't have enough information to interpolate then you need to extrapolate.

It really is that simple, don't over-think it :)

To explain a bit more:

In general interpolation is better because interpolation is always right. To extrapolate you have to guess. Then you have to deal with what happens when you guess wrong, which leads to rubber banding or popping and all sorts of systems to deal with handling all of that and disguising it.

What happens if you extrapolated a bat position and showed it going to the right place and bouncing the ball, then realize afterwards that you were wrong and it didn't bounce the ball? There is no good way to handle that scenario.

share|improve this answer
    
oh ok so in pong, the user's paddle is predicted and the ball and other paddle are interpolated? – J leong Mar 11 at 18:07
    
That entirely depends on how you implement it. See my edit for more information. – Tim B Mar 11 at 19:00

You interpolate to find states between known values, and you extrapolate to find future states.

Think of the problem in terms of state variables, like positions and velocities. In the best of all scenarios, every computer which needs to work with state has access to the state data for the time they want to work on. For example, a collision algorithm to see whether laser-rifle shot X interesets player A's head, the best of all cases is when the algorithm knows the exact position of every object at the time the laser was fired.

In the real world, we are not always so lucky. Sometimes the truth information we receive is more sparse. For example, if player A is a remote player on another computer, you may not know exactly where they're going when you fire the laser and need to calculate the shot. In this case, you need to create an estimator for A's position, typically with interpolation or extrapolation.

The difference between the two is whether you have data that is bounded on both sides, or only one side. Let's say that Player A has already announced their truth position for t=0 and t=1. Player B shoots a laser at t =0.5. In many situations Player A's announcement of their position at t=1 can occur before Player B pulls the trigger. Why? In many games, the responsiveness of the controls is less than perfectly instantaneous. In a racing simulation, much of the player's position is bounded by the physics of a moving vehicle. You may choose to announce a "future position" because you know you really can't steer all that much in a short period. If you have information in the future, you can interpolate between the two values.

What if you aren't lucky enough to have a t=1 value? What if Player A wasn't in a position to announce their future location, and you're stuck deciding whether you hit or missed with only the information from t=0? In this case you have to extrapolate. In extrapolation, you use what you know about the motion to extend beyond any data you have. You might know that Player A has a certain velocity, so presume that if you multiply that by time, you can get a position at each time.

The difference is in the behaviors. Interpolation requires you to have an upper and a lower bound, which you do not always have. However, in nearly all situations it has vastly better results than extrapolation. Extrapolation can easily lead to unrealistic movements. Consider the case of a player who is sidestepping left and right to avoid being shot while advancing. At any given point, their velocity is along a diagonal, so if you extrapolate, the player may appear to run off to the side when, in fact, they never do. If you only do interpolation, the values tend not to stray outside realistic values.

Interpolation and extrapolation are two extremes in the world of filtering. There are many many many many many filters out there for handling data like this which mix and match properties between interpolation and extrapolation. Accordingly, don't be surprised if you see algorithms that are not clearly interpolation or clearly extrapolation. Those two are just the tip of the ice berg.

share|improve this answer

Interpolation is using known data to calculate a datum within the bounds of the data set (inter- being the 'inside' prefix). Extrapolation is calculating a datum outside the bounds of the existing data (extra- being the 'outside' prefix). Both are used to synthesize additional data, with the exact method of calculation defining the expected reliability of the data generated.

Or to put it into a very simple diagram:

A - - - - - B - - - - - C - - - - - D

Given the data points A and C you can interpolate B and extrapolate D.


The accuracy of an interpolation or an extrapolation is entirely dependent on how well you can account for every variable in the calculation. If you know all of the variables and have an equation that accounts for all of them, then you can interpolate or extrapolate with equal ease.

For game mechanics the limiting factors will be the points at which the variables are influenced in unpredictable ways, either by the player or some random or pseudo-random element.

For example, the movement of a ball in Breakout (in its simplest form) can be extrapolated all the way up to the point where it could potentially interact with the player's paddle. All of the variables can be accounted for up to that point and so you can precisely model the actions of the ball. When it reaches the point where player interaction is possible then there are a number of possible outcomes and no way to accurately model which of those is going to be the case until it actually happens. This is the predictive limit of the game physics model.

Interpolation is simpler in games because you are working with known points and don't have to wonder if the conditions will change. Further you have full control over the variables involved and can use any rules you define to determine the path of an object. The more complex the rules the harder it may be to interpolate.

For object movement with simple collisions in a gravity-free playing space (like Breakout or Pong) the mechanism for interpolation along a line on the path is a simple linear interpolation of the points, and the same calculation can be used to extrapolate the line to test for future collisions. Once a collision is detected you can extrapolate the effect of that collision on the objects involved.

share|improve this answer
    
This is exactly the difference between the words. The reason we have different words for guessing B and D when all we have is A and C is because guessing B correctly is so much easier than guessing D correctly. Artillery experts call interpolating backeting. They get two marking rounds either side of you, you're dead if you don't move. Extrapolating is what you're trying to do when you play the stock market after looking at the stock price charts. Extrapolating is hard. – CandiedOrange Mar 13 at 13:41
    
@CandiedOrange Extrapolating complex systems is hard, but so is interpolating. It depends on the quality of your data points and how predictable the system is. If you can derive an accurate equation that describes the system then you can interpolate or extrapolate with accuracy - lines are simple to extrapolate, curves can be, stock markets not so much. – Corey Mar 13 at 23:26
    
By hard I mean that interpolating gives you the fundamental theorem of calculus to fall back on. Extrapolating doesn't. A and C tell you B is somewhere that made C possible given A. Asking for D is asking to predict the future. For all you know C is where the player died. Which one is more reliable and acceptable: Interpolation or extrapolation? why-is-extrapolation-riskier-than-interpolation – CandiedOrange Mar 13 at 23:53
    
@CandiedOrange Sure, extrapolation is limited to the degree at which you can control and predict all of the relevant variables. So is interpolation. Given two positions that a player has occupied in the past you can't necessarily accurately interpolate a mid-point since the player may have varied off a direct or optimal path. Both methods are limited. – Corey Mar 14 at 0:00
    
Sure, both are limited. But one destroys careers more often than the other. Guess which. My claim isn't that interpolating is perfect. It's that seeing them as having the same predictive power is dangerous. – CandiedOrange Mar 14 at 0:05

The short answer: you interpolate when you have to estimate a value between two known values (i.e.: in one hour the value is 1, in 3 hours it's three, to interpolate the value at 2 at the most likely value 2, with the given values). Extrapolate is when the unknown is outside what you know, so when 1 and 2 are known you can make an educated guess on 3.

Interpolate: in between Extrapolate: outside

The long answers here are most likely way more accurate and scientifically correct, but I hope my simple explanation can make sense to some

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.