14.6.3.2. Bucketed Updates

In the presence of inter-object dependencies, the phased updates technique described above must be adjusted a little. This is because inter-object dependencies can lead to conflicting rules governing the order of updating.

For example, let's imagine that object B is being held by object A. Further, let's assume that we can only update object B after A has been fully updated, including the calculation of its final world-space pose and matrix palette. This conflicts with the need to batch animation updates of all game objects together in order to allow the animation system to achieve maximum throughput.

Inter-object dependencies can be visualized as a forest of dependency trees. The game objects with no parents (no dependencies on any other object) represent the roots of the forest. An object that depends directly on one of these root objects resides in the first tier of children in one of the trees in the forest. An object that depends on a first-tier child becomes a second-tier child, and so on. This is illustrated in Figure 14.14.

Figure 14.14. Inter-object update order dependencies can be viewed as a forest of dependency trees.

One solution to the problem of conflicting update order requirements is to collect objects into independent groups, which we'll call buckets here for lack of a better name. The first bucket consists of all root objects in the forest. The second bucket is comprised of all first-tier children. The third bucket contains all second-tier children, and so on. For each bucket, we run a complete update of the game objects and the engine systems, complete with all update phases. Then we repeat the entire process for each bucket until there are no more buckets.

In theory, the depths of the trees in our dependency forest are unbounded. However, in practice, they are usually quite shallow. For example, we might have characters holding weapons, and those characters might or might not be riding on a moving platform or a vehicle. To implement this, we only need three tiers in our dependency forest, and hence only three buckets: one for platforms/vehicles, one for characters, and one for the weapons in the characters' hands. Many game engines explicitly limit the depth of their dependency forest so that they can use a fixed number of buckets (presuming they use a bucketed approach at all -- there are of course many other ways to architect a game loop).

Here's what a bucketed, phased, batched update loop might look like:

void UpdateBucket(Bucket bucket)
{
// ...

for (each gameObject in bucket)
{
gameObject.PreAnimUpdate(dt);
}

g_animationEngine.CalculateIntermediatePoses
(bucket, dt);

for (each gameObject in bucket)
{
gameObject.PostAnimUpdate(dt);
}

g_ragdollSystem.ApplySkeletonsToRagDolls(bucket);
g_physicsEngine.Simulate(bucket, dt);
// runs
// ragdolls too
g_collisionEngine.DetectAndResolveCollisions
(bucket, dt);

g_ragdollSystem.ApplyRagDollsToSkeletons(bucket);
g_animationEngine.FinalizePoseAndMatrixPalette
(bucket);

for (each gameObject in bucket)
{
gameObject.FinalUpdate(dt);
}
// ...
}
void RunGameLoop()

{
while (true)
{
// ...

UpdateBucket(g_bucketVehiclesAndPlatforms);

UpdateBucket(g_bucketCharacters);

UpdateBucket(g_bucketAttachedObjects);

// ...

g_renderingEngine.RenderSceneAndSwapBuffers();
}
}

In practice, things might a bit more complex than this. For example, some engine subsystems like the physics engine might not support the concept of buckets, perhaps because they are third-party SDKs or because they cannot be practically updated in a bucketed manner. However, this bucketed update is essentially what we used at Naughty Dog to implement Uncharted: Drake's Fortune and are using again for our upcoming title, Uncharted 2: Among Thieves. So it's a method that has proven to be practical and reasonably efficient.