each game object selects an action and
determines individually the effects of
this action. In the update phase, all the
effects are combined and update the
current state of the game to create the
new state for the next iteration of the
simulation loop.
Because of these two phases, we can
separate the attributes of game objects
into states and effects. State attributes
represent the snapshot of the world
after the last iteration of the simulation loop. They are altered only in the
update phase and are read-only in the
effect phase. Effect attributes, on the
other hand, contain the new actions of
the game objects, and the state of the
game is updated with effects during the
update phase. Because interactions between game objects are logically simultaneous, effect values are never read
until the update phase. Hence, effect
values are, in some sense, write-only
during the effect phase.
Game physics provides many examples of this pattern. At the beginning of
the simulation loop, each game object
has a current position and velocity recorded as state attributes. To compute
the new velocity, each object computes
the vector sum of all of the forces acting upon it, such as collisions, gravity,
or friction. In other words, the force
attribute may be written to multiple
times during the simulation loop, but
it is never read until all of the force values have been summed together at the
end of the loop. The example in Figure
2 illustrates the use of the state-effect
pattern to simulate objects moving
about in a potential field. The variable
force is an effect in this calculation.
During the effect phase we only increment its value and never read it to determine control flow. Whereas most
implementations would read the old
value of force to perform this increment, this is not necessary; we could
also gather all of these force values in a
list and add them together at the end of
the effect phase.
Most of the time, game developers
use the state-effect pattern to manually
design high-performance algorithms
for very specific cases. That is because
it has several properties that allow
them to significantly enhance the performance of the simulation loop. The
effect phase can be parallelized since
the effect assignments do not influence
figure 2: example of the state-effect pattern.
// Outer simulation loop
for each timestep {
// Compute effects for all for each particle o {
o.effectPhase();
}
// Update state for all for each particle o {
o.updatePhase() ;
}
}
// State variables
vector position, velocity;
scalar q, damping, mass;
// Effect variables
vector force;
// Read state, write effects
effectPhase() {
for each particle p {
r = position-this.p.position;
s = ((this.q*p.q)/( r.magnitude())^ 3;
force += s*r;
}
}
// Read and write state, read effects
updatePhase() {
velocity = damping*velocity+force/mass;
}
each other. The update phase can also
be parallelized since it consists only of
the aggregation of effects and updates
to state variables. This does not need
to be done by hand; if the scripting
language knew which attributes were
state attributes and which were effect
attributes, it could perform much of
this parallelization automatically, even
in scripts written by inexperienced designers. This is similar to what Google
achieves with its Sawzall language and
the MapReduce pattern; special aggregate variables perform much the
same function as effect attributes, and
the language allows programmers at
Google to process data without any
knowledge of how the program is being parallelized.
1
Automatic parallelization is an
example of an alternative execution
model; the game runs the script using
a control flow that is different from the
one specified by the programmer. Since
the simulation loop logically processes
all of the game objects simultaneously,
we can process them in any order, pro-
vided that we always produce the same
outcome. Thus, alternative execution
models are among the easiest ways of
optimizing game scripts. Another unusual execution model is used by the
SGL scripting language, which is being
developed at Cornell University. 2 This
language is based on the observation
that game scripts written in the state-effect pattern can often be optimized
and processed with database techniques. The script compiler gathers
all of the scripts together and converts
them into a single in-memory query
plan. Instead of using explicit threads,
it constructs a data pipeline that allows
the code to be parallelized in natural
ways. Many of these data pipelines are
similar to the ones that game programmers create when they program on the
graphics processing unit, except that
these are generated automatically.
the Restricted iteration Pattern
Iteration is another common source of
problems in game development. Allowing arbitrary iteration can quickly lead