figure 3: example of the restricted iteration pattern.

//=====================================================================
// Nudge items and units within a given rect, so that they can fi nd
// 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

 

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 com-pile-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

2

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 real-time strategy game that has to process armies of individual units. The NudgeObjectsInRect script in Figure 3 appears in the Blizzard.j file. This function takes a rectangle and loops through all of the military units that appear in that rectangle; in that loop, it uses the function NudgeUnitsInRectEnum to push units apart so that there is a minimum distance between pairs of units.

All the operations in this script are external functions provided by the software engineers. The scripting language

is not aware that these functions implement the equivalent of a for-each loop (a loop over a fixed set of objects); otherwise, the compiler would be able to perform loop optimizations on it. Given the number of times this pattern appears in the Warcraft III scripts, this could result in significant performance improvements.

 

concurrency Patterns Iteration is not the only case in which developers could benefit from alternative control structures. Many games execute scripts in parallel, which requires scriptwriters to be cognizant of concurrency issues. As an example, consider inventory management in online games, a notoriously problematic scenario, with consistency violations resulting in lost or duplicated objects. Consider the following simple script written to put an item in a container such as a sack or a backpack:

 

// Test a container, and
insert an object if okay
success = TestPutItem(me,
container, item)
if (!success):

Bail() else:

PutItemInContainer(item, container)

be eliminated by the addition of locks or synchronization primitives to the scripting language. Locks can be expensive and error-prone, however, so game developers like to avoid them if at all possible. They are particularly dangerous in the hands of designers.

Additionally, lock-based synchronization is incompatible with the state-effect pattern. In the state-effect pattern, the state of the container consists of the contents at the end of the last iteration of the simulation loop, while an effect attribute is used to gather the items being added to the container. Effect variables cannot be read, even with locks, so the script cannot test for conflicting items being added simultaneously.

Instead of trying to solve this problem with traditional concurrency approaches, it is best to step back and understand what the programmer is trying to do in this pattern. The programmer wants to update an object, but under some conditions this update may result in an inconsistent state. The function TestPutItem defines which states are consistent. If the language knew this was the consistency function for PutItemInContainer, it could delay the check to ensure consistency without a lock. The language could first gather all of the items to be added to the container and then use the consistency check to place as many as the container can hold. In some cases, the language could even place multiple objects with a single consistency check.

Of course, this approach does not solve arbitrary problems with parallel execution, but game companies use languages with almost no concurrency support, and they rely on coding conventions to limit consistency errors. Adding features that provide concurrency guarantees for the more common design patterns in games would allow the game developers to trust their scriptwriters with a wider variety of scripts, increasing their artistic freedom.

 

This script tests if a container has the capacity to hold an item, then adds the item if there is space. Nothing in the script says that this action must be executed atomically, so in a distributed or concurrent setting, the container could fill up between the time it is tested and the time the item is added to the container. Obviously, this could

Game-aware Runtimes Language features provide the runtime with clues on how best to execute the code, but some games have properties outside of the scripting language that the runtime can also leverage. For example, the right optimization strategy for a set of scripts depends on the current state of the game. If the game is