Book Excerpt: Game Engine Architecture
July 23, 2014
Press Releases
July 23, 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 Page 1 of 6

[Gamasutra presents an excerpt from Naughty Dog programmer Jason Gregory's Game Engine Architecture; the book contains a huge amount of data on specifics to consider when developing a game engine. This excerpt, from Chapter 14 in particular, covers how the engine handles objects. For more info, visit the book's official site.]

# Updating Game Objects in Real Time

Every game engine, from the simplest to the most complex, requires some means of updating the internal state of every game object over time. The state of a game object can be defined as the values of all its attributes (sometimes called its properties, and called data members in the C++ language). For example, the state of the ball in Pong is described by its (x, y) position on the screen and its velocity (speed and direction of travel). Because games are dynamic, time-based simulations, a game object's state describes its configuration at one specific instant in time. In other words, a game object's notion of time is discrete rather than continuous. (However, as we'll see, it's helpful to think of the objects' states as changing continuously and then being sampled discretely by the engine, because it helps you to avoid some common pitfalls.)

In the following discussions, we'll use the symbol Si(t) to denote the state of object i at an arbitrary time t. The use of vector notation here is not strictly mathematically correct, but it reminds us that a game object's state acts like a heterogeneous n-dimensional vector, containing all sorts of information of various data types. We should note that this usage of the term "state" is not the same as the states in a finite state machine . A game object may very well be implemented in terms of one -- or many -- finite state machines, but in that case, a specification of the current state of each FSM would merely be a part of the game object's overall state vector S(t).

Most low-level engine subsystems (rendering, animation, collision, physics, audio, and so on) require periodic updating, and the game object system is no exception. As we saw in Chapter 7, updating is usually done via a single master loop called the game loop (or possibly via multiple game loops , each running in a separate thread ). Virtually all game engines update game object states as part of their main game loop -- in other words, they treat the game object model as just another engine subsystem that requires periodic servicing.

Game object updating can therefore be thought of as the process of determining the state of each object at the current time Si(t) given its state at a previous time Si(t - Δt). Once all object states have been updated, the current time t becomes the new previous time (t - Δt), and this process repeats for as long as the game is running. Usually, one or more clocks are maintained by the engine -- one that tracks real time exactly and possibly others that may or may not correspond to real time. These clocks provide the engine with the absolute time t and/or with the change in time Δt from iteration to iteration of the game loop. The clock that drives the updating of game object states is usually permitted to diverge from real time. This allows the behaviors of the game objects to be paused, slowed down, sped up, or even run in reverse -- whatever is required in order to suit the needs of the game design. These features are also invaluable for debugging and development of the game.

As we mentioned in Chapter 1, a game object updating system is an example of what is known as a dynamic, real-time, agent-based computer simulation in computer science. Game object updating systems also exhibit some aspects of discrete event simulations (see Section 14.7 for more details on events). These are well-researched areas of computer science, and they have many applications outside the field of interactive entertainment. Games are one of the more-complex kinds of agent-based simulation -- as we'll see, updating game object states over time in a dynamic, interactive virtual environment can be surprisingly difficult to get right. Game programmers can learn a lot about game object updating by studying the wider field of agent-based and discrete event simulations. And researchers in those fields can probably learn a thing or two from game engine design as well!

As with all high-level game engine systems, every engine takes a slightly (or sometimes radically) different approach. However, as before, most game teams encounter a common set of problems, and certain design patterns tend to crop up again and again in virtually every engine. In this section, we'll investigate these common problems and some common solutions to them. Please bear in mind that game engines may exist that employ very different solutions to the ones described here, and some game designs face unique problems that we can't possibly cover here.

14.6.1. A Simple Approach (That Doesn't Work)

The simplest way to update the states of a collection of game objects is to iterate over the collection and call a virtual function, named something like Update(), on each object in turn. This is typically done once during each iteration of the main game loop (i.e., once per frame). Game object classes can provide custom implementations of the Update() function in order to perform whatever tasks are required to advance the state of that type of object to the next discrete time index. The time delta from the previous frame can be passed to the update function so that objects can take proper account of the passage of time. At its simplest, then, our Update() function's signature might look something like this:

virtual void Update(float dt);

For the purposes of the following discussions, we'll assume that our engine employs a monolithic object hierarchy, in which each game object is represented by a single instance of a single class. However, we can easily extend the ideas here to virtually any object-centric design. For example, to update a component-based object model, we could call Update() on every component that makes up each game object, or we could call Update() on the "hub" object and let it update its associated components as it sees fit. We can also extend these ideas to property-centric designs, by calling some sort of Update() function on each property instance every frame.

They say that the devil is in the details, so let's investigate two important details here. First, how should we maintain the collection of all game objects? And second, what kinds of things should the Update() function be responsible for doing?

14.6.1.1. Maintaining a Collection of Active Game Objects

The collection of active game objects is often maintained by a singleton manager class, perhaps named something like GameWorld or GameObject Manager. The collection of game objects generally needs to be dynamic, because game objects are spawned and destroyed as the game is played. Hence a linked list of pointers, smart pointers, or handles to game objects is one simple and effective approach. (Some game engines disallow dynamic spawning and destroying of game objects; such engines can use a statically-sized array of game object pointers, smart pointers, or handles rather than a linked list.) As we'll see below, most engines use more-complex data structures to keep track of their game objects rather than just a simple, flat linked list. But for the time being, we can visualize the data structure as a linked list for simplicity.

14.6.1.2. Responsibilities of the Update() Function

A game object's Update() function is primarily responsible for determining the state of that game object at the current discrete time index Si(t) given its previous state Si(t - Δt). Doing this may involve applying a rigid body dynamics simulation to the object, sampling a preauthored animation, reacting to events that have occurred during the current time step, and so on.

Most game objects interact with one or more engine subsystems. They may need to animate , be rendered, emit particle effects, play audio, collide with other objects and static geometry, and so on. Each of these systems has an internal state that must also be updated over time, usually once or a few times per frame. It might seem reasonable and intuitive to simply update all of these subsystems directly from within the game object's Update() function. For example, consider the following hypothetical update function for a Tank object:

virtual void Tank::Update(float dt)
{
// Update the state of the tank itself.
MoveTank(dt);

DeflectTurret(dt);
FireIfNecessary();

// Now update low-level engine subsystems on behalf
// of this tank. (NOT a good idea... see below!)
m_pAnimationComponent->Update(dt);

m_pCollisionComponent->Update(dt);

m_pPhysicsComponent->Update(dt);

m_pAudioComponent->Update(dt);
m_pRenderingComponent->draw();
}

Given that our Update() functions are structured like this, the game loop could be driven almost entirely by the updating of the game objects, like this:

while (true)
{

float dt = g_gameClock.CalculateDeltaTime();

for (each gameObject)
{
// This hypothetical Update() function updates
// all engine subsystems!
gameObject.Update(dt);
}

g_renderingEngine.SwapBuffers();
}

However attractive the simple approach to object updating shown above may seem, it is usually not viable in a commercial-grade game engine. In the following sections, we'll explore some of the problems with this simplistic approach and investigate common ways in which each problem can be solved.

Page 1 of 6

### Related Jobs

Disney Consumer Products — Glendale, California, United States
[07.23.14]

Contract Game Programmer
Zindagi Games — Camarillo, California, United States
[07.23.14]

Software Engineer
Telltale Games — San Rafael, California, United States
[07.23.14]

Core Technology – Client Network Engineer
Gearbox Software — Plano, Texas, United States
[07.23.14]

Release Engineer

 James Hofmann
 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

 Edelmar Schneider
 Worth every line.

 Quentin Smith
 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
 Interesting except for multi-threaded solutions it's common practice to update animation, physics etc. using separate threads.

 Jason Gregory
 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

 Eirik Moseng
 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
 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
 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
 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
 excellent..

 Yuri Syrov
 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
 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