Fast engine.tick() design

Performance Tuning
#21

I’m attempting to get frame interpolation in my game working (just messing around with different types of game loops), and the result is very twitchy entities. I’m not sure if I’m doing this right.

So here it is distilled a bit:

In the update for the entity, it will add its acceleration to its velocity, then its position will be position + velocity.
In the draw for the entity, it will be drawn at position + velocity * interpolation.

The result is an incredibly twitchy entity.

The FPS are generally around 40 and the logic runs at a fixed 25 hz.

Interpolation is calculated like this:


float interpolation = ( now + TIME_BETWEEN_UPDATES - nextUpdate ) /  (float) TIME_BETWEEN_UPDATES ;
view.drawView( interpolation );

Can anyone point me in the right direction?

EDIT:
Let me just post my whole loop:


while( loopIsRunning )
{
    double now = getTimeInSeconds();
		
    int updates = 0;
    while (now >= nextUpdate && updates < MAX_SKIPS)
    {
        update();
        nextUpdate += TIME_BETWEEN_UPDATES;
        updates++;
    }
		
    view.drawView( (getTimeInSeconds() + TIME_BETWEEN_UPDATES - nextUpdate ) / (float)( TIME_BETWEEN_UPDATES ) );
}
#22

maybe you forgot to interpolate with acceleration in your interpolated position :

this :

pos = pos0+v0t+0.5a*t² (t=interpolation time starting at pos0 with velocity v0)

will be different than this :

pos = pos0+v0*t

EDIT :
if you want smooth interpolation (that take care in a certain manner of acceleration) try cubic interpolation

http://freespace.virgin.net/hugo.elias/models/m_inter4.gif

http://freespace.virgin.net/hugo.elias/models/m_inter4b.gif

form : http://freespace.virgin.net/hugo.elias/models/m_perlin.htm

function Cubic_Interpolate(v0, v1, v2, v3,x)
	P = (v3 - v2) - (v0 - v1)
	Q = (v0 - v1) - P
	R = v2 - v0
	S = v1

	return Px3 + Qx2 + Rx + S
  end of function
#23

http://freespace.virgin.net/hugo.elias/models/m_inter4b.gif

here some precision v0,v1,v2 are the last know position of your entity at fixed time step and v3 the futur position that you already know (interpolation vs extrapolation)

lets say v0=pos at t=0
lets say v1=pos at t=40ms
lets say v2=pos at t=80ms
lets say v3=pos at t=120ms

you will be interrested in finding v between v2 & v3 if you want v at time=100 just do

v=Cubic_Interpolate(v0, v1, v2, v3,1.5);

so for x/y:

xi=Cubic_Interpolate(x0, x1, x2, x3,1.5);
yi=Cubic_Interpolate(y0, y1, y2, y3,1.5);

#24

It sounds like you are doing extrapolation. You don’t want to guess where the object will be next frame, then sudden movements can render your guess incorrect and the movement will jump around. I recommend the link I posted earlier.

Snapshot the state of the game before each fixed logic step. Now you have the previousState and the currentState. Since you did a fixed logic step, you may have stepped < the delta. Do alpha = 1 - timeRemaining / fixedTimeStep to get a number between 0 and 1. Interpolate by rendering at the previousState + ((currentState - previousState) * alpha). This introduces one frame of latency, but no guessing is involved.

#25

Here is a game loop:


static final int LOGIC_HZ = 60;
static final int STEP = 1000 / LOGIC_HZ;
static final float PER_SECOND = STEP / 1000f;

int accumulator;
float speed = 1f;
final State previousState = new State();
final State currentState = new State();
final State renderState = new State();

void init () {
	currentState.x = 100;
	currentState.y = 100
	currentState.vx = 42 * PER_SECOND;
	currentState.vy = 42 * PER_SECOND;
	previousState.copy(currentState);
}

void render (int delta) {
	accumulator += delta / speed;
	while (accumulator >= STEP) {
		accumulator -= STEP;
		previousState.copy(currentState);
		currentState.integrate();
	}
	float alpha = accumulator / (float)STEP;
	renderState.interpolate(previousState, currentState, alpha);
	renderState.render();
}

Note the accumulator is int. The fixed steps are 16ms (60hz). Because I know the logic will always happen in 16ms increments, I base all my speeds on this (note I don’t even bother passing the step to integrate()). Eg, if I move an object each logic step by 20 * 0.016, then it will move at a speed of 20 pixels per second. By doing this, in the above code I can use speed = 1 for normal speed or I can do slow (speed < 1) or fast (speed > 1) motion without ruining the simulation.

The state class would look something like:


class State {
	float x, y, vx, vy;
	void integrate () {
		x += vx;
		y += vy;
	}
	void interpolate (State previous, State current, float alpha) {
		x = previous.x * (1 - alpha) + current.x * alpha;
		y = previous.y * (1 - alpha) + current.y * alpha;
	}
	void copy (State other) {
		x = other.x;
		y = other.y;
	}
	void render () {
		...
	}
}
#26

That has one MAJOR flaw. If a ball is moving towards a wall at 100 mph at tick n, and hits the wall one tenth of the way between tick n and n+1, the renderer will interpolate the ball as moving into the wall and back out.

I always use linear interpolation. It’s fast and it works well.
For things like pinball and such where collisions are important, I build a list of all collision points during a tick, then interpolate (linearely) between those when rendering.

#27

I also usually use linear interpolation, but as Demon talk about acceleration cubic interpolation fit better. this is only a flow if you use it “brut force” and only interpolate position without doing anything else (you can handle such case pretty easily),

also in the case your mention (as I understand it)… linear interpolation will just make the ball never touch the wall like if a magnetic field keep it away, it is as false than going throught… :stuck_out_tongue:

#28

here is what I mean :

the advantage of Cubic vs linear is that you can subsampling it into smaller linear part and compute real collision(avoid the MAJOR flaw), subsampling linear will have no effect and will stay as false.

#29

Thanks for all that, guys. I’m definitely going to go with the state approach as mentioned above - I’ve already got previousPosition and position stored, so all I need to add is previousRotation and it’ll work fine. I wasn’t really seeing it as being 1 frame behind which is what my original problem was, I think.

I’ll let you all know how this works.

EDIT - Doing it via state looks great. Very stable and not twitchy. Thanks everyone. I’ll definitely make my loops like this in the future. It’s a lot nicer to not have to worry about a delta variable all the time, too.

#30

I find it much less jarring with linear interpolation than cubic, and the overhead of doing a “clever” (ie world aware) cubic interpolation is probably a LOT bigger than you assume. I’d rather list all collisions within a tick and interpolate linearely between those.

Including acceleration in the interpolation, however, is a very good idea if you manage to do it right, but it’ll only matter in games where things change direction a lot.

#31

But I guess the only reason to not do it state based to avoid that single frame of latency? Seems pretty negligible, but I guess if you’re doing a super-accurate simulation or something it makes sense.