Gamasutra: The Art & Business of Making Gamesspacer
Book Excerpt: Game Engine Architecture
View All     RSS
September 2, 2014
arrowPress Releases
September 2, 2014
PR Newswire
View All





If you enjoy reading this site, you might also want to check out these UBM Tech sites:


 
Book Excerpt: Game Engine Architecture

November 25, 2009 Article Start Previous Page 4 of 6 Next
 

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.


Article Start Previous Page 4 of 6 Next

Related Jobs

WB Games
WB Games — Kirkland, Washington, United States
[09.02.14]

Senior Software Engineer, Graphics
Wargaming.net
Wargaming.net — Chicago, Illinois, United States
[09.02.14]

QA Analyst - Web
Playtika Santa Monica
Playtika Santa Monica — Santa Monica, California, United States
[09.01.14]

Sr. BI Developer
Wargaming.net
Wargaming.net — Hunt Valley, Maryland, United States
[09.01.14]

Engineering Manager






Comments


James Hofmann
profile image
Cool read. I've started using something akin to buckets, but I call them "choreographers" and they're conceptually "fatter" - they aren't just there to resolve update dependencies. Instead they replace the actor model, and execute their own code to drive the dependent objects as completely as possible. A squad of soldiers, a tank and its driver, and a group of projectiles can each be expressed in a choreographed form: the choreographer just needs to be aware of which groups of objects it's acting on, and then it can "take over" their AI. Once I did this, the biggest dependency problems disappeared. Individual behavior can still vary in this model, so I haven't "lost" anything as far as I can tell.

Taure Anthony
profile image
A great read

Edelmar Schneider
profile image
Worth every line.

Quentin Smith
profile image
Very nice read. I wonder what affect event listeners would have on these various designs. The core of the system revolving around buckets, which should resolve 80% of timing issues, with exceptions, the 20%, handled by listeners attaching to update events. In your example, B would hold A, a depends on B. Even if A and B are in the same bucket, A knows it depends on B so A ignores updating and instead waits for broadcast from B. Cross dependency resolution rules would have to be applied, say when A depends on B, yet B depends on C, who depends on A. To ensure all objects update, however, more than likely we could throw away confusing linkages for simulation sake.

Timothy Ryan
profile image
Interesting except for multi-threaded solutions it's common practice to update animation, physics etc. using separate threads.

Jason Gregory
profile image
Very true... using SIMD, fork/join, one-thread-per-subsystem, and/or jobs for parallelism is described in detail in chapter 7 of the book. When major subsystems are updated via threads or jobs, the calls to "update" those systems from the main thread are still there, but they are responsible only for setting up and "kicking" the SPU jobs, or sending "start" commands to the threads involved.

Stephen Northcott
profile image
The spooky thing for me about this article is that it's like reading through the trial and error that I (and others I am sure) went through over the years when refining various engines I/they have been involved in....



Perhaps "spooky" is not the right word, and "reassuring" or "familiar" could be....



A good read.

Eirik Moseng
profile image
The article is for sure great read but I can really recommend the book too even if you are a professional game programmer. Its worth every single penny. I have read through a few books on game engine design and architecture and in my opinion, Jason's book is really outstanding in many cases.

Alban Wood
profile image
Caching object state of previous frames and subsequent interpolation of frames can also allow a system that can only update its simulation (gameplay, animation, physics, etc) at a given rate to still render at a higher rate. Of course, this introduces added latency since we must wait for two simulation frames to be ready before we can show anything, and the input feedback isn't any faster since it is tied to the simulation update, but useful nonetheless.



I agree that updating game objects in parallel is tricky. If static analysis can be performed (what data does the object read, what data does it write, what behaviour runs on it), it can be automated to a certain point (like most job trees would do), but it's easier said than done. Super interesting problem though.

Alban Wood
profile image
Jason, by the way, is your gameplay/simulation still deterministic? Do all jobs for a given frame absolutely non-optionally need to complete before the frame is considered over? Would the jobs being executed in a different order or finishing at different times for two identical runs of the simulation yield a different result?



One thing I consider paramount is deterministic behaviour, for many reasons. But one important reason is to be able to reproduce problems, behaviour, and tune the game against reproducible scenarios (and have the certainty that a problem is fixed or something is properly tuned by re-simulating the game to the problematic point with the fix).

Daniel Koenig-Schieber
profile image
I'll have to second Eirik's post, you did a great job Jason. I came across a couple of books about various programming fields and this particular one goes with the small selection that is as informative as it is just fun to read. I really hope that you may find the time and energy to do some more books like this on other topics.

Believe it or not, although I am not working within the game industry, some of the principles that are explained are as useful for other programming tasks and I always love to get a fresh perspective to handling data management problems. So it is actually both, an interesting look behind the scenes of the bits and bolts in game engines and a valuable resource for concepts that also do apply to other fields.

Ayotunde Ayoko
profile image
excellent..

Yuri Syrov
profile image
All patterns mentioned were used 20-some years ago in pre-MT universe. Perhaps still relevant for mobiles. Now, with tens of cores, hundreds of threads and VNUMAs, things are not at all the same.

Jason Gregory
profile image
Alban: In the Uncharted 2 engine, SPU jobs are kicked by the central "game loop" thread on the PPU, as described above, or kicked automatically by previous SPU jobs. So all job "scheduling" is ultimately derived from what happens on the PPU. Given a set of initial conditions, what happens during a given frame is therefore *mostly* deterministic. We don't always control which of the 6 SPUs a particular job runs on, and certain subsystems like audio introduce some minor indeterminisms as well. But for the most part, it's deterministic. Our concept of "frame" is a bit loose, because rendering is tied to vsync, but the main game loop is only loosely coupled to rendering. During a given frame it's possible for, say, post processing from the previous frame to be running on the SPUs even *after* the next game frame has started executing on the PPU and kicking its own SPU jobs. This ensures we don't idle the PPU or SPUs waiting for vsync unless we absolutely have to.

Michael Dube
profile image
Nice and informative read. I'm thinking about buying the book. Looks very interesting indeed.

Dave Smith
profile image
Lucid and enlightening. Congratulations on the Front Line Award nomination for your book! I can't wait to read the rest of it.


none
 
Comment: