Data structures for interpolation and threading?

Question

I've been dealing with some frame-rate jittering issues with my game lately, and it seems that the best solution would be the one suggested by Glenn Fiedler (Gaffer on Games) in the classic Fix Your Timestep! article.

Now - I'm already using a fixed time-step for my update. The problem is that I'm not doing the suggested interpolation for rendering. The upshot is that I get doubled or skipped frames if my render rate doesn't match my update rate. These can be visually noticeable.

So I'd like to add interpolation to my game - and I'm interested to know how others have structured their data and code to support this.

Obviously I will need to store (where?/how?) two copies of game state information relevant to my renderer, so that it may interpolate between them.

Additionally - this seems like a good place to add threading. I imagine that an update thread could work on a third copy of the game state, leaving the other two copies as read-only for the render thread. (Is this a good idea?)

It seems that having two or three versions of the game's state could introduce performance and - far more importantly - reliability and developer productivity problems, compared to having just a single version. So I'm particularly interested in methods for mitigating those issues.

Of particular note, I think, is the problem of how to handle adding and removing objects from the game state.

Finally, it seems that some state is either not directly needed for rendering, or would be too difficult to track different versions of (eg: a third-party physics engine that stores a single state) - so I'd be interested to know how people have handled that kind of data within such a system.

Answer 1

Do not attempt to replicate the whole game state. Interpolating it would be a nightmare. Just isolate the parts which are variable and needed by rendering (let us call this a "Visual State").

For each object class create an accompanying class which will be able to hold the object Visual State. This object will be produced by the simulation, and consumed by the rendering. The interpolation will easily plug in between. If the state is immutable and passed by value, you will have no threading issues.

The rendering usually does not need to know anything about logical relations between the objects, therefore the structure used for the rendering will be a plain vector, or at most a simple tree.

Example

Traditional design

class Actor
{
  Matrix4x3 position;
  float fuel;
  float armor;
  float stamina;
  float age;

  void Simulate(float deltaT)
  {
    age += deltaT;
    armor -= HitByAWeapon();
  }
}

Using Visual state

class IVisualState
{
  public:
  virtual void Interpolate(const IVisualState &newVS, float f) {}
};
class Actor
{
  struct VisualState: public IVisualState
  {
    Matrix4x3 position;
    float fuel;
    float armor;
    float stamina;
    float age;

    virtual auto_ptr<IVisualState> Interpolate(const IVisualState &newVS, float f)
    {
      const VisualState &newState = static_cast<const VisualState &>(newVS);
      IVisualState *ret = new VisualState;
      ret->age = lerp(this->age,newState.age);
      // ... interpolate other properties as well, using any suitable interpolation method
      // liner, spline, slerp, whatever works best for the given property
      return ret;
    };
  };

  auto_ptr<VisualState> state_;

  void Simulate(float deltaT)
  {
    state_->age += deltaT;
    state_->armor -= HitByAWeapon();
  }
}

Answer 2

My solution far less elegant/complicated than most. I'm using Box2D as my physics engine so keeping more than one copy of the system state isn't manageable (clone the physics system then try to keep them in sync, there might be a better way but I couldn't come up with one).

Instead I keep a running counter of the physics generation. Each update increments the physics generation, when the physics system double updates, the generation counter double updates as well.

The rendering system keeps track of the last rendered generation and the delta since that generation. When rendering objects that wish to interpolate their position can use these values along with their position and velocity to guess where the object should be rendered.

I didn't address what to do if the physics engine was too fast. I'd almost argue that you shouldn't interpolate for fast movement. If you did both, you'd need to be careful to not cause the sprites to jump around by guessing too slow then guessing too fast.

When I wrote the interpolation stuff I was running the graphics at 60Hz and the physics at 30Hz. It turns out that Box2D is much more stable when it is run at 120Hz. Because of this my interpolation code gets very little use. By doubling the target framerate the physics on average updates twice per frame. With jitter that could be 1 or 3 times as well, but almost never 0 or 4+. The higher physics rate kinda fixes the interpolation problem by itself. When running both the physics and framerate at 60hz you might get 0-2 updates per frame. The visual difference between 0 and 2 is huge compared to 1 and 3.

Answer 3

I've heard this approach to timesteps suggested quite frequently, but in 10 years in games, I've never worked on a real-world project that relied on a fixed timestep and interpolation.

It seems generally more effort than a variable timestep system (assuming a sensible range of framerates, in the 25Hz-100Hz sort of range).

I did try the fixed timestep+interpolation approach once for a very small prototype - no threading, but fixed-timestep logic update, and as-fast-as-possible rendering when not updating that. My approach there was to have a few classes such as CInterpolatedVector and CInterpolatedMatrix - which stored previous/current values, and had an accessor used from the render code, to retrieve the value for the current render time (which would always be between the previous and current times)

Each game object would, at the end of it's update, set it's current state in to a set of these interpolatable vectors/matrices. This sort of thing could be extended to support threading, you'd need at least 3 sets of values - one that was being updated, and at least 2 previous values to interpolate between...

Note that some values can't be trivially interpolated (e.g. 'sprite animation frame', 'special effect active'). You may be able to skip interpolation entirely, or it may cause issues, depending on your game's needs.

IMHO, it's best to just go variable timestep - unless you're making an RTS, or other game where you have a huge number of objects, and have to keep 2 independent simulations in sync for network games (sending only orders/commands over the network, rather than object positions). In that situation, fixed-timestep is the only option.

Answer 4

Obviously I will need to store (where?/how?) two copies of game state information relevant to my renderer, so that it may interpolate between them.

Yes, thankfully the key here is "relevant to my renderer". This might be no more than adding an an old position and a timestamp for it into the mix. Given 2 positions you can interpolate to a position between them, and if you have a 3D animation system you can typically just request the pose at that precise point in time anyway.

It's quite simple really - imagine your renderer has to be able to render your game object. It used to ask the object what it looks like, but now it has to ask it what it looked like at a certain time. You just need to store whatever information is necessary to answer that question.

Additionally - this seems like a good place to add threading. I imagine that an update thread could work on a third copy of the game state, leaving the other two copies as read-only for the render thread. (Is this a good idea?)

It just sounds like a recipe for added pain at this point. I haven't thought through the whole implications but I'm guessing you might gain a small bit of extra throughput at the cost of higher latency. Oh, and you may get some benefits from being able to use another core, but I dunno.

Answer 5

Note I'm not actually looking into interpolation so this answer doesn't address it; I am just concerned with having one copy of the game state for the rendering thread, and another for the update thread. So I can't comment on the issue of interpolation, though you could modify the following solution to interpolate.

I've been wondering about this as I've been designing and thinking about a multithreaded engine. So I asked a question on Stack Overflow, about how to implement some sort of "journaling" or "transactions" design pattern. I got some good responses, and the accepted answer really got me thinking.

It's tough to create an immutable object, since all of its children must also be immutable, and you need to be really careful that everything truly is immutable. But if you are indeed careful, you could create a superclass GameState which contains all of the data (and subdata and so on) in your game; the "Model" part of the Model-View-Controller organizational style.

Then, as Jeffrey says, instances of your GameState object are fast, memory efficient, and thread safe. The big downside is that in order to change anything about the model, you sort of need to recreate the model, so you need to be really careful that your code doesn't turn into a huge mess. Setting a variable within the GameState object to a new value is more involved than just var = val;, in terms of lines of code.

I'm terribly intrigued by it though. You don't need to copy your entire data structure every frame; you just copy a pointer to the immutable structure. That by itself is very impressive, don't you agree?

Answer 6

I started by having three copies of the game state of each node in my scene graph. One is being written to by the scene graph thread, one is being read by the renderer, and a third is available for reading/writing as soon as one of those needs to swap. This worked well, but was over complicated.

I then realized I only need to keep three states of what was going to be rendered. My update thread now fills one of three much smaller buffers of "RenderCommands", and the Renderer reads from the newest buffer that's not currently being written to, which prevents the threads from ever waiting on one another.

In my setup, each RenderCommand has the 3d geometry/materials, a transformation matrix, and a list of lights that affect it (still doing forward rendering).

My render thread no longer has to do any culling or light distance calculations, and this sped things up considerably on large scenes.