Extrapolation breaks collision detection

Question

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

Answer 1

I can't post a comment yet, so I will post this as an answer.

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.

Answer 2

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!