220.127.116.11. Object State Inconsistencies and One-Frame-Off Lag
Let's revisit game object updating, but this time thinking in terms of each object's local notion of time. We said in Section 14.6 that the state of game object i at time t can be denoted by a state vector Si(t). When we update a game object, we are converting its previous state vector Si(t1) into a new current state vector Si(t2) (where t2 = t1 + Δt).
In theory, the states of all game objects are updated from time t1 to time t2 instantaneously and in parallel, as depicted in Figure 14.15. However, in practice, we can only update the objects one by one -- we must loop over each game object and call some kind of update function on each one in turn. If we were to stop the program half-way through this update loop, half of our game objects' states would have been updated to Si(t2), while the remaining half would still be in their previous states, Si(t1). This implies that if we were to ask two of our game objects what the current time is during the update loop, they may or may not agree! What's more, depending on where exactly we interrupt the update loop, the objects may all be in a partially updated state. For example, animation pose blending may have been run, but physics and collision resolution may not yet have been applied. This leads us to the following rule:
The states of all game objects are consistent before and after the update loop, but they may be inconsistent during it.
This is illustrated in Figure 14.16.
Figure 14.15. In theory, the states of all game objects are updated instantaneously and in parallel during each iteration of the game loop.
Figure 14.16. In practice, the states of the game objects are updated one by one. This means that at some arbitrary moment during the update loop, some objects will think the current time is t2 while others think it is still t1. Some objects may be only partially updated, so their states will be internally inconsistent. In effect, the state of such an object lies at a point between t1 and t2.
The inconsistency of game object states during the update loop is a major source of confusion and bugs, even among professionals within the game industry. The problem rears its head most oft en when game objects query one another for state information during the update loop (which implies that there is a dependency between them). For example, if object B looks at the velocity of object A in order to determine its own velocity at time t, then the programmer must be clear about whether he or she wants to read the previous state of object A, SA(t1), or the new state, SA(t2). If the new state is needed but object A has not yet been updated, then we have an update order problem that can lead to a class of bugs known as one-frame-off lags . In this type of bug, the state of one object lags one frame behind the states of its peers, which manifests itself on-screen as a lack of synchronization between game objects.
18.104.22.168. Object State Caching
As described above, one solution to this problem is to group the game objects into buckets (Section 22.214.171.124). One problem with a simple bucketed update approach is that it imposes somewhat arbitrary limitations on the way in which game objects are permitted to query one another for state information. If a game object A wants the updated state vector SB(t2) of another object B, then object B must reside in a previously updated bucket. Likewise, if object A wants the previous state vector SB(t1) of object B, then object B must reside in a yet-to-be-updated bucket. Object A should never ask for the state vector of an object within its own bucket, because as we stated in the rule above, those state vectors may be only partially updated.
One way to improve consistency is to arrange for each game object to cache its previous state vector Si(t1) while it is calculating its new state vector Si(t2) rather than overwriting it in-place during its update. This has two immediate benefits. First, it allows any object to safely query the previous state vector of any other object without regard to update order. Second, it guarantees that a totally consistent state vector (Si(t1)) will always be available, even during the update of the new state vector. To my knowledge there is no standard terminology for this technique, so I'll call it state caching for lack of a better name.
Another benefit of state caching is that we can linearly interpolate between the previous and next states in order to approximate the state of an object at any moment between these two points in time. The Havok physics engine maintains the previous and current state of every rigid body in the simulation for just this purpose.
The downside of state caching is that it consumes twice the memory of the update-in-place approach. It also only solves half the problem, because while the previous states at time t1 are fully consistent, the new states at time t2 still suffer from potential inconsistency. Nonetheless, the technique can be useful when applied judiciously.