Android Game-Loop (rendering & logic removed, but still 'skipping frames')

Question

Overview

Guys really hoping for some help here. My game loop is based on code from Fix Your Timestep!.

I've read the article more than a few times, but I can't quite work out what exactly is supposed to be going on within the loop.

I'm running my code on a Nexus 10 tablet which has VSync set to 60fps.

Playing catch up

When I run my code, I'm getting caught quite often in the while loop, ie it runs my logic more than once - so runs logic twice in a row before rendering).

With my understanding of the loop, this should happen when rending takes too long to fit into the time slice (which is 16.66666666666667ms).

So, maybe in 'normal circumstances', I would expect this to happen occasionally).

However, I've tried removing all rendering and logic updating and just running a skeleton loop and I'm still getting caught regularly and constantly within the 'while-loop'.

Therefore, when I'm running my game (with rendering and logic), I'm getting a lot of stuttering because I know the loop is going to skip frames. The logic updates are however being capped at 60 which is exactly what I want.

Obviously whether or not my rendering or physics update could be more efficient is not the issue here and is a question for another day as I've already removed that from the equation.

I can smooth things out somewhat with interpolation and it really does make a difference, however, it's not as smooth as some of the games I download from the Play Store and I really need to make it better.

So, what am I missing or not understanding? I would think it should (certainly with no rendering or logic updating to create a bottleneck):

• Enter the while-loop
• Exit the while-loop
• Wait for next VSync
• And repeat

Here is the loop I'm testing with:

@Override
public void onDrawFrame(GL10 gl) {

    newTime = System.currentTimeMillis()*0.001;
    frameTime = newTime - currentTime; //Amount of time this entire frame took
            if ( frameTime > (0.25))
                frameTime = (0.25);

            currentTime = newTime;
            accumulator += frameTime;

            //Update logic
            while (accumulator >= dt){
//              saveGameState();  //Removed for testing
//              updateLogic(dt);  //Removed for testing
                accumulator -= dt;
            }

            //Get the amount to interpolate by
//              interpolation = (float) (accumulator / dt);  //Removed for testing
//              render(interpolate);                         //Removed for testing

}  

Answer 1

Fix your Timestep does not deal with graphical stuttering even in a correct implementation. Assume a working implementation where the only game logic is physics. If physics is at 50Hz, and render can run at 200Hz, you're only going to see 50Hz unless you implement visual interpolation. Likewise, if your framerate varies, expect stuttering.

The rest of this answer is largely a re-explanation of the above, with some extra points.

Possibility 1: Cost too high - missing updates

If you're often missing frames per se, i.e. not even getting a single frame in a given update then your per-frame logic is too costly and you need to reduce it, e.g. have fewer physics bodies active.

Possibility 2: Cost reasonably low against a fluctuating frame period

I'm getting caught quite often in the while loop, i.e. it runs my logic more than once

Therein lies your problem. When the system is running your code on true fixed-rate vsync, you expect the same number of logic updates per display update. 1 or 10, but it should always be same - if it is, no stuttering. Android frame rate is quite steady, on my devices it's just under 60fps for a light NDK/OpenGL app, but it does fluctuate. Read on.

There's quite a difference in expectations between setups where you

• have direct control over the core (while) loop, which you can run at the highest rate possible given the ops coded there in C/C++ code, and where if you take too long to process / render, that is entirely your own concern - but typically you have many render frames per logic frame;
• have a (relatively) fixed frame rate dictated to you by the system, which calls your update (onDrawFrame() in this case) as a callback e.g. browser JS, Flash, or in this case, Android - here you have one or more logic frames per render frame (see the inversion from the above case?), and you absolutely must complete at least one logic update per frame period (dictated by the system) for things to proceed sanely - this which is fundamentally different.

From early experiences with this, I believe Gaffer's concept (in that article) is geared to the former, i.e. primarily AAA desktop and console games written in C++ where the core loop runs as fast as possible and often without any external timing mechanism (ever seen those Quake demos where they're getting like 400fps?). Let's look at some examples to see what can happen with the latter.

Example A - the display frequency is relatively steady, around 16.7ms period, give or take a millsecond or 2, and for maybe 90% of frames, it is spot on at 16.7. Let's say your logic takes 9ms. Most frames, then, you'll manage just one update. But due to unforeseen delays in the Android operating system, the period on which onDrawFrame() fluctuates and sometimes jumps up to 18+ ms every so often, say 5% of the time, and then you are going to end up doing 2 logic updates because you have enough time do so instead of just 1...but the actual display frequency hasn't changed so much that it would have been apparent using a one-logic-update-per-display-update approach anyway, so what do you see? Stuttering, of course.

Example B - Your logic processing takes about 16.3ms on average. If at any stage it jumps up by say 0.5ms, and exceeds the point by which the OS intends to render, you'll also see stuttering, the severity of which depends on the frequency with which you exceed that soft limit of around 16.7ms.

Crucially, It's not that the accumulator approach isn't a good one - it's excellent, in fact, and is really the only sane way to handle the fixed timestep required for stable physics without frequent network desync (after all, you cannot just drop the accumulated time, and every client is going to accumulate differently). But if you don't have direct control over the timing loop, you can easily run into problems you didn't expect. And you must appreciate that when the accumulator does build up enough time to run more than one update at a time (the exception rather than the rule), then it may well lead to a jarring visual result. So you will need to do graphical interpolation.

In conclusion

You need interpolation if you want to accurately reflect your maximum frame rate as against your slower logic update rate, and with naive interpolation you may still perceive unwanted variances in frame rate due to occasional double-runs of physics and game logic. Admittedly I'm not an expert on interpolation / extrapolation algorithms but it stands to reason that the more frames you use to calculate averages over, the smoother it's going to look, though too many frames has drawbacks.

When there is a mechanism in place dictating your timing, it's best to just stick with that and not try to work around it - such loops (as opposed to what Gaffer describes) are intended for one update per frame. If there are good solutions for this type of scenario, I'd love to hear them.

However... I've not used Android's Java interface for game dev (only NDK), but what I would suggest (if possible?) is to run a while loop that has nothing to do with onDrawFrame() but rather just sits in main doing its game / physics logic things, while onDrawFrame() purely handles rendering at the appropriate time. I don't know how that will sync up or even if it will work at all.

For Android NDK as with most native development, you have direct control over the while loop off which everything runs - game logic and render calls - so the problem there is already solved.

Answer 2

The purpose of the fix step time loop is to always update at a fixed time interval. This is important in things like collision which that big delta times could cause objects to phase through another. Updating multiple times between rendering is the desired behaviour. Your loop looks fine but the problem is that the device (or other part of your code) is not fast enough to keep your game running at 60FPS. Perhaps the problem is in the Vsync. See this link.

Answer 3

[I'm posting this as an answer because I don't have enough reputation to post comments.]

I wanted to add a comment to Arcane Engineer's answer since it is fundamentally wrong because it is based on a misunderstanding on what Gaffer's "Fix your timestep" tries to communicate.

The design suggested by Gaffer disconnects the rendering from the physics (ie updating), so it is not relying on having the highest possible rate of rendering. Nor is it relying on a vsync fixed rate of rendering. The design described by Gaffer allows the rendering to run at any rate (max speed, fixed vsync, or even slower than the physics updates) independently of the updating which in contrast must run at an absolutely fixed rate to achieve the desired determinism of the model progression.

Now to the original question. There is a bit of information missing, namely the value of the delta time (dt). If dt is set to eg. 0.01 as it is in the Gaffer article, then staying in the while loop for two updates is expected behaviour - at least about every other pass through the rendering loop.

Answer 4

I would personally never make my control loop within the render method (here onDraw). However, to prove to Arcane Engineer that he completely misunderstood the functionality of the Fixed Timestep algorithm, and to show the original poster (and any other interested parties) that the algorithm itself works exactly as intended I made this implementation exactly like the original poster intended.

Contrary to the claims of Arcane Engineer the purpose of the algorithm IS to make sure that the updates to the model is running with completely fixed increments even when controlled by a fluctuating timer.

I made a very simple implementation the Gaffer algorithm in Android - as requested - to give you an opportunity to... what was the phrase? "explain to your children and grandchildren the day when you were knocked to the floor in disbelief" :-)

This implementation updates the display about 60 times per second. And it updates the model about 100 times per second. But the delta time (dt) can be set to any value - for instance 0.04 to make it run about 25 times per second, but still the animation will be smooth because of the interpolation.

Activity class

import android.app.Activity;
import android.os.Bundle;

public class MainActivity extends Activity {

    private FixedTimestepView view;

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        view = new FixedTimestepView(this);
        setContentView(view);
        view.run();
    }

}

The View

import android.content.Context;
import android.graphics.Canvas;
import android.graphics.Color;
import android.graphics.Paint;
import android.view.View;

public class FixedTimestepView extends View {
// Render frequency
private static final int FPS = 60;
private int worldWidth;
private int worldHeight;

// Gaffer timestep control
private double t = 0.0;
private double dt = 0.01;   // Fixed update speed
private double currentTime;
private double accumulator = 0.0;

// States
private FixedTimestepState mPrevState;
private FixedTimestepState mCurState;
private FixedTimestepState state;

private Paint p = new Paint();

public FixedTimestepView(Context context) {
    super(context);
}

@Override
public void onSizeChanged(int newX, int newY, int oldX, int oldY) {
    super.onSizeChanged(newX, newY, oldX, oldY);
    worldWidth = this.getWidth();
    worldHeight = this.getHeight();
}

public void run() {
    Thread animationThread = new Thread() {
        @Override
        public void run() {
            final long millis = 1000 / FPS;
            final int nanos = (int) ((1000.0f / FPS - millis) * 1000000);
            init();

            while (true) {
                postInvalidate();
                try {
                    Thread.sleep(millis, nanos);
                } catch (InterruptedException ex) {
                }
            }
        }
    };
    animationThread.start();
}

public void init() {
    p.setColor(Color.RED);
    state = new FixedTimestepState();
    mCurState = new FixedTimestepState(50, 50, -100, 65, 20);
    mPrevState = new FixedTimestepState();
    currentTime = System.currentTimeMillis() / 1000.0d;
}

@Override
public void onDraw(Canvas g) {
    // Implementing the Gaffer algorithm directly in the onDraw method

    double newTime = System.currentTimeMillis() / 1000.0d;
    double frameTime = newTime - currentTime;
    if (frameTime > 0.25)
        frameTime = 0.25;
    currentTime = newTime;

    accumulator += frameTime;

    while (accumulator >= dt) {
        mPrevState.set(mCurState);
        integrate(mCurState, t, dt);
        t += dt;
        accumulator -= dt;
    }

    final double alpha = accumulator / dt;

    state.interpolate(mCurState, mPrevState, alpha);

    render(g, state);

}

public void integrate(FixedTimestepState state, double totalTime, double deltaTime) {
    state.update(deltaTime);
    state.handleCollision(worldWidth, worldHeight);
}

public void render(Canvas g, FixedTimestepState interpolatedState) {
    g.drawColor(Color.BLACK);

    final int left = (int)interpolatedState.x;
    final int top = (int)interpolatedState.y;
    final int right = left + (int)interpolatedState.size;
    final int bottom = top + (int)interpolatedState.size;
    g.drawRect(left, top, right, bottom, p);
}

}

The State

public class FixedTimestepState {
public float x;
public float y;
public float vx;
public float vy;
public int size;

public FixedTimestepState() {
    this(0.0f, 0.0f, 0.0f, 0.0f, 0);
}

public FixedTimestepState(float x, float y, float vx, float vy, int size) {
    set(x, y, vx, vy, size);
}

public void set(float x, float y, float vx, float vy, int size) {
    this.x = x;
    this.y = y;
    this.vx = vx;
    this.vy = vy;
    this.size = size;
}

public void set(FixedTimestepState state) {
    x = state.x;
    y = state.y;
    vx = state.vx;
    vy = state.vy;
    size = state.size;
}

public void interpolate(FixedTimestepState currentState, FixedTimestepState previousState, double alpha) {
    x = (float)(currentState.x * alpha + previousState.x * (1.0 - alpha));
    y = (float)(currentState.y * alpha + previousState.y * (1.0 - alpha));
    vx = (float)(currentState.vx * alpha + previousState.vx * (1.0 - alpha));
    vy = (float)(currentState.vy * alpha + previousState.vy * (1.0 - alpha));
    size = currentState.size;
}

public void update(double deltaTime) {
    x += vx * deltaTime;
    y += vy * deltaTime;
}

public void handleCollision(int worldWidth, int worldHeight) {
    if (x < 0 && vx < 0) {
        vx *= -1;
        x = -x;
    } else if (x + size > worldWidth && vx > 0) {
        vx *= -1;
        x -= (x + size - worldWidth) * 2;
    }

    if (y < 0 && vy < 0) {
        vy *= -1;
        y = -y;
    } else if (y + size > worldHeight && vy > 0) {
        vy *= -1;
        y -= (y + size - worldHeight) * 2;
    }
}

}