This article shows how to create a long running set of background tasks, so that each part of the task is split over several frames and the game remains reponsive. Such a mechanism can be used to generate procedural content in the background, calculate AI parameters, perform inital pathfinding for a game entity, and other time consuming but not time-critical tasks. It closely approximates the ability to multi-thread, if used appropriately.
Flash does not currently (as of the time of writing, Player 11) permit AS3 programs to create background threads. Every function called within a single frame will be run to completion before the frame is allowed to end – which means that, if you want to run code which takes more than 30ms, your game will fall behind its target frame rate, and if you want to run a long-running task your game will lag while it finishes.
Sometimes you must simply run less time-consuming code; if the average code execution time needed to process and render a frame is too long, then it is not possible for the game to run at full speed. But often, the task is not something that needs completing every frame, but when it does need doing, it takes a long time. The solution to this problem is to split such long-running tasks across several frames, in sections which each take as little time as possible.
This article introduces a library which makes it easier to manage such background tasks and to respond to their progress.
The library works by managing a queue of requested tasks, and during each frame, it asks the task currently active (i.e. at the top of the queue) to perform a single step. A task is something which is logically a single action, but which takes long enough that you don't want to run it in a single frame, and which can be broken down into smaller steps; for example, 'find the shortest path through this maze', with each step being one pass of the A* pathfinding algorithm. Task steps continue to be run within the frame until the maximum time per frame is reached.
Once one task is complete, it is removed from the queue, and the next task in the sequence is begun. Because Flash does not provide threading, each task is run in sequence.
Often, a long-running task is essentially a loop. In this case, it is easy to see what the step should be: it is the contents of the loop. In other cases you may have to find less obvious breakpoints, or re-arrange how the task works so that it can be more easily split into several tasks.
A task can be anything which implements the ITask interface:
public interface ITask {
function get complete() : Boolean;
function get progress() : Number;
function get total() : Number;
function get source() : * ;
function doNextItem() : void;
}
doNextItem is repeatedly called by the task manager (see below) until complete returns true. The two functions progress and total give an indication of how much of the task has been completed, which you can use for a progress indicator. source is for recording the object which pushed this task onto the queue. The only rules are that, eventually, complete should return true, and that doNextItem() should execute quickly. However, three of the most common types of task have already been implemented.
Firstly, the MarkerTask does nothing, and completes immediately. You can use this type of task to insert markers onto the queue so that you know when a particular group of tasks is complete.
Secondly, the LoopTask allows you to replace a loop of the form:
for each(var object:DataClass in vector){
...
}
... with a background task of the form:
var task:ITask = new LoopTask(vector, function(object:DataClass) : void {
...
}, this);
... allowing you to split up an iteration over a large list across multiple frames. Similarly, the RepeatTask lets you replace a traditional for loop with a similar task in which the function is called a given number of times. Looping in one of these two ways accounts for many of the most common cases of long-running code.
Once you have determined how to split your task up, and you know how to create the task object you want, how do you execute it and get the result? Because the execution can be spread over multiple frames, you can't wait for it to complete within a function; instead, you need to create an event handler that will be notified when a task completes, and when it moves on.
The TaskManager class is the core of the library. It manages the queue, and handles execution of the tasks. To get a task to be executed, you need to add it to the queue of a task manager:
taskManager.add(myTask);
Before a TaskManager will begin to run tasks, it needs to be attached to a stage, so it can run an ENTER_FRAME handler. This can be done either at construction time, or later by assigning the stage property.
TaskManager dispatches four events (with names defined by constants within the class), which provide various levels of detail on the progress of tasks:
For this example I am going to use a well known looping algorithm: finding prime numbers by the Sieve of Erasthosthenes. The natural task step function in this case is one pass through the sieve, and the operation itself is a repeat of that action for a requested number of times, so I extend RepeatTask:
public class ErasthosTask extends RepeatTask {
private var mask:Vector.<Boolean>;
public function ErasthosTask(max:int, source:*) {
super(max, stepFunction, source);
mask = new Vector.<Boolean>(max * max);
for (var i:int = 2; i < max * max; i++) mask[i] = true;
}
private function stepFunction(value:int) : void {
if(mask[value])
for (var i:int = value * value; i < total * total; i += value)
mask[i] = false;
}
public function get primes() : Vector.<int> {
var r:Vector.<int> = new Vector.<int>();
for (var i:int = 0; i < total * total; i++)
if (mask[i]) r.push(i);
return r;
}
public function toString() : String {
return "[" + primes.join(" ") + "]";
}
}
In my main display object, some time after it has been added to the stage, I need to create a task manager and attach it to the stage, and listen for the completion event:
taskManager = new TaskManager(20, stage);
taskManager.addEventListener(TaskManager.TASK_COMPLETE, function(e:DataEvent) : void {
var task:ErasthosTask = e.Data as ErasthosTask;
if(task) updateDisplay(task.primes);
});
(The 20 in the constructor indicates the maximum time the manager will attempt to use per frame.) Finally, at some point, for example on an event handler for a button, I will create the task and add it to the queue:
taskManager.add(new ErasthosTask(1000));
Note that when you run this, even though execution lasts for some time (about a second for me), your game is still responsive and, if you have a FPS counter, it should remain fairly high.
Note that by downloading the library, you agree to the following licence conditions: (i) you will not claim this code as your own; (ii) you will not attempt to sell the code; and (iii) if anything goes wrong as a result of using this code, I won't be held responsible. Download AS3 implementation.