The design brief for the new game's AI has just been handed to you, and to call it optimistic would be an understatement. You are charged with developing a real-time living, breathing city, populated by thousands of pedestrians, hundreds of cars, and dozens of non-player characters. The 'incidental' pedestrians and traffic need to react convincingly to each other and to your actions, while the NPCs absolutely positively must act in a believable manner when you encounter them. It's going to be computationally expensive, but you've only been given 20% of the processor time each frame, and if you exceed that and the game frames out, you've failed.

Modern games will increasingly make such demands on hardware and programmers. Fortunately help is at hand with techniques to control and manage real-time AI execution, techniques that open up the possibility of future hardware acceleration of AI.

Games Should Be Fun

Games should be fun. This requirement has many consequences. One important consequence is that games that allow player input at any moment ("arcade-style" games) should run in real-time, presenting events that occur sufficiently fast to challenge the player's reactions. Lower frame-rates look bad, reduce the opportunity for interaction, increase player frustration, and do not reflect the speed of events in the real world. With this firmly in mind, we set out to design a framework for the general execution of AI code.

Latter stages of a game project involve optimising parts of game code for processing time reductions. This includes AI code, which, depending on the type of game, can take up more or less of the available CPU time. Given this, an important requirement for general AI execution is that (a) it conforms to the timing constraint of the overall game frame rate. A consequence of (a) is that the AI never exceeds a maximum per-frame processing time.

AI requires the execution of arbitrarily complex and heterogeneous pieces of code, often grouped together as behavioural "rules" or "behavioursets" for various game objects or agents, such as the AI code for a trapdoor, obstacle, spring, or the code for an adversary, racing vehicle or character. Therefore, a further requirement for general AI execution is that (b) it makes no assumptions about the exact nature of the AI code, including assumptions about how long the code will take to execute.

Rendering code normally has to execute every frame in order to construct the visual scene. The situation is different for AI code. Consider a soccer player, who may need to check for passing and shooting opportunities every frame, but only need check its position against the team's formation every other frame, or only in a dead-ball situation. AI code involves a wide range of execution frequencies compared to non-AI game code. If all AI code is fully executed every frame when this is not required then the resulting code is inefficient. Also, some games require different execution frequencies for objects and agents, in addition to controlling the execution frequencies of their internal processes. For example, a very slow moving tortoise need not be processed every frame, whereas the hare may need to be. Hence, a further requirement for general AI execution is (c) it allows different execution frequencies to be specified both for agents and their constitutive internal processes.

Finally we realised that some AI processes can be extensively time-sliced across many frames, particularly if the results of the process are not immediately required. For example, if a strategy game agent needs to plan a route through a terrain, then the planning can potentially take place over many frames before the agent actually begins to traverse the deduced route. Time slicing allows computationally expensive processes to be 'smeared' across many frames thereby reducing the per frame CPU hit. Therefore, a final requirement for general AI execution is (d) it allows AI processes to be dynamically suspended and reactivated.

There are no general methods for supporting different execution frequencies of parts of AI code and time-slicing non-urgent AI processes. If these techniques are employed they are employed in a project-specific, ad-hoc manner. There is no 'AI operating system' that allows programmers to control these factors. This represents an important missed opportunity for the development of more complex AI in games. If all AI code were executed through a common AI operating system or engine, with mechanisms for specifying execution frequencies, upper bounds on CPU time, time-slicing, and suspension and reactivation of processes, then it would be possible to get more AI for the same CPU power.

To recap, here are four main requirements for general-purpose AI execution:

1. Conformity to the timing constraint of the overall game frame rate despite variable AI load;
2. No assumptions about the exact nature of AI code;
3. Allow different AI processes to have different execution frequencies, both for agents and their constitutive internal processes;
4. Allow AI processes to be dynamically suspended and reactivated.

By now you may have realised that (a) asks the impossible: AI algorithms that take the same amount of time even when asked to do more work. However, games must entertain the player, not implement a perfect simulation. In the next section we'll look at why we can partially satisfy requirement (a).

Believability Vs Accuracy

An arcade-style game is somewhat like the real world, consisting of both active and passive agents and events that unfold over time. But the game need not process every object, agent and event in the virtual world in order to present a believable, entertaining experience. For example, if a truck is within the player's field of view when planting a mine then the game necessarily needs to process the truck movement and the mine drop, and the rendering code necessarily needs to draw this event to the screen. However, if the truck is 'off-screen' the rendering code need not be run, and the AI code controlling the truck could simply assert the existence of a mine on the road at a certain time, rather than processing the fine-grained movement of the truck. Virtual game worlds need to present a believable world to the player, and not necessarily present an accurate simulation of the real world. Events not 'interactively close' to the human player need not be fully processed. Therefore, requirement (a) can be satisfied if some AI processes need only be "believable" rather than "accurate". These kinds of processes can be time-sliced over many frames, executed at a lower frequency, be replaced with computationally less expensive "default" behaviours, or simply postponed. Furthermore, what may need to be "accurate" at one time may need to be only "believable" at another, depending on the current activities of the human player. We call the idea of prioritising the update of parts of the game world currently most relevant to the player "egocentric processing". Our Process Manager implements this idea.