16.2.1.1 A Simple Object-Based Model in C: Hydro Thunder

Game object models needn’t be implemented in an object-oriented language like C++ at all. For example, the arcade hit Hydro Thunder, by Midway Home Entertainment in San Diego, was written entirely in C. Hydro employed a very simple game object model consisting of only a few object types:

A few screenshots of Hydro Thunder are shown in Figure 16.1. Notice the hovering boost icons in both screenshots and the shark swimming by in the left image (an example of an ambient animated object).

Hydro had a C struct named World_t that stored and managed the contents of a game world (i.e., a single race track). The world contained pointers to arrays of various kinds of game objects. The static geometry was a single mesh instance. The water surface, waterfalls and particle effects were each represented by custom data structures. The boats, boost icons and other dynamic objects in the game were represented by instances of a general-purpose struct called WorldOb_t (i.e., a world object). This was Hydro’s equivalent of a game object as we’ve defined it in this chapter.

The WorldOb_t data structure contained data members encoding the position and orientation of the object, the 3D mesh used to render it, a set of collision spheres, simple animation state information (Hydro only supported rigid hierarchical animation), physical properties like velocity, mass and buoyancy, and other data common to all of the dynamic objects in the game. In addition, each WorldOb_t contained three pointers: a void* “user data” pointer, a pointer to a custom “update” function and a pointer to a custom “draw” function. So while Hydro Thunder was not object-oriented in the strictest sense, the Hydro engine did extend its non-object-oriented language (C) to support rudimentary implementations of two important OOP features: inheritance and polymorphism. The user data pointer permitted each type of game object to maintain custom state information specific to its type while inheriting the features common to all world objects. For example, the Banshee boat had a different booster mechanism than the Rad Hazard, and each booster mechanism required different state information to manage its deployment and stowing animations. The two function pointers acted like virtual functions, allowing world objects to have polymorphic behaviors (via their “update” functions) and polymorphic visual appearances (via their “draw” functions).

struct WorldOb_s
{
 Orient_t m_transform; /* position/rotation */
 Mesh3d* m_pMesh;  /* 3D mesh */
 /* … */
 void* m_pUserData; /* custom state */
 void (*m_pUpdate)(); /* polymorphic update */
 void (*m_pDraw)(); /* polymorphic draw */
};
typedef struct WorldOb_s WorldOb_t;

16.2.1.2 Monolithic Class Hierarchies

It’s natural to want to classify game object types taxonomically. This tends to lead game programmers toward an object-oriented language that supports inheritance. A class hierarchy is the most intuitive and straightforward way to represent a collection of interrelated game object types. So it is not surprising that the majority of commercial game engines employ a class hierarchy based technique.

Figure 16.2 shows a simple class hierarchy that could be used to implement the game Pac-Man. This hierarchy is rooted (as many are) at a common class called GameObject, which might provide some facilities needed by all object types, such as RTTI or serialization. The MovableObject class represents any object that has a position and orientation. RenderableObject gives the object an ability to be rendered (in the case of traditional Pac-Man, via a sprite, or in the case of a modern 3D Pac-Man game, perhaps via a triangle mesh). From RenderableObject are derived classes for the ghosts, Pac-Man, pellets and power pills that make up the game. This is just a hypothetical example, but it illustrates the basic ideas that underlie most game object class hierarchies—namely that common, generic functionality tends to exist at the root of the hierarchy, while classes toward the leaves of the hierarchy tend to add increasingly specific functionality.

A game object class hierarchy usually begins small and simple, and in that form, it can be a powerful and intuitive way to describe a collection of game object types. However, as class hierarchies grow, they have a tendency to deepen and widen simultaneously, leading to what I call a monolithic class hierarchy. This kind of hierarchy arises when virtually all classes in the game object model inherit from a single, common base class. The Unreal Engine’s game object model is a classic example, as Figure 16.3 illustrates.

16.2.1.3 Problems with Deep, Wide Hierarchies

Monolithic class hierarchies tend to cause problems for the game development team for a wide range of reasons. The deeper and wider a class hierarchy grows, the more extreme these problems can become. In the following sections, we’ll explore some of the most common problems caused by wide, deep class hierarchies.

Inability to Describe Multidimensional Taxonomies

A hierarchy inherently classifies objects according to a particular system of criteria known as a taxonomy. For example, biological taxonomy (also known as alpha taxonomy) classifies all living things according to genetic similarities, using a tree with eight levels: domain, kingdom, phylum, class, order, family, genus and species. At each level of the tree, a different criterion is used to divide the myriad life forms on our planet into more and more refined groups.

One of the biggest problems with any hierarchy is that it can only classify objects along a single “axis”—according to one particular set of criteria—at each level of the tree. Once the criteria have been chosen for a particular hierarchy, it becomes difficult or impossible to classify along an entirely different set of “axes.” For example, biological taxonomy classifies objects according to genetic traits, but it says nothing about the colors of the organisms. In order to classify organisms by color, we’d need an entirely different tree structure.

In object-oriented programming, this limitation of hierarchical classification often manifests itself in the form of wide, deep and confusing class hierarchies. When one analyzes a real game’s class hierarchy, one often finds that its structure attempts to meld a number of different classification criteria into a single class tree. In other cases, concessions are made in the class hierarchy to accommodate a new type of object whose characteristics were not anticipated when the hierarchy was first designed. For example, imagine the seemingly logical class hierarchy describing different types of vehicles, depicted in Figure 16.4.

What happens when the game designers announce to the programmers that they now want the game to include an amphibious vehicle? Such a vehicle does not fit into the existing taxonomic system. This may cause the programmers to panic or, more likely, to “hack” their class hierarchy in various ugly and error-prone ways.

Multiple Inheritance: The Deadly Diamond

One solution to the amphibious vehicle problem is to utilize C++’s multiple inheritance (MI) features, as shown in Figure 16.5. At first glance, this seems like a good solution. However, multiple inheritance in C++ poses a number of practical problems. For example, multiple inheritance can lead to an object that contains multiple copies of its base class’ members—a condition known as the “deadly diamond” or “diamond of death.” (See Section 3.1.1.3 for more details.)

The difficulties in building an MI class hierarchy that works and that is understandable and maintainable usually outweigh the benefits. As a result, most game studios prohibit or severely limit the use of multiple inheritance in their class hierarchies.

Mix-In Classes

Some teams do permit a limited form of MI, in which a class may have any number of parent classes but only one grandparent. In other words, a class may inherit from one and only one class in the main inheritance hierarchy, but it may also inherit from any number of mix-in classes (stand-alone classes with no base class). This permits common functionality to be factored out into a mix-in class and then spot-patched into the main hierarchy wherever it is needed. This is shown in Figure 16.6. However, as we’ll see below, it’s usually better to compose or aggregate such classes than to inherit from them.

16.2.1.4 Using Composition to Simplify the Hierarchy

Perhaps the most prevalent cause of monolithic class hierarchies is over-use of the “is-a” relationship in object-oriented design. For example, in a game’s GUI, a programmer might decide to derive the class Window from a class called Rectangle, using the logic that GUI windows are always rectangular. However, a window is not a rectangle—it has a rectangle, which defines its boundary. So a more workable solution to this particular design problem is to embed an instance of the Rectangle class inside the Window class, or to give the Window a pointer or reference to a Rectangle.

In object-oriented design, the “has-a” relationship is known as composition. In composition, a class A either contains an instance of class B directly, or contains a pointer or reference to an instance of B. Strictly speaking, in order for the term “composition” to be applicable, class A must own class B. This means that when an instance of class A is created, it automatically creates an instance of class B as well; when that instance of A is destroyed, its instance of B is destroyed, too. We can also link classes to one another via a pointer or reference without having one of the classes manage the other’s lifetime. In that case, the technique is usually called aggregation.

Converting Is-A to Has-A

Converting “is-a” relationships into “has-a” relationships can be a useful technique for reducing the width, depth and complexity of a game’s class hierarchy. To illustrate, let’s take a look at the hypothetical monolithic hierarchy shown in Figure 16.7. The root GameObject class provides some basic functionality required by all game objects (e.g., RTTI, reflection, persistence via serialization, network replication, etc.). The MovableObject class represents any game object that has a transform (i.e., a position, orientation and optional scale). RenderableObject adds the ability to be rendered onscreen. (Not all game objects need to be rendered—for example, an invisible TriggerRegion class could be derived directly from MovableObject.) The CollidableObject class provides collision information to its instances. The AnimatingObject class grants to its instances the ability to be animated via a skeletal joint hierarchy. Finally, the PhysicalObject gives its instances the ability to be physically simulated (e.g., a rigid body falling under the influence of gravity and bouncing around in the game world).

One big problem with this class hierarchy is that it limits our design choices when creating new types of game objects. If we want to define an object type that is physically simulated, we are forced to derive its class from PhysicalObject even though it may not require skeletal animation. If we want a game object class with collision, it must inherit from CollidableObject even though it may be invisible and hence not require the services of RenderableObject.

A second problem with the hierarchy shown in Figure 16.7 is that it is difficult to extend the functionality of the existing classes. For example, let’s imagine we want to support morph target animation, so we derive two new classes from AnimatingObject called SkeletalObject and MorphTargetObject. If we wanted both of these new classes to have the ability to be physically simulated, we’d be forced to refactor PhysicalObject into two nearly identical classes, one derived from SkeletalObject and one from MorphTargetObject, or turn to multiple inheritance.

One solution to these problems is to isolate the various features of a GameObject into independent classes, each of which provides a single, well-defined service. Such classes are sometimes called components or service objects. A componentized design allows us to select only those features we need for each type of game object we create. In addition, it permits each feature to be maintained, extended or refactored without affecting the others. The individual components are also easier to understand, and easier to test, because they are decoupled from one another. Some component classes correspond directly to a single engine subsystem, such as rendering, animation, collision, physics, audio, etc. This allows these subsystems to remain distinct and well-encapsulated when they are integrated together for use by a particular game object.

Figure 16.8 shows how our class hierarchy might look after refactoring it into components. In this revised design, the GameObject class acts like a hub, containing pointers to each of the optional components we’ve defined. The MeshInstance component is our replacement for the RenderableObject class—it represents an instance of a triangle mesh and encapsulates the knowledge of how to render it. Likewise, the AnimationController component replaces AnimatingObject, exposing skeletal animation services to the GameObject. Class Transform replaces MovableObject by maintaining the position, orientation and scale of the object. The RigidBody class represents the collision geometry of a game object and provides its GameObject with an interface into the low-level collision and physics systems, replacing CollidableObject and PhysicalObject.

 class GameObject
 {
 protected:
 // My transform (position, rotation, scale).
 Transform  m_transform;
 // Standard components:
 MeshInstance*  m_pMeshInst;
 AnimationController* m_pAnimController;
 RigidBody*  m_pRigidBody;
 public:
 GameObject()
 {
 // Assume no components by default.
 // Derived classes will override.
 m_pMeshInst = nullptr;
 m_pAnimController = nullptr;
 m_pRigidBody = nullptr;
 }
 ∼GameObject()
 {
 // Automatically delete any components created by
 // derived classes. (Deleting null pointers OK.)
 delete m_pMeshInst;
 delete m_pAnimController;
 delete m_pRigidBody;
 }
 // …
 };
 class Vehicle : public GameObject
 {
 protected:
 // Add some more components specific to Vehicles …
 Chassis* m_pChassis;
 Engine* m_pEngine;
 // …
 public:
 Vehicle()
 {
 // Construct standard GameObject components.
 m_pMeshInst = new MeshInstance;
 m_pRigidBody = new RigidBody;
 // NOTE: We’ll assume the animation controller
 // must be provided with a reference to the mesh
 // instance so that it can provide it with a
 // matrix palette.
 m_pAnimController
 = new AnimationController(*m_pMeshInst);
 // Construct vehicle-specific components.
 m_pChassis = new Chassis(*this,
 *m_pAnimController);
 m_pEngine = new Engine(*this);
 }
 ~Vehicle()
 {
 // Only need to destroy vehicle-specific
 // components, as GameObject cleans up the
 // standard components for us.
 delete m_pChassis;
 delete m_pEngine;
 }
 };

16.2.1.5 Generic Components

Another more flexible (but also trickier to implement) alternative is to provide the root game object class with a generic linked list of components. The components in such a design usually all derive from a common base class—this allows us to iterate over the linked list and perform polymorphic operations, such as asking each component what type it is or passing an event to each component in turn for possible handling. This design allows the root game object class to be largely oblivious to the component types that are available and thereby permits new types of components to be created without modifying the game object class in many cases. It also allows a particular game object to contain an arbitrary number of instances of each type of component. (The hard-coded design permits only a fixed number, determined by how many pointers to each component exist within the game object class.)

This kind of design is illustrated in Figure 16.9. It is trickier to implement than a hard-coded component model because the game object code must be written in a totally generic way. The component classes can likewise make no assumptions about what other components might or might not exist within the context of a particular game object. The choice between hard-coding the component pointers or using a generic linked list of components is not an easy one to make. Neither design is clearly superior—they each have their pros and cons, and different game teams take different approaches.

16.2.1.6 Pure Component Models

What would happen if we were to take the componentization concept to its extreme? We would move literally all of the functionality out of our root GameObject class into various component classes. At this point, the game object class would quite literally be a behavior-less container, with a unique id and a bunch of pointers to its components, but otherwise containing no logic of its own. So why not eliminate the class entirely? One way to do this is to give each component a copy of the game object’s unique id. The components are now linked together into a logical grouping by id. Given a way to quickly look up any component by id, we would no longer need the GameObject “hub” class at all. I will use the term pure component model to describe this kind of architecture. It is illustrated in Figure 16.10.

A pure component model is not quite as simple as it first sounds, and it is not without its share of problems. For one thing, we still need some way of defining the various concrete types of game objects our game needs and then arranging for the correct component classes to be instantiated whenever an instance of the type is created. Our GameObject hierarchy used to handle construction of components for us. Instead, we might use a factory pattern, in which we define factory classes, one per game object type, with a virtual construction function that is overridden to create the proper components for each game object type. Or we might turn to a data-driven model, where the game object types are defined in a text file that can be parsed by the engine and consulted whenever a type is instantiated.

Another issue with a components-only design is inter-component communication. Our central GameObject acted as a “hub,” marshalling communications between the various components. In pure component architectures, we need an efficient way for the components making up a single game object to talk to one another. This could be done by having each component look up the other components using the game object’s unique id. However, we probably want a much more efficient mechanism—for example the components could be prewired into a circular linked list.

In the same sense, sending messages from one game object to another is difficult in a pure componentized model. We can no longer communicate with the GameObject instance, so we either need to know a priori with which component we wish to communicate, or we must multicast to all components that make up the game object in question. Neither option is ideal.

Pure component models can and have been made to work on real game projects. These kinds of models have their pros and cons, but again, they are not clearly better than any of the alternative designs. Unless you’re part of a research and development effort, you should probably choose the architecture with which you are most comfortable and confident, and which best fits the needs of the particular game you are building.

16.2.2.1 Implementing Behavior via Property Classes

Each type of property can be implemented as a property class. Properties can be as simple as a single Boolean or floating-point value or as complex as a renderable triangle mesh or an AI “brain.” Each property class can provide behaviors via its hard-coded methods (member functions). The overall behavior of a particular game object is determined by the aggregation of the behaviors of all its properties.

For example, if a game object contains an instance of the Health property, it can be damaged and eventually destroyed or killed. The Health object can respond to any attacks made on the game object by decrementing the object’s health level appropriately. A property object can also communicate with other property objects within the same game object to produce cooperative behaviors. For example, when the Health property detects and responds to an attack, it could possibly send a message to the AnimatedSkeleton property, thereby allowing the game object to play a suitable hit reaction animation. Similarly, when the Health property detects that the game object is about to die or be destroyed, it can talk to the RigidBodyDynamics property to activate a physics-driven explosion or a “rag doll” dead body simulation.

16.2.2.2 Implementing Behavior via Script

Another option is to store the property values as raw data in one or more database-like tables and use script code to implement a game object’s behaviors. Every game object could have a special property called something like ScriptId, which, if present, specifies the block of script code (script function, or script object if the scripting language is itself object-oriented) that will manage the object’s behavior. Script code could also be used to allow a game object to respond to events that occur within the game world. See Section 16.8 for more details on event systems and Section 16.9 for a discussion of game scripting languages.

In some property-centric engines, a core set of hard-coded property classes is provided by the engineers, but a facility is provided allowing game designers and programmers to implement new property types entirely in script. This approach was used successfully on the Dungeon Siege project, for example.

16.2.2.3 Properties versus Components

It’s important to note that many of the authors cited in Section 16.2.2.5 use the term “component” to refer to what I call a “property object” here. In Section 16.2.1.4, I used the term “component” to refer to a subobject in an object-centric design, which isn’t quite the same as a property object.

However, property objects are very closely related to components in many ways. In both designs, a single logical game object is made up of multiple subobjects. The main distinction lies in the roles of the subobjects. In a property-centric design, each subobject defines a particular attribute of the game object itself (e.g., health, visual representation, inventory, a particular magic power, etc.), whereas in a component-based (object-centric) design, the subobjects often represent linkages to particular low-level engine subsystems (renderer, animation, collision and dynamics, etc.) This distinction is so subtle as to be virtually irrelevant in many cases. You can call your design a pure component model (Section 16.2.1.6) or a property-centric design as you see fit, but at the end of the day, you’ll have essentially the same result—a logical game object that is comprised of, and derives its behavior from, a collection of subobjects.

16.2.2.4 Pros and Cons of Property-Centric Designs

There are a number of potential benefits to an attribute-centric approach. It tends to be more memory-efficient, because we need only store attribute data that is actually in use (i.e., there are never game objects with unused data members). It is also easier to construct such a model in a data-driven manner—designers can define new attributes easily, without recompiling the game, because there are no game object class definitions to be changed. Programmers need only get involved when entirely new types of properties need to be added (presuming the property cannot be added via script).

A property-centric design can also be more cache-friendly than an object-centric model, because data of the same type is stored contiguously in memory. This is a commonplace optimization technique on modern gaming hardware, where the cost of accessing memory is far higher than the cost of executing instructions and performing calculations. (For example, on the PlayStation 3, the cost of a single cache miss is equivalent to the cost of executing literally thousands of CPU instructions.) By storing data contiguously in RAM, we can reduce or eliminate cache misses, because when we access one element of a data array, a large number of its neighboring elements are loaded into the same cache line. This approach to data design is sometimes called the struct of arrays technique, in contrast to the more-traditional array of structs approach. The differences between these two memory layouts are illustrated by the code snippet below. (Note that we wouldn’t really implement a game object model in exactly this way—this example is meant only to illustrate the way in which a property-centric design tends to produce many contiguous arrays of like-typed data, rather than a single array of complex objects.)

static const U32 MAX_GAME_OBJECTS = 1024;
// Traditional array-of-structs approach.
 struct GameObject
 {
 U32  m_uniqueId;
 Vector  m_pos;
 Quaternion m_rot;
 float  m_health;
 // …
 };
 GameObject g_aAllGameObjects[MAX_GAME_OBJECTS]; // Cache-friendlier struct-of-arrays approach.
 struct AllGameObjects
 {
 U32  m_aUniqueId[MAX_GAME_OBJECTS];
 Vector  m_aPos[MAX_GAME_OBJECTS];
 Quaternion m_aRot[MAX_GAME_OBJECTS];
 float  m_aHealth[MAX_GAME_OBJECTS];
 // …
 };
 AllGameObjects g_allGameObjects;

Attribute-centric models have their share of problems as well. For example, when a game object is just a grab bag of properties, it becomes much more difficult to enforce relationships between those properties. It can be hard to implement a desired large-scale behavior merely by cobbling together the finegrained behaviors of a group of property objects. It’s also much trickier to debug such systems, as the programmer cannot slap a game object into the watch window in the debugger in order to inspect all of its properties at once.

16.2.2.5 Further Reading

A number of interesting PowerPoint presentations on the topic of property-centric architectures have been given by prominent engineers in the game industry at various game development conferences.

16.3.3.1 Object Type Schemas

A game object’s attributes and behaviors are defined by its type. In a game world editor that employs a spawner-based design, a game object type can be represented by a data-driven schema that defines the collection of attributes that should be visible to the user when creating or editing an object of that type. At runtime, the tool-side object type can be mapped in either a hard-coded or data-driven way to a class or collection of classes that must be instantiated in order to spawn a game object of the given type.

Type schemas can be stored in a simple text file for consumption by the world editor and for inspection and editing by its users. For example, a schema file might look something like this:

enum LightType
 {
 Ambient, Directional, Point, Spot
 }
 type Light
 {
 String  UniqueId;
 LightType Type; Vector  Pos;
 Quaternion Rot;
 Float  Intensity : min(0.0), max(1.0);
 ColorARGB DiffuseColor;
 ColorARGB SpecularColor;
 // …
 }
 type Vehicle
 {
 String  UniqueId;
 Vector  Pos;
 Quaternion  Rot;
 MeshReference Mesh;
 Int  NumWheels : min(2), max(4);
 Float  TurnRadius;
 Float  TopSpeed : min(0.0);
 // …
 }
 // …

The above example brings a few important details to light. You’ll notice that the data types of each attribute are defined, in addition to their names. These can be simple types like strings, integers and floatingpoint values, or they can be specialized types like vectors, quaternions, ARGB colors, or references to special asset types like meshes, collision data and so on. In this example, we’ve even provided a mechanism for defining enumerated types, like LightType. Another subtle point is that the object type schema provides additional information to the world editor, such as what type of GUI element to use when editing the attribute. Sometimes an attribute’s GUI requirements are implied by its data type—strings are generally edited with a text field, Booleans via a check box, vectors via three text fields for the x-, y- and z-coordinates or perhaps via a specialized GUI element designed for manipulating vectors in 3D. The schema can also specify meta-information for use by the GUI, such as minimum and maximum allowable values for integer and floating-point attributes, lists of available choices for drop-down combo boxes and so on.

Some game engines permit object type schemas to be inherited, much like classes. For example, every game object needs to know its type and must have a unique id so that it can be distinguished from all the other game objects at runtime. These attributes could be specified in a top-level schema, from which all other schemas are derived.

16.3.3.2 Default Attribute Values

As you can well imagine, the number of attributes in a typical game object schema can grow quite large. This translates into a lot of data that must be specified by the game designer for each instance of each game object type he or she places into the game world. It can be extremely helpful to define default values in the schema for many of the attributes. This permits game designers to place “vanilla” instances of a game object type with little effort but still permits him or her to fine-tune the attribute values on specific instances as needed.

One inherent problem with default values arises when the default value of a particular attribute changes. For example, our game designers might have originally wanted Orcs to have 20 hit points. After many months of production, the designers might decide that Orcs should be more powerful and have 30 hit points by default. Any new Orcs placed into a game world will now have 30 hit points unless otherwise specified. But what about all the Orcs that were placed into game world chunks prior to the change? Do we need to find all of these previously created Orcs and manually change their hit points to 30?

Ideally, we’d like to design our spawner system so that changes in default values automatically propagate to all preexisting instances that have not had their default values overridden explicitly. One easy way to implement this feature is to simply omit key-value pairs for attributes whose value does not differ from the default value. Whenever an attribute is missing from the spawner, the appropriate default can be used. (This presumes that the game engine has access to the object type schema file, so that it can read in the attributes’ default values. Either that or the tool can do it—in which case, propagating new default values requires a simple rebuild of all world chunk(s) affected by the change.) In our example, most of the preexisting Orc spawners would have had no HitPoints key-value pair at all (unless of course one of the spawner’s hit points had been changed from the default value manually). So when the default value changes from 20 to 30, these Orcs will automatically use the new value.

Some engines allow default values to be overridden in derived object types. For example, the schema for a type called Vehicle might define a default TopSpeed of 80 miles per hour. A derived Motorcycle type schema could override this TopSpeed to be 100 miles per hour.

16.3.3.3 Some Beneifts of Spawners and Type Schemas

The key benefits of separating the spawner from the implementation of the game object are simplicity, flexibility and robustness. From a data management point of view, it is much simpler to deal with a table of key-value pairs than it is to manage a binary object image with pointer fix-ups or a custom serialized object format. The key-value pairs approach also makes the data format extremely flexible and robust to changes. If a game object encounters key-value pairs that it is not expecting to see, it can simply ignore them. Likewise, if the game object is unable to find a key-value pair that it needs, it has the option of using a default value instead. This makes a key-value pair data format extremely robust to changes made by both the designers and the programmers.

Spawners also simplify the design and implementation of the game world editor, because it only needs to know how to manage lists of key-value pairs and object type schemas. It doesn’t need to share code with the runtime game engine in any way, and it is only very loosely coupled to the engine’s implementation details.

Spawners and archetypes give game designers and programmers a great deal of flexibility and power. Designers can define new game object type schemas within the world editor with little or no programmer intervention. The programmer can implement the runtime implementation of these new object types whenever his or her schedule allows it. The programmer does not need to immediately provide an implementation of each new object type as it is added in order to avoid breaking the game. New object data can exist safely in the world chunk files with or without a runtime implementation, and runtime implementations can exist with or without corresponding data in the world chunk file.

16.4.3.1 Determining Which Resources to Load

One question that arises when using a fine-grained chunky memory allocator for world streaming is how the engine will know what resources to load at any given moment during gameplay. In the Naughty Dog engine, we use a relatively simple system of level load regions to control the loading and unloading of assets.

All of the Uncharted and The Last of Us games are set in multiple, geographically distinct, contiguous game worlds. For example, Uncharted: Drake’s Fortune takes place in a jungle and on an island. Each of these worlds exists in a single, consistent world space, but they are divided up into numerous geographically adjacent chunks. A simple convex volume known as a region encompasses each of the chunks; the regions overlap each other somewhat. Each region contains a list of the world chunks that should be in memory when the player is in that region.

At any given moment, the player is within one or more of these regions. To determine the set of world chunks that should be in memory, we simply take the union of the chunk lists from each of the regions enclosing the Nathan Drake character. The level loading system periodically checks this master chunk list and compares it against the set of world chunks that are currently in memory. If a chunk disappears from the master list, it is unloaded, thereby freeing up all of the allocation blocks it occupied. If a new chunk appears in the list, it is loaded into any free allocation blocks that can be found. The level load regions and world chunks are designed in such a way as to ensure that the player never sees a chunk disappear when it is unloaded and that there’s enough time between the moment at which a chunk starts loading and the moment its contents are first seen by the player to permit the chunk to be fully streamed into memory. This technique is illustrated in Figure 16.12.

16.4.3.2 PlayGo on the PlayStation 4

The PlayStation 4 includes a new feature called PlayGo that makes the process of downloading a game (as opposed to buying it on Blu-ray) a lot less painful than it has traditionally been. PlayGo works by downloading only the minimum subset of data required in order to play the first section of the game. The PS4 downloads the rest of the game’s content in the background, while the player continues to experience the game without interruption. In order for this to work well, the game must of course support seamless level streaming, as we’ve described above.

16.4.4.1 OffLine Memory Allocation for Object Spawning

Some game engines solve the problems of allocation speed and memory fragmentation in a rather draconian way, by simply disallowing dynamic memory allocation during gameplay altogether. Such engines permit game world chunks to be loaded and unloaded dynamically, but they spawn in all dynamic game objects immediately upon loading a chunk. Thereafter, no game objects can be created or destroyed. You can think of this technique as obeying a “law of conservation of game objects.” No game objects are created or destroyed once a world chunk has been loaded.

This technique avoids memory fragmentation because the memory requirements of all the game objects in a world chunk are (a) known a priori and (b) bounded. This means that the memory for the game objects can be allocated offline by the world editor and included as part of the world chunk data itself. All game objects are therefore allocated out of the same memory used to load the game world and its resources, and they are no more prone to fragmentation than any other loaded resource data. This approach also has the benefit of making the game’s memory usage patterns highly predictable. There’s no chance that a large group of game objects is going to spawn into the world unexpectedly, and cause the game to run out of memory.

On the downside, this approach can be quite limiting for game designers. Dynamic object spawning can be simulated by allocating a game object in the world editor but instructing it to be invisible and dormant when the world is first loaded. Later, the object can “spawn” by simply activating itself and making itself visible. But the game designers have to predict the total number of game objects of each type that they’ll need when the game world is first created in the world editor. If they want to provide the player with an infinite supply of health packs, weapons, enemies or some other kind of game object, they either need to work out a way to recycle their game objects, or they’re out of luck.

16.4.4.2 Dynamic Memory Management for Object Spawning

Game designers would probably prefer to work with a game engine that supports true dynamic object spawning. Although this is more difficult to implement than a static game object spawning approach, it can be implemented in a number of different ways.

Again, the primary problem is memory fragmentation. Because different types of game objects (and sometimes even different instances of the same type of object) occupy different amounts of memory, we cannot use our favorite fragmentation-free allocator—the pool allocator. And because game objects are generally destroyed in a different order than that in which they were spawned, we cannot use a stack-based allocator either. Our only choice appears to be a fragmentation-prone heap allocator. Thankfully, there are many ways to deal with the fragmentation problem. We’ll investigate a few common ones in the following sections.

16.4.5.1 Checkpoints

One approach to save games is to limit saves to specific points in the game, known as checkpoints. The benefit of this approach is that most of the knowledge about the state of the game is saved in the current world chunk(s) in the vicinity of each checkpoint. This data is always exactly the same, no matter which player is playing the game, so it needn’t be stored in the saved game. As a result, saved game files based on checkpoints can be extremely small. We might need to store only the name of the last checkpoint reached, plus perhaps some information about the current state of the player character, such as the player’s health, number of lives remaining, what items he has in his inventory, which weapon(s) he has and how much ammo each one contains. Some games based on checkpoints don’t even store this information—they start the player off in a known state at each checkpoint. Of course, the downside of a game based on checkpoints is the possibility of user frustration, especially if checkpoints are few and far between.

16.4.5.2 Save Anywhere

Some games support a feature known as save anywhere. As the name implies, such games permit the state of the game to be saved at literally any point during play. To implement this feature, the size of the saved game data file must increase significantly. The current locations and internal states of every game object whose state is relevant to gameplay must be saved and then restored when the game is loaded again later.

In a save-anywhere design, a saved game data file contains basically the same information as a world chunk, minus the world’s static components. It is possible to utilize the same data format for both systems, although there may be factors that make this infeasible. For example, the world chunk data format might be designed for flexibility, but the saved game format might be compressed to minimize the size of each saved game.

As we’ve mentioned, one way to reduce the amount of data that needs to be stored in a saved game file is to omit certain irrelevant game objects and to omit some irrelevant details of others. For example, we needn’t remember the exact time index within every animation that is currently playing or the exact momentums and velocities of every physically simulated rigid body. We can rely on the imperfect memories of human gamers and save only a rough approximation to the game’s state.

16.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 GameObjectManager. 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.

16.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 S_i(t) given its previous state S_i(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)
 {
 PollJoypad();
 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.

16.6.3.1 Phased Updates

To account for inter-subsystem dependencies, we can explicitly code our engine subsystem updates in the proper order within the main game loop. For example, to handle the interplay between the animation system and rag doll physics, we might write something like this:

while (true) // main game loop
 {
 // …
 g_animationEngine.CalculateIntermediatePoses(dt);
 g_ragdollSystem.ApplySkeletonsToRagDolls();
 g_physicsEngine.Simulate(dt); // runs ragdolls too
 g_collisionEngine.DetectAndResolveCollisions(dt);
 g_ragdollSystem.ApplyRagDollsToSkeletons();
 g_animationEngine.FinalizePoseAndMatrixPalette();
 // …
 }

We must be careful to update the states of our game objects at the right time during the game loop. This is often not as simple as calling a single Update() function per game object per frame. Game objects may depend upon the intermediate results of calculations performed by various engine subsystems. For example, a game object might request that animations be played prior to the animation system running its update. However, that same object may also want to procedurally adjust the intermediate pose generated by the animation system prior to that pose being used by the rag doll physics system and/or the final pose and matrix palette being generated. This implies that the object must be updated twice, once before the animation calculates its intermediate poses and once afterward.

Many game engines allow their game objects to run update logic at multiple points during the frame. For example, the Naughty Dog engine (the engine that drives the Uncharted and The Last of Us game series) updates game objects three times—once before animation blending, once after animation blending but prior to final pose generation and once after final pose generation. This can be accomplished by providing each game object class with three virtual functions that act as “hooks.” In such a system, the game loop ends up looking something like this:

while (true) // main game loop
 {
 // …
 for (each gameObject)
 {
 gameObject.PreAnimUpdate(dt);
 }
 g_animationEngine.CalculateIntermediatePoses(dt);
 for (each gameObject)
 {
 gameObject.PostAnimUpdate(dt);
 }
 g_ragdollSystem.ApplySkeletonsToRagDolls();
 g_physicsEngine.Simulate(dt); // runs ragdolls too
 g_collisionEngine.DetectAndResolveCollisions(dt);
 g_ragdollSystem.ApplyRagDollsToSkeletons();
 g_animationEngine.FinalizePoseAndMatrixPalette();
 for (each gameObject)
 {
 gameObject.FinalUpdate(dt);
 }
 // …
 }

We can provide our game objects with as many update phases as we see fit. But we must be careful, because iterating over all game objects and calling a virtual function on each one can be expensive. Also, not all game objects require all update phases—iterating over objects that don’t require a particular phase is a pure waste of CPU bandwidth.

Actually, the above example isn’t completely realistic. Iterating directly over all game objects to call their PreAnimUpdate(), PostAnimUpdate() and FinalUpdate() hook functions would be highly inefficient, because only a small percentage of the objects might actually need to perform any logic in each hook. It’s also an inflexible design, because only game objects are supported—if we wanted to update a particle system during the postanimation phase, we’d be out of luck. Finally, such a design would lead to unnecessary coupling between the low-level engine systems and the game object system.

A generic callback mechanism would be a much better design choice. In such a design, the animation system would provide a facility by which any client code (game objects or any other engine system) could register a callback function for each of the three update phases (pre-animation, post-animation and final). The animation system would iterate through all registered callbacks and call them, without any “knowledge” of game objects per se. This design maximizes performance, because only those clients that actually need updates register callbacks and are called each frame. It also maximizes flexibility and eliminates unnecessary coupling between the game object system and other engine subsystems, because any client is allowed to register a callback, not just game objects.

16.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 16.14.

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:

enum Bucket
 {
 kBucketVehiclesPlatforms,
 kBucketCharacters,
 kBucketAttachedObjects,
 kBucketCount
 };
 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); // ragdolls etc.
 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(kBucketVehiclesAndPlatforms);
 UpdateBucket(kBucketCharacters);
 UpdateBucket(kBucketAttachedObjects);
 // …
 g_renderingEngine.RenderSceneAndSwapBuffers();
 }
 }

In practice, things might be 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 all of the games in the Uncharted series as well as The Last of Us. So it’s a method that has proven to be practical and reasonably efficient.

16.6.3.3 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 16.6 that the state of game object i at time t can be denoted by a state vector S_i(t). When we update a game object, we are converting its previous state vector S_i(t₁) into a new current state vector S_i(t₂) (where t₂ = t₁ + Δt).

In theory, the states of all game objects are updated from time t₁ to time t₂ instantaneously and in parallel, as depicted in Figure 16.15. However, presuming that our game update loop is single-threaded, we actually update the objects one by one—we loop over each game object and call some kind of update function on each one in turn. If we were to stop the program halfway through this update loop, half of our game objects’ states would have been updated to S_i(t₂), while the remaining half would still be in their previous states S_i(t₁). 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:

This is illustrated in Figure 16.16.

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 often 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, S_A (t₁), or the new state, S_A (t₂). 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.

16.6.3.4 Object State Caching

As described above, one solution to this problem is to group the game objects into buckets (Section 16.6.3.2). 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 S_B(t₂) of another object B, then object B must reside in a previously updated bucket. Likewise, if object A wants the previous state vector S_B(t₁) 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. Or at best, there’s some uncertainty as to whether you’re accessing the other object’s state at time t₁ or time t₂.

One way to improve consistency is to arrange for each game object to cache its previous state vector S_i(t₁) while it is calculating its new state vector S_i(t₂) 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 (S_i(t₁)) 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 t₁ are fully consistent, the new states at time t₂ still suffer from potential inconsistency. Nonetheless, the technique can be useful when applied judiciously.

This technique is influenced strongly by the design principles of pure functional programming (see Section 16.9.2). In a pure functional programming language, all operations are performed by functions with a clear input and output, and no side-effects. All data is considered constant and immutable—rather than mutating an input datum in place, a brand new datum is always produced.

16.6.3.5 Time-Stamping

One easy and low-cost way to improve the consistency of game object states is to time-stamp them. It is then a trivial matter to determine whether a game object’s state vector corresponds to its configuration at a previous time or the current time. Any code that queries the state of another game object during the update loop can assert or explicitly check the time stamp to ensure that the proper state information is being obtained.

Time-stamping does not address the inconsistency of states during the update of a bucket. However, we can set a global or static variable to reflect which bucket is currently being updated. Presumably every game object “knows” in which bucket it resides. So we can check the bucket of a queried game object against the currently updating bucket and assert that they are not equal in order to guard against inconsistent state queries.

16.7.2.1 When to Make Asynchronous Requests

One particularly tricky aspect of converting synchronous, unbatched code to use an asynchronous, batched approach is determining when during the game loop (a) to kick off the request and (b) to wait for and utilize the results. In doing this, it is often helpful to ask ourselves the following questions:

16.7.4.1 Game Object Updates as Jobs

If our game engine has a job system, it will very likely be used to parallelize the various low-level subsystems in our engine, such as animation, audio, collsion/physics, rendering, file I/O, and so on. So why not parallelize our game object updates by making them jobs, too? This is the approach used in the Naughty Dog engine. It works, but getting it to work correctly, and efficiently, is a non-trivial undertaking.

We discussed in Section 16.6.3.2 that, due to interdependencies between game objects, we need to control the order in which they update. One way to achieve this is to divide all of the objects in the game into N buckets, such that the objects in bucket B depend only on objects in buckets 0 through B − 1. If we take this approach, we could update all the game objects in each bucket by kicking them off as jobs, and let the job system schedule them across the available cores (and interspersed with whatever other jobs happen to be running at the time). This is roughly the technique employed in the Naughty Dog engine.

void UpdateBucket(int iBucket)
 {
 job::Declaration aDecl[kMaxObjectsPerBucket];
 const int count = GetNumObjectsInBucket(iBucket);
 for (int jObject = 0; jObject < count; ++jObject)
 {
 job::Declaration& decl = aDecl[jObject];
 decl.m_pEntryPoint = UpdateGameObjectJob;
 decl.m_param = reinterpret_cast<uintptr_t>(
 GetGameObjectInBucket(iBucket, jObject));
 }
 job::KickJobsAndWait(aDecl, count);
 }

Another way to deal with inter-object dependencies is to make them explicit. In this case, we would presumably have some way of declaring that game object A depends on game objects B, C and D, for example. These dependencies would form a simple directed graph. To update the game objects, we’d start by kicking off update jobs for all of the game objects with no dependencies on any other game object (i.e., those nodes of the dependency graph with no outgoing edges). As each job completes, we would walk to each dependent game object, and wait until all of its dependent objects’ update jobs are complete. This process would repeat until the entire graph of game objects has been updated.

We can get into trouble with a graph of game object dependencies if the graph contains any cycles. A dependency cycle involving two or more game objects indicates that those objects cannot simply be updated in dependency order. To handle cycles, we either need to eliminate them by changing the way the objects interact (turning our graph into a directed acyclic graph or DAG), or we need to isolate these “clumps” of cyclically-dependent game objects and update each clump serially on a single core.

16.7.4.2 Asynchronous Game Object Updates

We said in Section 16.7.1 that game object updates are usually done asynchronously. For example, rather than calling a blocking function to cast a ray, we would kick off an asynchronous request for a ray cast, and the collision subsystem would process this request at some future time during the frame. Later in the frame, or next frame, we would pick up the results of the ray cast, and act on them.

This approach continues to work well when the game objects themselves are also updating concurrently (across multiple cores). However, if our job system is based on user-level threads (coroutines or fibers), then blocking calls become a viable option, too. This works because a coroutine has the unique property of being able to yield (to another coroutine) and then continue where it left off at some later time (when another coroutine yields back to it). In a fiber-based job system (like the one used in the Naughty Dog engine), jobs aren’t coroutines per se, but they do have this same property: A fiber-based job is able to “go to sleep” midway through its execution, and later to be “woken up” to continue execution where it left off.

Here’s an example ray cast implemented using a blocking call, in a coroutine- or fiber-based job system:

SomeGameObject::Update()
 {
 // …
 // Cast a ray to see if the player has line of sight
 // to the enemy.
 RayCastResult r = castRayAndWait(playerPos, enemyPos);
 // zzz…
 // Wake up when ray cast result is ready!
 // Now process the results…
 if (r.hitSomething() && isEnemy(r.getHitObject()))
 {
 // Player can see the enemy.
 // …
 }
 // …
 }

Notice that this implementation looks nearly identical to the example of what not to do that we presented in Section 16.7.2! Thanks to user-level threads, the execution of our job can make use of blocking function calls after all! Figure 16.20 illustrates what is happening: The job has effectively been cleaved into two parts—the portion that runs before the blocking ray cast call, and the portion that runs after.

This mechanism is what allows us to implement job system functions like WaitForCounter() KickJobsAndWait(). These functions block their jobs, putting them to sleep and permitting other jobs to execute while they wait for the counter(s) in question to hit zero.

16.7.4.3 Locking During Game Object Updates

Bucketed updates go a long way to solving the problems that arise due to inter-object dependencies. They ensure that the game objects are updated in the correct global order (e.g., the train car updates before the objects sitting on it). And they help with inter-object state queries. An object in bucket B can safely query the state of objects in buckets B − Δ, and those in buckets B + Δ (where Δ > 0), because in both cases we know that those objects won’t be updating concurrently with the objects in bucket B. There is still a one-frame-off issue, however: If on frame N, an object in bucket B queries an object in bucket B − Δ, it will see the state of that object on frame N; however, if it queries an object in bucket B + Δ, it will see the state of that object as it was last frame (on frame N − 1) because it won’t have updated yet.

So, with a bucketed updating system, we can safely access game objects in other buckets without needing any kind of lock. However, what about when game objects in the same bucket need to interact or query one another? Here, we are once again prone to concurrent race conditions, so we can’t just do nothing and cross our fingers.

We might be tempted to introduce a single, global lock (mutex or spin lock) into the game object system. Every game object within one particular bucket could acquire this lock, perform its update (possibly interacting with other game objects in the process), and then release the lock when it’s done. This would certainly guarantee that inter-object communication would be free from data races. However, it would also have the highly undesirable effect of serializing the updates of all game objects within the bucket, reducing our “concurrent” game object update in effect to a single-threaded update! This occurs because the lock would prevent any two game objects from ever updating concurrently, even when those two objects don’t interact in any way.

There are all sorts of other ways to tackle this problem. One approach we tried early on at Naughty Dog was to introduce a global locking system, but to only acquire the lock whenever a game object handle was dereferenced within a game object’s update function. Game objects in our engine are referenced by handle rather than by raw pointers, to support memory defragmentation. So to get a raw pointer to a game object, one must first dereference its handle. This is a perfect opportunity to detect that one game object intends to interact with another. By only taking locks when interactions are actually likely to happen, we were able to recover some degree of concurrency. However, this locking system was complex, difficult to work with, and still led to inefficient use of the CPU cores during bucket updates.

16.7.4.4 Object Snapshots

Upon analyzing the inter-dependencies between the game objects in a real game engine, we can make an observation: A large majority of the interactions between game objects during their updates are state queries. In other words, game object A reaches out and queries the current state of game objects B, C, and so on. When game object A does this, it really only needs to have access to a read-only copy of the states of these other game objects. It needn’t interact with the objects themselves (which might or might not be concurrently updating at the moment of such interactions).

Given this state of affairs, it makes sense to arrange for each game object to provide a snapshot of its relevant state information—a read-only copy which can be queried, without locks or fear of data races, by any other game object in the system. Snapshots are really just an example of the state caching technique we described in Section 16.6.3.4. We used this approach at Naughty Dog for The Last of Us: Remastered, Uncharted 4: A Thief’s End and Uncharted: The Lost Legacy.

Here’s how snapshots work in the Naughty Dog engine: At the start of each bucket update, we ask each game object to update its snapshot. These updates never query the state of other game objects, so they can be run concurrently without locks. Once all updates are complete, we kick off concurrent jobs to update the game objects’ internal states. These too run concurrently.

Whenever a game object in bucket B needs to query the state of another object, it now has three options:

16.7.4.5 Handling Inter-Object Mutation

Snapshots allow us to avoid locks when game objects read one another’s game state. However, they do nothing to address the data races that can occur when one game object needs to mutate the state of another object in the same bucket. To handle these situations, Naughty Dog applied a combination of the following rules of thumb and techniques:

Another option for inter-object mutation within a single bucket is to spawn a job in the next bucket whose job it is to synchronize these mutation operations. By deferring the action to a later bucket, we can be certain that the objects in question have completed their updated and will not be updating concurrently with our work. We did this at Naughty Dog to handle synchronized melee moves involving the player and an NPC.

16.7.4.6 Future Improvements

The bucketed updating system we’ve described in this section isn’t perfect by any means. Bucketed updates aren’t as efficient as they could be, because each transition between buckets introduces a sync point into the game loop. At these sync points, some CPU cores may sit idle while we wait for all game objects in the bucket to complete their updates.

Snapshotting is also an imperfect solution to within-bucket dependency problems, because it only handles read-only queries; locks are still required for inter-object mutations. The snapshots themselves can be expensive to update as well (although one easy-to-apply optimization here is to only generate snapshots for objects on an as-needed basis).

There are lots of other ways to tackle these problems. The best way to discover how to update game objects concurrently is to experiment. Hopefully we’ve presented some useful ideas in this section that will pave the way forward as you experiment for yourself!

16.8.4.1 Event Arguments as Key-Value Pairs

A fundamental problem with an indexed collection of event arguments is order dependency. Both the sender and the receiver of an event must “know” that the arguments are listed in a specific order. This can lead to confusion and bugs. For example, a required argument might be accidentally omitted or an extra one added.

This problem can be avoided by implementing event arguments as key-value pairs. Each argument is uniquely identified by its key, so the arguments can appear in any order, and optional arguments can be omitted altogether. The argument collection might be implemented as a closed or open hash table, with the keys used to hash into the table, or it might be an array, linked list or binary search tree of key-value pairs. These ideas are illustrated in Table 16.1. The possibilities are numerous, and the specific choice of implementation is largely unimportant as long as the game’s particular requirements have been effectively and efficiently met.

16.8.9.1 Some Benefits of Event Queuing

The following sections outline some of the benefits of event queuing.

// This function is called at least once per frame. Its
 // job is to dispatch all events whose delivery time is
 // now or in the past.
 void EventQueue::DispatchEvents(F32 currentTime)
 {
 // Look at, but don’t remove, the next event on the
 // queue.
 Event* pEvent = PeekNextEvent();
 while (pEvent
 && pEvent->GetDeliveryTime() <= currentTime)
 {
 // Remove the event from the queue.
 RemoveNextEvent();
 // Dispatch it to its receiver’s event handler.
 pEvent->Dispatch();
 // Peek at the next event on the queue (again
 // without removing it).
 pEvent = PeekNextEvent();
 }
 }

16.8.9.2 Some Problems with Event Queuing

void SendExplosionEventToObject(GameObject& receiver)
 {
 // Allocate event args on the call stack.
 Point centerPoint(-2.0f, 31.5f, 10.0f);
 F32 damage = 5.0f;
 F32 radius = 2.0f;
 // Allocate the event on the call stack.
 Event event(“Explosion”);
 event.SetArgFloat(“Damage”, damage);
 event.SetArgPoint(“Center”, &centerPoint);
 event.SetArgFloat(“Radius”, radius);
 // Send the event, which causes the receiver’s event
 // handler to be called immediately, as shown below.
 event.Send(receiver);
 //{
 // receiver.OnEvent(event);
 //}
 }

void SendExplosionEventToObject(GameObject& receiver)
 {
 // We can still allocate event args on the call
 // stack.
 Point centerPoint(-2.0f, 31.5f, 10.0f);
 F32 damage = 5.0f;
 F32 radius = 2.0f;
 // Still OK to allocate the event on the call stack
 Event event(“Explosion
 event.SetArgFloat(“Damage”, damage);
 event.SetArgPoint(“Center”, &centerPoint);
 event.SetArgFloat(“Radius”, radius);
 // This stores the event in the receiver’s queue for
 // handling at a future time. Note how the event
 // must be deep-copied prior to being enqueued, since
 // the original event resides on the call stack and
 // will go out of scope when this function returns.
 event.Queue(receiver);
 //{
 // Event* pEventCopy = DeepCopy(event);
 // receiver.EnqueueEvent(pEventCopy);
 //}
 }

while (true) // main game loop
 {
 // …
 // Update animation clocks. This may detect the end
 // of a clip, and cause EndOfAnimation events to
 // be sent.
 g_animationEngine.UpdateLocalClocks(dt);
 // Next, dispatch events. This allows an
 // EndOfAnimation event handler to start up a new
 // animation this frame if desired.
 g_eventSystem.DispatchEvents();
 // Finally, start blending all currently playing
 // animations (including any new clips started
 // earlier this frame).
 g_animationEngine.StartAnimationBlending();
 // …
 }

16.8.11.1 Data Pathway Communication Systems

One of the problems with converting a function-call-like event system into a data-driven system is that different types of events tend to be incompatible. For example, let’s imagine a game in which the player has an electromagnetic pulse gun. This pulse causes lights and electronic devices to turn off, scares small animals and produces a shock wave that causes any nearby plants to sway. Each of these game object types may already have an event response that performs the desired behavior. A small animal might respond to the “Scare” event by scurrying away. An electronic device might respond to the “TurnOff” event by turning itself off. And plants might have an event handler for a “Wind” event that causes them to sway. The problem is that our EMP gun is not compatible with any of these objects’ event handlers. As a result, we end up having to implement a new event type, perhaps called “EMP,” and then write custom event handlers for every type of game object in order to respond to it.

One solution to this problem is to take the event type out of the equation and to think solely in terms of sending streams of data from one game object to another. In such a system, every game object has one or more input ports to which a data stream can be connected, and one or more output ports through which data can be sent to other objects. Provided we have some way of wiring these ports together, such as a graphical user interface in which ports can be connected to each other via rubber-band lines, then we can construct arbitrarily complex behaviors. Continuing our example, the EMP gun would have an output port, perhaps named “Fire,” that sends a Boolean signal. Most of the time, the port produces the value 0 (false), but when the gun is fired, it sends a brief (one-frame) pulse of the value 1 (true). The other game objects in the world have binary input ports that trigger various responses. The animals might have a “Scare” input, the electronic devices a “TurnOn” input and the foliage objects a “Sway” input. If we connect the EMP gun’s “Fire” output port to the input ports of these game objects, we can cause the gun to trigger the desired behaviors. (Note that we’d have to pipe the gun’s “Fire” output through a node that inverts its input, prior to connecting it to the “TurnOn” input of the electronic devices. This is because we want them to turn off when the gun is firing.) The wiring diagram for this example is shown in Figure 16.22.

Programmers decide what kinds of port(s) each type of game object will have. Designers using the GUI can then wire these ports together in arbitrary ways in order to construct arbitrary behaviors in the game. The programmers also provide various other kinds of nodes for use within the graph, such as a node that inverts its input, a node that produces a sine wave or a node that outputs the current game time in seconds.

Various types of data might be sent along a data pathway. Some ports might produce or expect Boolean data, while others might be coded to produce or expect data in the form of a unit float. Still others might operate on 3D vectors, colors, integers and so on. It’s important in such a system to ensure that connections are only made between ports with compatible data types, or we must provide some mechanism for automatically converting data types when two differently typed ports are connected together. For example, connecting a unit-float output to a Boolean input might automatically cause any value less than 0.5 to be converted to false, and any value greater than or equal to 0.5 to be converted to true. This is the essence of GUI-based event systems like Unreal Engine 4’s Blueprints. A screenshot of Blueprints is shown in Figure 16.23.

16.8.11.2 Some Pros and Cons of GUI-Based Programming

The benefits of a graphical user interface over a straightforward, text-file-based scripting language are probably pretty obvious: ease of use, a gradual learning curve with the potential for in-tool help and tool tips to guide the user, and plenty of error-checking. The downsides of a flowchart style GUI include the high cost to develop, debug, and maintain such a system, the additional complexity, which can lead to annoying or sometimes schedule-killing bugs, and the fact that designers are sometimes limited in what they can do with the tool. A text-file-based programming language has some distinct advantages over a GUI-based programming system, including its relative simplicity (meaning that it is much less prone to bugs), the ability to easily search and replace within the source code, and the freedom of each user to choose the text editor with which they are most comfortable.

16.9.2.1 Typical Characteristics of Game Scripting Languages

The characteristics that set a game scripting language apart from its native programming language brethren include:

16.9.3.1 QuakeC

Id Software’s John Carmack implemented a custom scripting language for Quake, known as QuakeC (QC). This language was essentially a simplified variant of the C programming language with direct hooks into the Quake engine. It had no support for pointers or defining arbitrary structs, but it could manipulate entities (Quake’s name for game objects) in a convenient manner, and it could be used to send and receive/handle game events. QuakeC is an interpreted, imperative, procedural programming language.

The power that QuakeC put into the hands of gamers is one of the factors that gave birth to what is now known as the mod community. Scripting languages and other forms of data-driven customization allow gamers to turn many commercial games into all sorts of new gaming experiences—from slight modifications on the original theme to entirely new games.

16.9.3.2 UnrealScript

Probably the best-known example of an entirely custom scripting language is Unreal Engine’s UnrealScript. This language is based on a C++-like syntactical style, and it supports most of the concepts that C and C++ programmers have become accustomed to, including classes, local variables, looping, arrays and structs for data organization, strings, hashed string ids (called FName in Unreal) and object references (but not free-form pointers). UnrealScript is an interpreted, imperative, object-oriented language.

Epic no longer supports the UnrealScript language. Instead, developers customize game behavior either via the Blueprints graphical “scripting” system, or by writing C++ code.

16.9.3.3 Lua

Lua is a well-known and popular scripting language that is easy to integrate into an application such as a game engine. The Lua website (http://www.lua.org/about.html) calls the language the “leading scripting language in games.”

According to the Lua website, Lua’s key benefits are:

Lua is a dynamically typed language, meaning that variables don’t have types—only values do. (Every value carries its type information along with it.) Lua’s primary data structure is the table, also known as an associative array. A table is essentially a list of key-value pairs with an optimized ability to index into the array by key.

Lua provides a convenient interface to the C language—the Lua virtual machine can call and manipulate functions written in C as easily as it can those written in Lua itself.

Lua treats blocks of code, called chunks, as first-class objects that can be manipulated by the Lua program itself. Code can be executed in source code format or in precompiled byte code format. This allows the virtual machine to execute a string that contains Lua code, just as if the code were compiled into the original program. Lua also supports some powerful advanced programming constructs, including coroutines. This is a simple form of cooperative multitasking, in which each thread must yield the CPU to other threads explicitly (rather than being time-sliced as in a preemptive multithreading system).

Lua does have some pitfalls. For example, its flexible function binding mechanism makes it possible (and quite easy) to redefine an important global function like sin() to perform a totally different task (which is usually not something one intends to do). But all in all, Lua has proven itself to be an excellent choice for use as a game scripting language.

16.9.3.4 Python

Python is a procedural, object-oriented, dynamically typed scripting language designed with ease of use, integration with other programming languages, and flexibility in mind. Like Lua, Python is a common choice for use as a game scripting language. According to the official Python website (http://www.python.org), some of Python’s best features include

Python syntax is reminiscent of C in many respects (for example, its use of the = operator for assignment and == for equality testing). However, in Python, code indentation serves as the only means of defining scope (as opposed to C’s opening and closing braces). Python’s primary data structures are the list—a linearly indexed sequence of atomic values or other nested lists—and the dictionary—a table of key-value pairs. Each of these two data structures can hold instances of the other, allowing arbitrarily complex data structures to be constructed easily. In addition, classes—unified collections of data elements and functions—are built right into the language.

Python supports duck typing, which is a style of dynamic typing in which the functional interface of an object determines its type (rather than being defined by a static inheritance hierarchy). In other words, any class that supports a particular interface (i.e., a collection of functions with specific signatures) can be used interchangeably with any other class that supports that same interface. This is a powerful paradigm: In effect, Python supports polymorphism without requiring the use of inheritance. Duck typing is similar in some respects to C++ template metaprogramming, although it is arguably more flexible because the bindings between caller and callee are formed dynamically, at runtime. Duck typing gets its name from the well-known phrase (attributed to James Whitcomb Riley), “If it walks like a duck and quacks like a duck, I would call it a duck.” See http://en.wikipedia.org/wiki/Duck_typing for more information on duck typing.

In summary, Python is easy to use and learn, embeds easily into a game engine, integrates well with a game’s object model, and can be an excellent and powerful choice as a game scripting language.

16.9.3.5 Pawn/Small/Small-C

Pawn is a lightweight, dynamically typed, C-like scripting language created by Marc Peter. The language was formerly known as Small, which itself was an evolution of an earlier subset of the C language called Small-C, written by Ron Cain and James Hendrix. It is an interpreted language—the source code is compiled into byte code (also known as P-code), which is interpreted by a virtual machine at runtime.

Pawn was designed to have a small memory footprint and to execute its byte code very quickly. Unlike C, Pawn’s variables are dynamically typed. Pawn also supports finite state machines, including state-local variables. This unique feature makes it a good fit for many game applications. Good online documentation is available for Pawn (http://www.compuphase.com/pawn/pawn.htm). Pawn is open source and can be used free of charge under the Zlib/libpng license (http://www.opensource.org/licenses/zlib-license.php).

Pawn’s C-like syntax makes it easy to learn for any C/C++ programmer and easy to integrate with a game engine written in C. Its finite state machine support can be very useful for game programming. It has been used successfully on a number of game projects, including Freaky Flyers by Midway. Pawn has shown itself to be a viable game scripting language.

16.9.5.1 Interface with the Native Programming Language

In order for a scripting language to be useful, it must not operate in a vacuum. It’s imperative for the game engine to be able to execute script code, and it’s usually equally important for script code to be capable of initiating operations within the engine as well.

A runtime scripting language’s virtual machine (VM) is generally embedded within the game engine. The engine initializes the virtual machine, runs script code whenever required, and manages those scripts’ execution. The unit of execution varies depending on the specifics of the language and the game’s implementation.

It’s usually beneficial to allow two-way communication between script and native code. Therefore, most scripting languages allowing native code to be invoked from script as well. The details are language- and implementation-specific, but the basic approach is usually to allow certain script functions to be implemented in the native language rather than in the scripting language. To call an engine function, script code simply makes an ordinary function call. The virtual machine detects that the function has a native implementation, looks up the corresponding native function’s address (perhaps by name or via some other kind of unique function identifier), and calls it. For example, some or all of the member functions of a Python class or module can be implemented using C functions. Python maintains a data structure, known as a method table, that maps the name of each Python function (represented as a string) to the address of the C function that implements it.

 void DcExecuteScript(DCByteCode* pCode)
 {
 DCStackFrame* pCurStackFrame
 = DcPushStackFrame(pCode);
 // Keep going until we run out of stack frames (i.e.,
 // the top-level script lambda “function” returns).
 while (pCurStackFrame != nullptr)
 {
 // Get the next instruction. We will never run
 // out, because the return instruction is always
 // last, and it will pop the current stack frame
 // below.
 DCInstruction& instr
 = pCurStackFrame->GetNextInstruction();
 // Perform the operation of the instruction.
 switch (instr.GetOperation())
 {
 case DC_LOAD_REGISTER_IMMEDIATE:
 {
 // Grab the immediate value to be loaded
 // from the instruction.
 Variant& data = instr.GetImmediateValue();
 // Also determine into which register to
 // put it.
 U32 iReg = instr.GetDestRegisterIndex();
 // Grab the register from the stack frame.
 Variant& reg
 = pCurStackFrame->GetRegister(iReg);
 // Store the immediate data into the
 // register.
 reg = data;
 }
 break;
 // Other load and store register operations…
 case DC_ADD_REGISTERS:
 {
 // Determine the two registers to add. The
 // result will be stored in register A. U32 iRegA = instr.GetDestRegisterIndex();
 U32 iRegB = instr.GetSrcRegisterIndex();
 // Grab the 2 register variants from the
 // stack.
 Variant& dataA
 = pCurStackFrame->GetRegister(iRegA);
 Variant& dataB
 = pCurStackFrame->GetRegister(iRegB);
 // Add the registers and store in
 // register A.
 dataA = dataA + dataB;
 }
 break;
 // Other math operations…
 case DC_CALL_SCRIPT_LAMBDA:
 {
 // Determine in which register the name of
 // the script lambda to call is stored.
 // (Presumably it was loaded by a previous
 // load instr.)
 U32 iReg = instr.GetSrcRegisterIndex();
 // Grab the appropriate register, which
 // contains the name of the lambda to call.
 Variant& lambda
 = pCurStackFrame->GetRegister(iReg);
 // Look up the byte code of the lambda by
 // name.
 DCByteCode* pCalledCode
 = DcLookUpByteCode(lambda.AsStringId());
 // Now “call” the lambda by pushing a new
 // stack frame.
 if (pCalledCode)
 {
 pCurStackFrame
 = DcPushStackFrame(pCalledCode);
 }
 }
 break;
 case DC_RETURN:
 {
 // Just pop the stack frame. If we’re in
 // the top lambda on the stack, this
 // function will return nullptr, and the
 // loop will terminate.
 pCurStackFrame = DcPopStackFrame();
 }
 break;
 // Other instructions…
 // …
 } // end switch
 } // end while
 }

typedef Variant DcNativeFunction(U32 argCount,
 Variant* aArgs);
 struct DcNativeFunctionEntry
 {
 StringId  m_name;
 DcNativeFunction* m_pFunc;
 };
 DcNativeFunctionEntry g_aNativeFunctionLookupTable[] =
 {
 {SID(“get-object-pos”), DcGetObjectPos},
 {SID(“animate-object”), DcAnimateObject},
 // etc.
 };

Variant DcGetObjectPos(U32 argCount, Variant* aArgs)
 {
 // Argument iterator expecting at most 2 args.
 DcArgIterator args(argCount, aArgs, 2);
 // Set up a default return value.
 Variant result;
 result.SetAsVector(Vector(0.0f, 0.0f, 0.0f));
 // Use iterator to extract the args. It flags missing
 // or invalid arguments as errors automatically.
 StringId objectName = args.NextStringId();
 Point* pDefaultPos = args.NextPoint(kDcOptional);
 GameObject* pObject
 = GameObject::LookUpByName(objectName);
 if (pObject)
 {
 result.SetAsVector(pObject->GetPosition());
 }
 else
 {
 if (pDefaultPos)
 {
 result.SetAsVector(*pDefaultPos);
 }
 else
 {
 DcErrorMessage(“get-object-pos:”
 “Object ‘%s’ not found.
”,
 objectName.ToDebugString());
 }
 }
 return result;
 }

16.9.5.2 Game Object References

Script functions often need to interact with game objects, which themselves may be implemented partially or entirely in the engine’s native language. The native language’s mechanisms for referencing objects (e.g., pointers or references in C++) won’t necessarily be valid in the scripting language. (It may not support pointers at all, for example.) Therefore, we need to come up with some reliable way for script code to reference game objects.

There are a number of ways to accomplish this. One approach is to refer to objects in script via opaque numeric handles. The script code can obtain object handles in various ways. It might be passed a handle by the engine, or it might perform some kind of query, such as asking for the handles of all game objects within a radius of the player or looking up the handle that corresponds to a particular object name. The script can then perform operations on the game object by calling native functions and passing the object’s handle as an argument. On the native language side, the handle is converted back into a pointer to the native object, and then the object can be manipulated as appropriate.

Numeric handles have the benefit of simplicity and should be easy to support in any scripting language that supports integer data. However, they can be unintuitive and difficult to work with. Another alternative is to use the names of the objects, represented as strings, as our handles. This has some interesting benefits over the numeric handle technique. For one thing, strings are human-readable and intuitive to work with. There is a direct correspondence to the names of the objects in the game’s world editor. In addition, we can choose to reserve certain special object names and give them “magic” meanings. For example, in Naughty Dog’s scripting language, the reserved name “self” always refers to the object to which the currently running script is attached. This allows game designers to write a script, attach it to an object in the game, and then use the script to play an animation on the object by simply writing (animate ’self name-of-animation).

Using strings as object handles has its pitfalls, of course. Strings typically occupy more memory than integer ids. And because strings vary in length, dynamic memory allocation is required in order to copy them. String comparisons are slow. Script programmers are apt to make mistakes when typing the names of game objects, which can lead to bugs. In addition, script code can be broken if someone changes the name of an object in the game world editor but forgets to update the name of the object in script.

Hashed string ids overcome most of these problems by converting any strings (regardless of length) into an integer. In theory, hashed string ids enjoy the best of both worlds—they can be read by users just like strings, but they have the runtime performance characteristics of an integer. However, for this to work, your scripting language needs to support hashed string ids in some way. Ideally, we’d like the script compiler to convert our strings into hashed ids for us. That way, the runtime code doesn’t have to deal with the strings at all, only the hashed ids (except possibly for debugging purposes—it’s nice to be able to see the string corresponding to a hashed id in the debugger). However, this isn’t always possible in all scripting languages. Another approach is to allow the user to use strings in script and convert them into hashed ids at runtime, whenever a native function is called.

Naughty Dog’s DC scripting language leverages the concept of “symbols,” which are native to the Scheme programming language, to encode its string ids. Writing ’foo—or more verbosely, (quote foo)—in DC/Scheme corresponds to the string id SID(“foo”) in C++.

16.9.5.3 Receiving and Handling Events in Script

Events are a ubiquitous communication mechanism in most game engines. By permitting event handler functions to be written in script, we open up a powerful avenue for customizing the hard-coded behavior of our game.

Events are usually sent to individual objects and handled within the context of that object. Hence, scripted event handlers need to be associated with an object in some way. Some engines use the game object type system for this purpose—scripted event handlers can be registered on a per-object-type basis. This allows different types of game objects to respond in different ways to the same event but ensures that all instances of each type respond in a consistent and uniform way. The event handler functions themselves can be simple script functions, or they can be members of a class if the scripting language is object-oriented. In either case, the event handler is typically passed a handle to the particular object to which the event was sent, much as C++ member functions are passed the this pointer.

In other engines, scripted event handlers are associated with individual object instances rather than with object types. In this approach, different instances of the same type might respond differently to the same event.

There are all sorts of other possibilities, of course. For example, in Naughty Dog’s engine (used to create the Uncharted and The Last of Us series), scripts are objects in their own right. They can be associated with individual game objects, they can be attached to regions (convex volumes that are used to trigger game events), or they can exist as stand-alone objects in the game world. Each script can have multiple states (that is, scripts are finite state machines in the Naughty Dog engine). In turn, each state can have one or more event handler code blocks. When a game object receives an event, it has the option of handling the event in native C++. It also checks for an attached script object, and if one is found, the event is sent to that script’s current state. If the state has an event handler for the event, it is called. Otherwise, the script simply ignores the event.

16.9.5.4 Sending Events

Allowing scripts to handle game events that are generated by the engine is certainly a powerful feature. Even more powerful is the ability to generate and send events from script code either back to the engine or to other scripts.

Ideally, we’d like to be able not only to send predefined types of events from script but to define entirely new event types in script. Implementing this is trivial if event types are strings or string ids. To define a new event type, the script programmer simply comes up with a new event type name and types it into his or her script code. This can be a highly flexible way for scripts to communicate with one another. Script A can define a new event type and send it to Script B. If Script B defines an event handler for this type of event, we’ve implemented a simple way for Script A to “talk” to Script B. In some game engines, event- or message-passing is the only supported means of inter-object communication in script. This can be an elegant yet powerful and flexible solution.

16.9.5.5 Object-Oriented Scripting Languages

Some scripting languages are inherently object-oriented. Others do not support objects directly but provide mechanisms that can be used to implement classes and objects. In many engines, gameplay is implemented via an object-oriented game object model of some kind. So it makes sense to permit some form of object-oriented programming in script as well.

16.9.5.6 Scripted Finite State Machines

Many problems in game programming can be solved naturally using finite state machines (FSMs). For this reason, some engines build the concept of FSMs right into the core game object model. In such engines, every game object can have one or more states, and it is the states—not the game object itself—that contain the update function, event handler functions and so on. Simple game objects can be created by defining a single state, but more complex game objects have the freedom to define multiple states, each with a different update and event-handling behavior.

If your engine supports a state-driven game object model, it makes a lot of sense to provide finite state machine support in the scripting language as well. And of course, even if the core game object model doesn’t support finite state machines natively, one can still provide state-driven behavior by using a state machine on the script side. An FSM can be implemented in any programming language by using class instances to represent states, but some scripting languages provide tools especially for this purpose. An object-oriented scripting language might provide custom syntax that allows a class to contain multiple states, or it might provide tools that help the script programmer easily aggregate state objects together within a central hub object and then delegate the update and event-handling functions to it in a straightforward way. But even if your scripting language provides no such features, you can always adopt a methodology for implementing FSMs and follow those conventions in every script you write.

16.9.5.7 Multithreaded Scripts

It’s often useful to be able to execute multiple scripts in parallel. This is especially true on today’s highly parallelized hardware architectures. If multiple scripts can run at the same time, we are in effect providing parallel threads of execution in script code, much like the threads provided by most multitasking operating systems. Of course, the scripts may not actually run in parallel—if they are all running on a single CPU, the CPU must take turns executing each one. However, from the point of view of the script programmer, the paradigm is one of parallel programming.

Most scripting systems that provide parallelism do so via cooperative multitasking. This means that a script will execute until it explicitly yields to another script. This is in contrast with a preemptive multitasking approach, in which the execution of any script could be interrupted at any time to permit another script to execute.

One simple approach to cooperative multitasking in script is to permit scripts to explicitly go to sleep, waiting for something relevant to happen. A script might wait for a specified number of seconds to elapse, or it might wait until a particular event is received. It might wait until another thread of execution has reached a predefined synchronization point. Whatever the reason, whenever a script goes to sleep, it puts itself on a list of sleeping script threads and tells the virtual machine that it can start executing another eligible script. The system keeps track of the conditions that will wake up each sleeping script—when one of these conditions becomes true, the script or scripts waiting on the condition are woken up and allowed to continue executing.

To see how this works in practice, let’s look at an example of a multithreaded script. This script manages the animations of two characters and a door. The two characters are instructed to walk up to the door—each one might take a different, and unpredictable, amount of time to reach it. We’ll put the script’s threads to sleep while they wait for the characters to reach the door. Once they both arrive at the door, one of the two characters opens the door, which it does by playing an “open door” animation. Note that we don’t want to hard-code the duration of the animation into the script itself. That way, if the animators change the animation, we won’t have to go back and modify our script. So we’ll put the threads to sleep again while the wait for the animation to complete. A script that accomplishes this is shown below, using a simple C-like pseudocode syntax.

procedure DoorCinematic()
 {
 thread Guy1()
 {
 // Ask guy1 to walk to the door.
 CharacterWalkToPoint(guy1, doorPosition);
 // Go to sleep until he gets there.
 WaitUntil(CHARACTER_ARRIVAL);
 // OK, we’re there. Tell the other threads
 // via a signal.
 RaiseSignal(“Guy1Arrived”);
 // Wait for the other guy to arrive as well.
 WaitUntil(SIGNAL, “Guy2Arrived”);
 // Now tell guy1 to play the “open door” // animation.
 CharacterAnimate(guy1, “OpenDoor”);
 WaitUntil(ANIMATION_DONE);
 // OK, the door is open. Tell the other threads.
 RaiseSignal(“DoorOpen”);
 // Now walk thru the door.
 CharacterWalkToPoint(guy1, beyondDoorPosition);
 }
 thread Guy2()
 {
 // Ask guy2 to walk to the door. CharacterWalkToPoint(guy2, doorPosition);
 // Go to sleep until he gets there.
 WaitUntil(CHARACTER_ARRIVAL);
 // OK, we’re there. Tell the other threads
 // via a signal.
 RaiseSignal(“Guy2Arrived”);
 // Wait for the other guy to arrive as well.
 WaitUntil(SIGNAL, “Guy1Arrived”);
 // Now wait until guy1 opens the door for me.
 WaitUntil(SIGNAL, “DoorOpen”);
 // OK, the door is open. Now walk thru the door.
 CharacterWalkToPoint(guy2, beyondDoorPosition);
 }
 }

In the above, we assume that our hypothetical scripting language provides a simple syntax for defining threads of execution within a single function. We define two threads, one for Guy1 and one for Guy2.

The thread for Guy1 tells the character to walk to the door and then goes to sleep waiting for his arrival. We’re hand-waving a bit here, but let’s imagine that the scripting language magically allows a thread to go to sleep, waiting until a character in the game arrives at a target point to which he was requested to walk. In reality, this might be implemented by arranging for the character to send an event back to the script and then waking the thread up when the event arrives.

Once Guy1 arrives at the door, his thread does two things that warrant further explanation. First, it raises a signal called “Guy1Arrived.” Second, it goes to sleep waiting for another signal called “Guy2Arrived.” If we look at the thread for Guy2, we see a similar pattern, only reversed. This pattern of raising a signal and then waiting for another signal is to synchronize the two threads.

In our hypothetical scripting language, a signal is just a Boolean flag with a name. The flag starts out false, but when a thread calls RaiseSignal(name), the named flag’s value changes to true. Other threads can go to sleep, waiting for a particular named signal to become true. When it does, the sleeping thread(s) wake up and continue executing. In this example, the two threads are using the “Guy1Arrived” and “Guy2Arrived” signals to synchronize with one another. Each thread raises its signal and then waits for the other thread’s signal. It does not matter which signal is raised first—only when both signals have been raised will the two threads wake up. And when they do, they will be in perfect synchronization. Two possible scenarios are illustrated in Figure 16.24, one in which Guy1 arrives first, the other in which Guy2 arrives first. As you can see, the order in which the signals are raised is irrelevant, and the threads always end up in sync after both signals have been raised.