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 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. ²

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, provided 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.1} This language is based on _{the observation that game} 3 scripts written in the state-effect pattern can often be optimized and processed with database techniques.

FIGURE

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 RES TRIC TED I TERA TION PAT TERN

Iteration is another common source of problems in game development. Allowing arbitrary iteration can quickly lead to significant performance degradation of the simulation loop. Iteration can be even more dangerous in the hands of inexperienced designers. During the development of City of Heroes, Cryptic Studios discovered that many of the scripts had interdependencies that produced hard-to-find infinite loops. To prevent this, the developers removed unbounded iteration from the scripting language.

Although this was a fairly drastic solution, most games do not need arbitrary iteration in their scripts. The scripts just need to perform a computation over a finite set of objects; such scripts follow the restricted iteration pattern, which obviously guarantees termination on all loops. In addition, it may enable code analysis and compile-time code transformations that improve performance. For example, SGL can take nested loops that produce quadratic behavior and generate an index structure from them¹; it then replaces the nested loops with a single loop that performs lookups into that index.

Examples of the restricted iteration pattern appear throughout the scripts in Warcraft III, a realtime strategy game that has to process armies of individual units. The NudgeObjectsInRect script in figure 3 appears in the

Example of the Restricted Iteration Pattern

//===================================================================== // Nudge items and units within a given rect, so that they can find

// locations where they can peacefully coexist function NudgeObjectsInRect takes rect nudgeArea returns nothing local group g

set g = CreateGroup() call GroupEnumUnitsInRect(g, nudgeArea, null) call ForGroup(g, function NudgeUnitsInRectEnum) call DestroyGroup(g)

call EnumItemsInRect(nudgeArea, null, function NudgeItemsInRectEnum) endfunction

more queue: www.acmqueue.com

ACM QUEUE November/December 2008 23