informa
/
Programming
Features

Dependency Graphs In Games

Ever dealt with a camera that constantly aimed where the character was in the last frame? Or had a homing missile that constantly missed a moving target? Anyone who has ever worked with a game engine has, at some point, stumbled across data dependency problems. This article discusses object dependency problems and solution for games.

Everyone who has ever worked with a game engine has, at some point, stumbled across data dependency problems. Relationships between objects and data are everywhere. When rendering a frame of the game, data from that frame needs to be processed in the correct order to get the proper view of your data. If the order is incorrect, the renderer can display data that's a frame behind where it should be.

For instance, imagine a car driving in your game, while a camera observes it. You want the camera to look precisely at the car as it is rendered. Assuming the car is moving, it will be updated each frame. But if the camera orientation is updated before the car's transform is updated, the camera will be looking at the old position of the car - it's location in the previous frame. If the frame rate is high enough and if the objects aren't moving too fast, this error may be very small. But in more extreme cases, it can be a big problem. For example, in our upcoming game, Xyanide for the Xbox, we have a spaceship flying at two kilometers per second. If our camera tracks our spaceship's position before it updates, it is looking about 30 meters behind the spaceship (at 60 frames per second). In this case, that's significant.

If you're not yet convinced of the benefit of updating your data in the correct order, this might convince you: when using a scene graph, calculating the world transformation matrix in the scene graph tree can be a very costly operation. The calculation is usually optimized by setting dirty flags in the scene graph. The goal of these dirty flags is to update the world transform of the objects as little as possible, preferably just once before rendering. Now imagine what happens if we have two objects, A and B. B is part of a scene graph, and has a parent. Object B moves each frame. If A uses B's world transformation matrix before B is updated, the calculation of B's world transformation matrix is performed twice: once when A uses it, and once before rendering, because B's update caused its world transform matrix to be marked dirty again. Naturally, this is a problem.

The goal of this article is to discuss object dependency problems like these in games, and offer some solutions. But frankly, the solutions provided aren't the primary focus for my writing this article. Above all, I would like to make game programmers aware of the relationship and dependency problems that exist in game programming. Since transformation matrices cause the most obvious dependency problems, I will focus on them. However, data dependency problems apply to any form of data.

The article is structured in three parts. The first part of this article discusses problems that arise in dependency graphs, the second section shows some solutions for a-cyclic dependency graphs, and the final section discusses cyclic dependencies and eventually expands a solution from part two into a solution for a cyclic dependency graph.

Breaking Down The Problem


Object: C++ object, collection of methods and data members.
Node:

An object that requires updating in the main loop.

Parent/child: Parent /child relationships in scene graph hierarchy.
Frame: A single timeframe in a game loop.
World transform: World transformation matrix.

Terminology

Source and Target Nodes

Let's take a look at the main loop. Here are the update steps a single frame might require:

  • Poll input devices
  • Update all nodes
  • Perform collision detection and response
  • Render

In game programming it's normal to update your events each frame. The game clock that's used for this purpose is usually maintained within the main loop. The polling of input devices is usually also hardcoded in the main loop. But why aren't the game clock and input devices treated like any other node?

The order in which these hardcoded operations are called is based upon the implicit dependencies between nodes. The collision code is dependent upon the nodes, and the nodes are dependent upon both the input devices and the gameclock. The renderer depends of all of them. So let's make all of them nodes, and create dependencies between them.

Let's examine the importance of a single timeframe. During a single timeframe the game updates data, which in turn is used to produce output on a physical device, like a monitor or the speakers. (The render operation is an example of how data can be turned into output on a physical device.) Apart from the nodes that produce output for physical devices, each node always has another node that depends on it. If this isn't the case, the node has no practical use.

A node is called a "root node" or "source node" if no other nodes depend on it. The gameclock and the node that polls for device input are good examples of source nodes. A node is called a "target" node if it produces output to physical devices. All other nodes ("common nodes") depend on other nodes and have nodes that depend on them.


Figure 1: The Clock is a source node, Car is a common code, and the Renderer is a target node.

Relationships

Let's take a look at some relationships between nodes.

Relationship 1: Traditional Hierarchical Dependency

If node C uses data from node B, this means that C depends upon B. Node B must therefore be updated before node C uses it. In the timeframe, we want to update node B before node C is updated.

Example: We have a camera (C) and a moving target (B). If we want the camera to look at the target, the position of the target must be updated before the camera orientation is calculated. But what if node B was part of a scene graph, and it had a parent? The camera would need node B's worldtransform. That implies that C depends on both node B and its parent, which we'll call node A. Figure 2 shows this relationship.


Figure 2: The observer depends on both nodes A and B to calculate the worldtransform of the target, node B.

We can argue that node B shouldn't be dependent upon node A - rather, that C should just be dependent upon node B, as shown in figure 3. But node B doesn't necessarily depend on its parent node if it's not using its own world transform! If no other node uses node B's world transform, this relationship is obsolete. On the other hand, if we omit the dependency between node B and node A, the observer would need knowledge of the subject's scene graph parents to get the correct world transform, and that's not ideal either. The choice is yours.


Figure 3: Another way to establish an observer relationship.

Relationship 2: Dependencies Not Known

In this type of relationship, node A can write data in node B. Node B does not have to know about this relationship, and therefore does not know that it now depends on node A.

Example: An input node that reads controller input and sets the transform of the car node. If the car node wants to use the correct transform, the input node must be updated first.


Figure 4: The car depends upon the inputobject, without the car knowing about it. Node A has to make sure that the car knows it depends upon it.

Relationship 3: Traditional Circular Dependency

In this relationship, a data member of node A can depend on a data member of node B, and vice versa.


Figure 5: Traditional circular dependency.

Consider three points in space that (naturally) form a triangle when lines are drawn between them. The constraint between these points is that the distance from a given point to its adjacent points must remain constant. Therefore, if I move one of the points, the other points must move along with the dragged point without deforming the shape.


Figure 6: Example of circular dependencies between nodes A, B and C.

Relationship 4: Solvable Circular Dependency

Here is another form of circular dependency between nodes. Node A contains data members X and Y, and node B contains data members V and W. X is depends upon V, and W depends upon Y (see figure 7). In this case, there is a circular dependency at the node level, while functionally there is no dependency at all.


Figure 7: Solvable circular dependency.



Relationship 5: The Data Processor

In this situation, a node does not contain data -- it only processes it. It always depends on one or more other nodes for input, and it will always output data to other nodes, as it cannot store the calculated data itself.

Often, node B will process data from a series of nodes, and also write back into these nodes. For example, imagine a collision-detection-and-response node that takes all of the node's transforms, sizes, speeds and so on, and writes the new data back into the input nodes.

Figure 8: Node B contains no data. Note that the relationship between node B and C is the same as shown in relationship 2.



Figure 9: Relationship 5 is likely to process an amount of data from input nodes, and write them back in these nodes.

Relationship 6: Multiple Dependencies

A node can depend on another node multiple times. For instance, imagine an AI enemy that slowly steers towards a target, but at the same time it's shooting at the target. If the "shooting" dependency is dropped because the enemy stopped shooting, the "steering" dependency may still be relevant.


Figure 10: A node can be dependent upon another node multiple times.

Scene Graph Versus Dependency Graph

At first look, it can be tempting to use the scene graph as your dependency graph. When retrieving an object's world transform, quite often it's obvious that you want its scene graph parents to be updated first. While this may hold for many cases, it fails for many others. For example, the observer relationship is quite hard to implement in a tree-like graph. An observer should be updated later in the timeframe then its subject. To do so, the observer must either be:

  • A parent of the subject
  • A sibling of the subject that is updated later
  • A child of a completely different root that is updated later then the subject.

This just doesn't sound good to me, and I'm not even mentioning the fact that observers should be able to switch subjects, or the fact that this method excludes dependencies to any other form of data.

Define Your Atoms

Let's take a look at relationship 4 again, the solvable circular dependency (shown in figure 7). It's a circular dependency between nodes. In object-oriented languages we are prone to create dependencies between functionally grouped data members, like a C++ object having multiple data members. As soon as your objects contain multiple data members and other objects depend on one of these data members, the problem shown in relationship 4 is bound to arise. An example of such a situation is when object A uses object B's translation data, and object B in turn uses object A's rotation data. Making this problem even trickier is that the translation and rotation data likely must be included in a single 4x4 matrix!

In our game, we have a similar situation. We have a node that is similar to a viewport, through which we see our ship. The ship determines its own world transform, but its rotation depends on the viewport's rotation. In turn, the viewport's translation depends on the ship's translation, as the viewport can scroll left/right/up/down to keep the ship visible.

Splitting the objects into smaller objects, as shown in figure 11, can solve this dependency problem. The viewport didn't necessarily need to be split up, but it is displayed this way for clarity.


Figure 11: Dividing your objects into smaller objects. The update order for this situation could be: ShipTranslate, Viewplane Translate, Viewplane Rotate, ShipRotate.

So you should consider what level you want to define your relationships. Are you content with relationships between objects that contain data sets, or would you prefer to depend on each single data member? And what if you have a 3D vector -- is it sufficient to be able to depend on the vector as a whole, or do you want to be able to depend of each element in the vector? We could continue this down to the byte level. That sounds silly, but professional 3D animation packages cannot do without dependencies at, say, the vector level.

Dynamically Created Objects In The Dependency Graph

When nodes are created dynamically, it's possible that they will be created during the update sequence. When adding the node to the dependency graph, you don't know whether it will be updated during this update loop, prior to rendering it. You might wonder whether updating this node during the same loop is proper behavior at all.

Personally, I think it's best to create dynamic objects with proper initial values and ensure that the node isn't updated that frame. For instance, when shooting a bullet from a cannon on a spaceship, I set the bullet's initial transform to be the location of the cannon on the ship. When rendering its first frame, I want the bullet to be visible at the cannon's mouth. If that position were then updated right away, it would no longer appear at the mouth of the cannon. I raise this issue because I have never seen a case where it mattered whether a node was created in the beginning or at the end of the update timeframe -- most of the time your node will seem to run one frame ahead.

A-Cyclic Dependency Graphs

This section explores three simple solutions for a-cyclic dependency graphs.

Example 1: The Framecaller

At the former company I worked for, we used a system called the framecaller. It's not very fancy, and it's actually very easy to use. With this solution, each node has a framecaller (parent node). This parent node is responsible for updating its children. Just like a scene graph, each node has a single parent node and a list of child nodes. If node A is dependent upon node B, node B will set its framecaller to node A. When switching framecallers, as is needed when switching observers, the old framecaller needs to be notified so it can remove its child node from its list.

Please treat the example code in this article as pseudo code, as it is far from complete. It is just to give you an idea of how it could be implemented.

Get daily news, dev blogs, and stories from Game Developer straight to your inbox

Latest Jobs

Sucker Punch Productions

Bellevue, Washington
08.27.21
Combat Designer

Xbox Graphics

Redmond, Washington
08.27.21
Senior Software Engineer: GPU Compilers

Insomniac Games

Burbank, California
08.27.21
Systems Designer

Deep Silver Volition

Champaign, Illinois
08.27.21
Senior Environment Artist
More Jobs   

CONNECT WITH US

Register for a
Subscribe to
Follow us

Game Developer Account

Game Developer Newsletter

@gamedevdotcom

Register for a

Game Developer Account

Gain full access to resources (events, white paper, webinars, reports, etc)
Single sign-on to all Informa products

Register
Subscribe to

Game Developer Newsletter

Get daily Game Developer top stories every morning straight into your inbox

Subscribe
Follow us

@gamedevdotcom

Follow us @gamedevdotcom to stay up-to-date with the latest news & insider information about events & more