android game loop vs updating in the rendering thread

Question

I'm making an android game and am currently not getting the performance I'd like. I have a game loop in its own thread which updates an object's position. The rendering thread will traverse these objects and draw them. The current behavior is what seems like choppy/uneven movement. What I cannot explain is that before I put the update logic in its own thread, I had it in the onDrawFrame method, right before the gl calls. In that case, the animation was perfectly smooth, it only becomes choppy/uneven specifically when I try to throttle my update loop via Thread.sleep. Even when I allow the update thread to go berserk (no sleep), the animation is smooth, only when Thread.sleep is involved does it affect the quality of the animation.

I've created a skeleton project to see if I could recreate the issue, below are the update loop and the onDrawFrame method in the renderer: Update Loop

    @Override
public void run() 
{
    while(gameOn) 
    {
        long currentRun = SystemClock.uptimeMillis();
        if(lastRun == 0)
        {
            lastRun = currentRun - 16;
        }
        long delta = currentRun - lastRun;
        lastRun = currentRun;

        posY += moveY*delta/20.0;

        GlobalObjects.ypos = posY;

        long rightNow = SystemClock.uptimeMillis();
        if(rightNow - currentRun < 16)
        {
            try {
                Thread.sleep(16 - (rightNow - currentRun));
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
}

And here is my onDrawFrame method:

        @Override
public void onDrawFrame(GL10 gl) {
    gl.glClearColor(1f, 1f, 0, 0);
    gl.glClear(GL10.GL_COLOR_BUFFER_BIT |
            GL10.GL_DEPTH_BUFFER_BIT);

    gl.glLoadIdentity();

    gl.glBindTexture(GL10.GL_TEXTURE_2D, textures[0]);
    gl.glTranslatef(transX, GlobalObjects.ypos, transZ);
    //gl.glRotatef(45, 0, 0, 1);
    //gl.glColor4f(0, 1, 0, 0);

    gl.glEnableClientState(GL10.GL_VERTEX_ARRAY);
    gl.glEnableClientState(GL10.GL_TEXTURE_COORD_ARRAY);

    gl.glVertexPointer(3,  GL10.GL_FLOAT, 0, vertexBuffer);
    gl.glTexCoordPointer(2, GL10.GL_FLOAT, 0, uvBuffer);

    gl.glDrawElements(GL10.GL_TRIANGLES, drawOrder.length,
              GL10.GL_UNSIGNED_SHORT, indiceBuffer);

    gl.glDisableClientState(GL10.GL_VERTEX_ARRAY);
    gl.glDisableClientState(GL10.GL_TEXTURE_COORD_ARRAY);
}

I've looked through replica island's source and he's doing his update logic in a separate thread, as well as throttling it with Thread.sleep, but his game looks very smooth. Does anyone have any ideas or has anyone experienced what I'm describing?

---EDIT: 1/25/13---
I've had some time to think and have smoothed out this game engine considerably. How I managed this might be blasphemous or insulting to actual game programmers, so please feel free to correct any of these ideas.

The basic idea is to keep a pattern of update, draw... update, draw... while keeping the time delta relatively the same (often out of your control). My first course of action was to synchronize my renderer in such a way that it only drew after being notified it was allowed to do so. This looks something like this:

public void onDrawFrame(GL10 gl10) {
        synchronized(drawLock)
    {
        while(!GlobalGameObjects.getInstance().isUpdateHappened())
        {
            try
            {
                Log.d("test1", "draw locking");
                drawLock.wait();
            } 
            catch (InterruptedException e) 
            {
                e.printStackTrace();
            }
        }
    }

When I finish my update logic, I call drawLock.notify(), releasing the rendering thread to draw what I just updated. The purpose of this is to help establish the pattern of update, draw... update, draw... etc.

Once I implemented that, it was considerably smoother, although I was still experiencing occasional jumps in movement. After some testing, I saw that I had multiple updates occurring between calls of ondrawFrame. This was causing one frame to show the result of two (or more) updates, a larger jump than normal.

What I did to resolve this was to cap the time delta to some value, say 18ms, between two onDrawFrame calls and store the extra time in a remainder. This remainder would be distributed to subsequent time deltas over the next few updates if they could handle it. This idea prevents all sudden long jumps, essentially smoothing a time spike out over multiple frames. Doing this gave me great results.

The downside to this approach is that for a little time, the position of objects will not be accurate with time, and will actually speed up to make up for that difference. But it's smoother and change in speed is not very noticeable.

Finally, I decided to rewrite my engine with the two above ideas in mind, rather than patching up the engine I had originally made. I made some optimizations for the thread synchronization that perhaps someone could comment on.

My current threads interact like this:
-Update thread updates the current buffer (double buffer system in order to update and draw simultaneously) and will then give this buffer to the renderer if the previous frame has been drawn.
-If the previous frame has not yet draw, or is drawing, the update thread will wait until the render thread notifies it that it has drawn.
-Render thread waits until notified by update thread that an update has occurred.
-When the render thread draws, it sets a "last drawn variable" indicating which of the two buffers it last drew and also notifies the update thread if it was waiting on the previous buffer to be drawn.

That may be a little convoluted, but what that's doing is allowing for the advantages of multithreading, in that it can perform the update for frame n while frame n-1 is drawing while also preventing multiple update iterations per frame if the renderer is taking a long time. To further explain, this multiple-update scenario is handled by the update thread locking if it detects that the lastDrawn buffer is equal to the one which was just updated. If they are equal, this indicates to the update thread that the frame before has not yet been drawn.

So far I'm getting good results. Let me know if anyone has any comments, would be happy to hear your thoughts on anything I'm doing, right or wrong.

Thanks

Doenitz

Answer 1

(The answer from Blackhex raised some interesting points, but I can't cram all this into a comment.)

Having two threads operating asynchronously is bound to lead to issues like this. Look at it this way: the event that drives animation is the hardware "vsync" signal, i.e. the point at which the Android surface compositor provides a new screen full of data to the display hardware. You want to have a new frame of data whenever vsync arrives. If you don't have new data, the game looks choppy. If you generated 3 frames of data in that period, two will be ignored, and you're just wasting battery life.

(Running a CPU full out may also cause the device to heat up, which can lead to thermal throttling, which slows everything in the system down... and can make your animation choppy.)

The easiest way to stay in sync with the display is to perform all of your state updates in onDrawFrame(). If it sometimes takes longer than one frame to perform your state updates and render the frame, then you're going to look bad, and need to modify your approach. Simply shifting all game state updates to a second core isn't going to help as much as you might like -- if core #1 is the renderer thread, and core #2 is the game state update thread, then core #1 is going to sit idle while core #2 updates the state, after which core #1 will resume to do the actual rendering while core #2 sits idle, and it's going to take just as long. To actually increase the amount of computation you can do per frame, you'd need to have two (or more) cores working simultaneously, which raises some interesting synchronization issues depending on how you define your division of labor (see http://developer.android.com/training/articles/smp.html if you want to go down that road).

Attempting to use Thread.sleep() to manage the frame rate generally ends badly. You can't know how long the period between vsync is, or how long until the next one arrives. It's different for every device, and on some devices it may be variable. You essentially end up with two clocks -- vsync and sleep -- beating against each other, and the result is choppy animation. On top of that, Thread.sleep() doesn't make any specific guarantees about accuracy or minimum sleep duration.

I haven't really gone through the Replica Island sources, but in GameRenderer.onDrawFrame() you can see the interaction between their game state thread (which creates a list of objects to draw) and the GL renderer thread (which just draws the list). In their model, the game state only updates as needed, and if nothing has changed it just re-draws the previous draw list. This model works well for an event-driven game, i.e. where the contents on screen update when something happens (you hit a key, a timer fires, etc). When an event occurs, they can do a minimal state update and adjust the draw list as appropriate.

Viewed another way, the render thread and the game state work in parallel because they're not rigidly tied together. The game state just runs around updating things as needed, and the render thread locks it down every vsync and draws whatever it finds. So long as neither side keeps anything locked up for too long, they don't visibly interfere. The only interesting shared state is the draw list, guarded with a mutex, so their multi-core issues are minimized.

For Android Breakout ( http://code.google.com/p/android-breakout/ ), the game has a ball bouncing around, in continuous motion. There we want to update our state as frequently as the display allows us to, so we drive the state change off of vsync, using a time delta from the previous frame to determine how far things have advanced. The per-frame computation is small, and the rendering is pretty trivial for a modern GL device, so it all fits easily in 1/60th of a second. If the display updated much faster (240Hz) we might occasionally drop frames (again, unlikely to be noticed) and we'd be burning 4x as much CPU on frame updates (which is unfortunate).

If for some reason one of these games missed a vsync, the player may or may not notice. The state advances by elapsed time, not a pre-set notion of a fixed-duration "frame", so e.g. the ball will either move 1 unit on each of two consecutive frames, or 2 units on one frame. Depending on the frame rate and the responsiveness of the display, this may not be visible. (This is a key design issue, and one that can mess with your head if you envisioned your game state in terms of "ticks".)

Both of these are valid approaches. The key is to draw the current state whenever onDrawFrame is called, and to update state as infrequently as possible.

Note for anyone else who happens to read this: don't use System.currentTimeMillis(). The example in the question used SystemClock.uptimeMillis(), which is based on the monotonic clock rather than wall-clock time. That, or System.nanoTime(), are better choices. (I'm on a minor crusade against currentTimeMillis, which on a mobile device could suddenly jump forward or backward.)

Update: I wrote an even longer answer to a similar question.

Update 2: I wrote an even longer longer answer about the general problem (see Appendix A).

Reeta

Thanks for the thoughtful answer. I've had a few weeks since I wrote the original post to play around and delve deeper into the issue. I've found that synching the renderer to only draw after an update, in that it will wait (as happens in Replica) until the update thread notifies it made a huge difference. – Doenitz

After I implemented that, I still noticed jumps in my movement. What was happening here was two updates would sometimes occur between a set of draws. This essentially moved the ball twice as far as in other frames. I took the approach to cap the time delta between two renders and put the extra time into a remainder which would then distribute itself to subsequent update iterations. This smoothed things out considerably. The downside of this is the ball is technically speeding up to make up for lost time. But it's hardly noticeable and doesn't outweigh the smoothness.Is this a typical approach? – Doenitz

Re: above + updates to question. Remember that you can't know ahead of time how long the delay between screen redraws is -- on some devices it could even change mid-game -- so trying to think in terms of fixed-length time frames is going to lead to trouble (missing frames or double-step on frames). The frame rate should be fairly constant short-term though, so you can base the amount you advance stuff for the next frame on the elapsed time between onDrawFrame calls; over time, it should look smooth. (This is what Breakout does.) – Reeta

I'd think that would be the case yes, but from what I'm seeing, updating just based on the time delta produces choppy results. Capping a large time delta then speeding the object up over the next few frames to make up for lost time appears much much smoother. If there was some way to better regulate onDrawFrame calls, simply basing it off time delta would be sufficient I think, but I haven't figured out how to do that yet. – Doenitz

Answer 2

One part of the problem may be caused by fact that Thread.sleep() is not accurate. Try to investigate what is the actual time of the sleep.

The most important thing that should make your animations smooth is that you should compute some interpolation factor, call it alpha, that linearly interpolates your animations in consecutive rendering thread calls between two consecutive animation update thread calls. In other words, if your update interval is high comparing to your framerate, not interpolating your animation update steps is like you'd be rendering at update interval framerate.

EDIT: As an example, this is how PlayN does it:

@Override
public void run() {
  // The thread can be stopped between runs.
  if (!running.get())
    return;

  int now = time();
  float delta = now - lastTime;
  if (delta > MAX_DELTA)
    delta = MAX_DELTA;
  lastTime = now;

  if (updateRate == 0) {
    platform.update(delta);
    accum = 0;
  } else {
    accum += delta;
    while (accum >= updateRate) {
      platform.update(updateRate);
      accum -= updateRate;
    }
  }

  platform.graphics().paint(platform.game, (updateRate == 0) ? 0 : accum / updateRate);

  if (LOG_FPS) {
    totalTime += delta / 1000;
    framesPainted++;
    if (totalTime > 1) {
      log().info("FPS: " + framesPainted / totalTime);
      totalTime = framesPainted = 0;
    }
  }
}

Fatal

this approach seems logical . how would you get the time between the frames ? using System.currentTimeMillis() , and by saving the last time it was updated for each of the animations ? – Maiga

This is one option, you can expect the update frame to be accurate and compute alpha as delta time / desired frame time but when the frame time variation will be high, this may produce some influencies. You can also use this delta time value for Thread.sleep() inaccuracy balancing - for example when the actual sleep time will be 55 ms instead of 50 ms you can sleep 45 ms the next time. Another option could be to predict update time using some floating average. – Fatal

Ad you can even save the whole few previous update states and they deta times (at least 3) and delay rendering loop comparing to update loop by two frames to get fully fluent animation but this may be hard to implement and memory consuming. – Fatal

what is the most common approach ,which won't cause any noticeable weird "jumps" of frames ? – Maiga

I'd guess that the first one is good enough and the most simple so it will be the most used. See edited example as PlayN uses it. – Fatal

i see. thank you . is there a sample code that demonstrates it using libgdx ? – Maiga

I'm not understanding how computing some sort of interpolation in the rendering thread is a different approach from doing the update logic all together in the rendering thread. – Doenitz

The problem as I understand it now is that with the update logic in a different thread, the state of an object when the renderer is triggered is not guaranteed to be up-to-date up to that millisecond. The update could have happened 1ms before the draw, or like 15ms. The next frame, given any variance from Thread.sleep, or just a spike in either thread, the time between the update and the draw could be different. Any further ideas about this? – Doenitz

I has also further importance when the update thread is updating at regular intervals (for example using physics engine) and the rendering thread is rendering as fast as it can (without sleep). – Fatal