Scheduling

Introduction

Processor resources are limited and can easily get eaten up by some AI techniques such as pathfinding or complex decision making. Sometimes a frame may need a lot of AI elaboration, and sometimes you may have hundreds of frames where nothing much is happening to the AI.

Scheduling systems try to solve this kind of problems in order to keep the frame rate at acceptable values. There are three main ingredients to make the best use of the limited processing time available.

• dividing up the execution time among the AI that needs it
• having algorithms that can work a bit at a time over several frames
• giving preferential treatment to important characters and areas.

Scheduling systems were originally designed for AI and in the case of an extremely simple or light AI they are not essential. But when you have a good AI scheduling system you can use it for many other purposes: incremental loading of new areas of the level, game logic, audio scheduling, and so on.

The API

A Scheduler works by assigning a pot of execution time among a variety of tasks, based on which ones need the time. A task must implement the Schedulable interface in order to be scheduled.

Different AI tasks can and should be run at different frequencies. You can simply schedule some tasks to run every few frames and other tasks to run more frequently, slicing up the overall AI and distributing it over time. It is a powerful technique for making sure that the game doesn't take too much AI time overall.

The tasks that get called are passed timing information so they can decide when to stop running and return. However, note that there is nothing to stop a task from running for as long as it wants. The scheduler trusts that they will be well behaved.

Notes:

• Hierarchical Scheduling: The Scheduler interface extends the Schedulable interface, allowing a scheduling system to be run as a task by another scheduler. This technique is known as hierarchical scheduling. Also, it's worth noting that with a hierarchical approach, there's no reason why the schedulers at different levels should be of the same kind. For instance, it is possible to use a frequency-based scheduler for the whole game and priority-based schedulers for individual characters.
• AI Level of Detail: On its own there is nothing that hierarchical scheduling provides that a single scheduler cannot handle. It comes into its own when used in combination with level of detail (LOD) systems. AI LOD systems are behavior selectors; they choose only one behavior to run. In a hierarchical structure this means that schedulers running the whole game don't need to know which behavior each character is running. A flat structure would mean removing and registering behaviors (tasks) with the main scheduler each time.

Frequency-Based Schedulers

Frequency-based schedulers take tasks, each one having a frequency and a phase that determine when it should be run.

• Frequency: On each time frame, the scheduler is called to manage the whole AI budget. It decides which tasks need to be run and calls them. This is done by keeping count of the number of frames passed. This is incremented each time the scheduler is called. It is easy to test if each task should be run by checking if the frame count is evenly divisible by the frequency. On its own, this approach suffers from clumping: some frames with no tasks being run, and other frames with several tasks sharing the budget. Picking frequencies that are relatively prime makes the clash points less frequent but doesn't eliminate them. To solve the problem, we use the phase.
• Phase: The phase doesn't change the frequency but offsets when the task will be called. However, calculating good phase values to avoid spikes can be difficult. It is not intuitively clear whether a particular set of frequency and phase values will lead to a regular spike or not. That's why this scheduler supports automatic phasing. When a new task is added to the scheduler, with a frequency of f, we perform a dry run of the scheduler for a fixed number of frames into the future. Rather than executing tasks in this dry run, we simply count how many would be executed. We find the frame with the least number of running tasks. The phase value for the task is set to the number of frames ahead at which this minimum occurs. The fixed number of frames is normally a manually set value found by experimentation. Ideally, it would be the least common multiple (LCM) of all the frequency values used in the scheduler (you can use ArithmeticUtils.lcmPositive(int, int) to calculate the LCM). Typically, however, this is a large number and would slow the algorithm unnecessarily (for frequencies of 2, 3, 5, 7, and 11, for example, the LCM is 2310). Despite being a good approach in practice, it has a theoretical chance that it will still produce heavy spikes, if the look-ahead isn't at least as large as the size of the LCM.

The framework provides two types of frequency-based schedulers: a load balancing scheduler and a priority scheduler. Let's take a look at both.

Load Balancing Scheduler

A LoadBalancingScheduler understands the time it has to run and distributes this time equally among the tasks that need to be run. This scheduler splits the time it is given according to the number of tasks that must be run on this frame. To adjust for small errors in the running time of tasks, this scheduler recalculates the time it has left after each task is run. This way an overrunning task will reduce the time that is given to others run in the same frame.

Priority Scheduler

A PriorityScheduler works like a LoadBalancingScheduler but allows different tasks to get a different share of the available time by assigning a priority to each task. This scheduler splits the time it is given proportionally to the priority of the tasks that must be run on this frame. In other words, the higher the priority value the larger the amount of the available time dedicated to the corresponding task.