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?
184.108.40.206. 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.
220.127.116.11. 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.
// Now update low-level engine subsystems on behalf
// of this tank. (NOT a good idea... see below!)
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:
float dt = g_gameClock.CalculateDeltaTime();
for (each gameObject)
// This hypothetical Update() function updates
// all engine subsystems!
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