# Extrapolation breaks collision detection

Before applying extrapolation to my sprite's movement, my collision worked perfectly. However, after applying extrapolation to my sprite's movement (to smooth things out), the collision no longer works.

This is how things worked before extrapolation:

However, after I implement my extrapolation, the collision routine breaks. I am assuming this is because it is acting upon the new coordinate that has been produced by the extrapolation routine (which is situated in my render call ).

After I apply my extrapolation

How to correct this behaviour?

I've tried puting an extra collision check just after extrapolation - this does seem to clear up a lot of the problems but I've ruled this out because putting logic into my rendering is out of the question.

I've also tried making a copy of the spritesX position, extrapolating that and drawing using that rather than the original, thus leaving the original intact for the logic to pick up on - this seems a better option, but it still produces some weird effects when colliding with walls. I'm pretty sure this also isn't the correct way to deal with this.

I've found a couple of similar questions on here but the answers haven't helped me.

This is my extrapolation code:

public void onDrawFrame(GL10 gl) {

//Set/Re-set loop back to 0 to start counting again
loops=0;

while(System.currentTimeMillis() > nextGameTick && loops < maxFrameskip){

SceneManager.getInstance().getCurrentScene().updateLogic();
nextGameTick+=skipTicks;
timeCorrection += (1000d/ticksPerSecond) % 1;
nextGameTick+=timeCorrection;
timeCorrection %=1;
loops++;
tics++;

}

extrapolation = (float)(System.currentTimeMillis() + skipTicks - nextGameTick) / (float)skipTicks;

render(extrapolation);
}


Applying extrapolation

            render(float extrapolation){

//This example shows extrapolation for X axis only.  Y position (spriteScreenY is assumed to be valid)
extrapolatedPosX = spriteGridX+(SpriteXVelocity*dt)*extrapolation;
spriteScreenPosX = extrapolationPosX * screenWidth;

drawSprite(spriteScreenX, spriteScreenY);

}


Edit

As I mentioned above, I have tried making a copy of the sprite's coordinates specifically to draw with.... this has it's own problems.

Firstly, regardless of the copying, when the sprite is moving, it's super-smooth, when it stops, it's wobbling slightly left/right - as it's still extrapolating it's position based on the time. Is this normal behavior and can we 'turn it off' when the sprite stops?

I've tried having flags for left / right and only extrapolating if either of these is enabled. I've also tried copying the last and current positions to see if there is any difference. However, as far as collision goes, these don't help.

If the user is pressing say, the right button and the sprite is moving right, when it hits a wall, if the user continues to hold the right button down, the sprite will keep animating to the right, while being stopped by the wall (therefore not actually moving), however because the right flag is still set and also because the collision routine is constantly moving the sprite out of the wall, it still appear to the code (not the player) that the sprite is still moving, and therefore extrapolation continues. So what the player would see, is the sprite 'static' (yes, it's animating, but it's not actually moving across the screen), and every now and then it shakes violently as the extrapolation attempts to do it's thing....... Hope this help

• This will take some digesting to fully understand ('interpolation' has seemingly a dozen different meanings and it's not wholly clear on first glance just what you mean by it here), but my first instinct is 'you should not be doing anything to affect your object's position in your rendering routine'. Your renderer should draw your object at the object's given position, and manipulating the object there is a recipe for trouble, since it inherently couples the renderer to the game's physics. In an ideal world, your renderer should be able to take const pointers to game objects. – Steven Stadnicki May 21 '14 at 16:58
• Hi @StevenStadnicki, many thanks for your comment, there are a multitude of examples showing an interpolation value being passed into the renderer, please see this: mysecretroom.com/www/programming-and-software/… which is from where I adapted my code. My limited understanding is that this interpolates the position between the last and next updates based on the amount of time taken since the last update - I agree it's a bit of a nightmare! I would be grateful if you could propose and alternative that my be easier to work with - cheers :-) – BungleBonce May 21 '14 at 17:06
• Well, I'll say 'just because you can find code for something doesn't make it a best practice'. :-) In this case, though, I suspect that the page you've linked to uses the interpolation value to figure out where to display its objects, but it doesn't actually update the object positions with them; you can do that too, just by having a draw-specific position that's calculated every frame, but keeping that position separate from the object's actual 'physical' position. – Steven Stadnicki May 21 '14 at 17:22
• Hi @StevenStadnicki, as outlined in my question (the paragraph starting "I've also tried making a copy"), I have actually already attempted to use a 'draw only' position :-) Can you propose a method of interpolation where I don't need to make adjustments to the sprite's position within the render routine? Thanks! – BungleBonce May 22 '14 at 1:59
• Looking at your code it looks like you are doing extrapolation instead of interpolation. – Durza007 May 22 '14 at 12:07

If I understand the problem correctly, it goes something like this:

1. first you have a collision
2. then the object's position is corrected (presumably by the collision detection routine)
3. the object's updated position is sent to the render function
4. the render function then updates the object's location using extrapolation
5. the position of the extrapolated object now breaks the collision detection routine

I can think of 3 possible solutions. I will list them in the order that is most desirable to least IMHO.

1. Move the extrapolation out of the render function. Extrapolate the object's position and then test for a collision.
2. or if you want keep the extrapolation in the render function, set a flag to denote a collision had happened. Have the collision detection correct the object's position as you already do, but before you calculate the extrapolation value check the collision flag first. Since the object is already where it needs to be, there is no need to move it.
3. The last possibility, which to me is more of a work-around than a fix would be to overcompensate with the collision detection. After a collision, move the object away from the wall, so that after extrapolation the object is back at the wall.

Example code for #2.

if (collisionHasOccured)
extrpolation = 0.0f;
else
extrapolation = (float)(System.currentTimeMillis() + skipTicks - nextGameTick) / (float)skipTicks;


I think #2 would probably be the quickest and easiest to get up an running, although #1 seems to be a more logically accurate solution. Depending on how you handle your delta time solution #1 could be broken in much the same way by a large delta, in which case you might have to use both #1 and #2 together.

EDIT: I misunderstood your code earlier. The loops is meant to render as fast as possible and update at a set interval. This is why you would be interpolating the sprite position, to handle the case where you are drawing more than updating. However, if the loop falls behind, then you poll on updating until you are caught up or you skipped the max number of frame draws.

That being said, the only problem is that the object is moving after a collision. If there is a collision the object should stop moving in that direction. So, if there is a collision, then set it's speed to 0. This should stop the render function from moving the object any further.

• Hi @Aholio I've tried option 2 and it does work but causes a few glitches maybe I did it wrong, I'll revisit that. However I'm very interested in option 1 although I can find no info on how to do this. How can I extrapolate say in my logic routine? BTW my delta is fixed so is 1/60 or 0.01667 (rather this is the figure I use to integrate although the amount of time each iteration of my game takes can obviously vary depending on what is going on but should never really take more than 0.01667) so any help on that would be great thanks. – BungleBonce Jun 3 '14 at 7:28
• Perhaps I don't fully understand what you are doing. Something that seems a bit odd to me is that you are not only doing position movements in your draw function; you are also doing time calculations. Is this done for every object? The correct order should be: time calculation done in the game loop code. The game loop passes the delta into an update(dt) function. Update(dt) will update all game objects. It should handle any movement, extrapolation, and collision detection. After update() returns to game loop, it then calls a render() function which draws all the freshly updated game objects. – Aholio Jun 3 '14 at 13:56
• Hmmmmm at present my update function does everything. Does the movement (by movement I mean calculates new position of sprites - this is calculated from my delta time). The only thing I'm doing in my render function (apart from actually drawing) is extrapolating the 'new' position, but of course this uses time as it has to take into account the time from the last logic update to the render call. That's my understanding anyway :-) How would you do this? I don't understand how to use extrapolation within just the logic update. Thanks! – BungleBonce Jun 3 '14 at 14:43
• Updated my answer. Hope that helps – Aholio Jun 4 '14 at 5:35
• Thanks, see in my original Q "when it stops, it's wobbling slightly left/right" - so even if I stop my sprite, the extrapolation still keeps the sprite 'moving' (wobbling) - this happens because I'm not using the sprite's old and current positions to work out my extrapolation, therefore even if the sprite is static, it still has this wobbling effect based on the 'extrapolation' value which is worked out each frame iteration. I've even tried saying 'if old and current pos are the same then don't extrapolate' but this still doesn't seem to work, I'll go back and take another look though! – BungleBonce Jun 6 '14 at 7:32

It looks like you need to separate rendering and updating of physics entirely. Usually the underlying simulation will run at discrete time-steps, and the frequency will never change. For example, you could simulate the movement of your ball every 1/60th of a second, and that's it.

In order to allow for a variable framerate the rendering code should operate on a variable frequency, but any simulation should still be at a fixed time-step. This lets the graphics read memory from the simulation as read-only, and lets you set up interpolation instead of extrapolation.

Since extrapolation is trying to predict where future values are going to be, sudden changes in movement can give you huge extrapolation errors. It is better to instead render your scene about a frame behind simulation and interpolate between discrete known positions.

If you want to see some details of implementation I've already written a short section about this topic in an article here. Please see the section called "Timestepping".

Here's the important psuedo code from the article:

const float fps = 100
const float dt = 1 / fps
float accumulator = 0

// In units seconds
float frameStart = GetCurrentTime( )

// main loop
while(true)
const float currentTime = GetCurrentTime( )

// Store the time elapsed since the last frame began
accumulator += currentTime - frameStart( )

// Record the starting of this frame
frameStart = currentTime

// Avoid spiral of death and clamp dt, thus clamping
// how many times the UpdatePhysics can be called in
// a single game loop.
if(accumulator > 0.2f)
accumulator = 0.2f

while(accumulator > dt)
UpdatePhysics( dt )
accumulator -= dt

const float alpha = accumulator / dt;

RenderGame( alpha )

void RenderGame( float alpha )
for shape in game do
// calculate an interpolated transform for rendering
Transform i = shape.previous * alpha + shape.current * (1.0f - alpha)
shape.previous = shape.current
shape.Render( i )


The RenderGame function is of most interest. The idea is to use interpolation between discrete simulation positions. The rendering code can make it's own copies of the simulation read-only data, and use a temporary interpolated value to render. This will give you very smooth movement without any silly issues like what you seem to be having!