Gamasutra: The Art & Business of Making Gamesspacer
Dependency Graphs In Games
View All     RSS
September 1, 2014
arrowPress Releases
September 1, 2014
PR Newswire
View All

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

Dependency Graphs In Games

August 29, 2003 Article Start Page 1 of 3 Next

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.

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.


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.


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.

Article Start Page 1 of 3 Next

Related Jobs — Hunt Valley, Maryland, United States

Engineering Manager — Chicago, Illinois, United States

Engineering Manager — Hunt Valley, Maryland, United States

Graphics Software Engineer — Chicago, Illinois, United States

Lead UI Engineer


Amir Taaki
profile image
boring. basic programming/

Kiaran Ritchie
profile image
Thanks for the great article! I'm implementing a scene graph for transformations, but I am going to turn it into a dependency graph now. Thank you for the great explanations. :)