How to spread a computation over multiple update cycles

Let us consider a simple example: We want to implement an animation effect which can be used for "press start screens", among other things. The animation can be decomposed into three phases:

1. Fade-in effect where the text "press start" appears from the void. To achieve that, the text is rendered with full transparency initially, then gradually goes to fully opaque. This effect should be short, e.g. half a second.
2. Blinking effect. The text is rendered alternating between fully transparent and opaque. We don't want to alternate between the two modes every frame, as that would be two fast. The text should be rendered opaque for half a second, then transparent (or not rendered at all) for half a second, and so on...
3. Fade-out effect, which is triggered when the player presses the start button. It's similar to the fade-in effect, but in reverse.

The game update loop

The XNA framework, just as most other frameworks, encourages the developer to build their game in a specific way. The main function, which is implemented by the framework, repeatedly calls a function Update provided by the developer, followed by a call to another function Draw, also provided by the user. The combine execution time of these two functions should not exceed the amount of time separating two frames, which is about 16ms for a game running at 60 frames per second.
In this context, implementing computations that need to span over multiple frames is a bit tricky. Not very complicated, and all experienced game developers can do that during their sleep. Nevertheless, I always found that annoying enough that it has often stopped me from implementing a cool animation that would have made my application look so much more professional.

Imperative code

For a moment, let us forget about the game loop and write some simple imperative code.

let sleep time dt exit =
    let t = ref 0.0f
    let dt = int (dt * 1000.0f)
    while !t < time && not !exit do
        System.Threading.Thread.Sleep(dt)

let fade_time = 0.5f   // half a second
let blink_time = 0.25f

let alpha = ref 0.0f
let is_visible = ref true

            
let run dt goto_fade_out =
    let t = ref 0.0f
    while !t < fade_time do
        alpha := !alpha + dt / fade_time
        t := !t + dt
        sleep dt dt (ref false)

    while not !goto_fade_out do
        is_visible := true
        sleep blink_time dt goto_fade_out
        is_visible := false
        sleep blink_time dt goto_fade_out

    let t = ref 0.0f
    while !t < fade_time do
        alpha := !alpha - dt / fade_time
        t := !t + dt
        sleep dt dt (ref false)

Implementation using a state machine

Back to reality (where the game update loop rules), one way to break a computation over multiple update cycles is to use a state machine. Transitions are taken every cycle. Our state machine could have four states: FadeIn, BlinkOn, BlinkOff, FadeOut. It would have the following transitions: FadeIn to FadeIn, FadeIn to BlinkOn, BlinkOn to BlinkOff, BlinkOff to BlinkOn, BlinkOn to FadeOut, BlinkOff to FadeOut. While in FadeIn and FadeOut, the state machine maintains a single float representing the degree of transparency of the text. This can be implemented in F# using discriminated unions, as shown below.

type States =
    | FadeIn of float32        // 0.0 -> 1.0
    | Blink of bool * float32  // On/Off, Time left before transition
    | FadeOut of float32       // 1.0 -> 0.0

let fade_time = 0.5f   // half a second
let blink_time = 0.25f

let initial = FadeIn 0.0f

let update dt goto_fade_out state =
    match state with
    | FadeIn k ->
        let delta_k = dt / fade_time
        let k = k + delta_k
        if k > 1.0f then
            Blink (true, blink_time)
        else
            FadeIn k

    | Blink (b, t) ->
        if goto_fade_out then
            FadeOut 1.0f
        else if t <= dt then
            Blink (not b, blink_time)
        else
            Blink (b, t - dt)

    | FadeOut k ->
        let delta_k = dt / fade_time
        let k = max (k - delta_k) 0.0f
        FadeOut k

Implementation using continuations

To an imperative programmer, functional programmers can seem a bit special. They like to do things in a complicated, twisted way. The method I will now show may appear unnecessarily complex, but it has its benefits, as we shall see.

type States =
    | Transparent of float32 * (bool * float32 -> States)
    | Blinking of bool * (bool * float32 -> States)

let fade_time = 0.5f   // half a second
let blink_time = 0.25f

let rec updateFadeIn alpha (_, dt) =
    let delta_alpha = dt / fade_time
    let alpha = alpha + delta_alpha
    if alpha > 1.0f then
        Blinking (true, updateBlinking true blink_time)
    else 
        Transparent (alpha, updateFadeIn alpha)

and updateBlinking is_visible remaining (goto_fade_out, dt) =
    if goto_fade_out then
        Transparent (1.0f, updateFadeOut 1.0f)
    else if remaining >= dt then
        Blinking (is_visible, updateBlinking is_visible (remaining - dt))
    else
        Blinking (not is_visible, updateBlinking (not is_visible) remaining)

and updateFadeOut alpha (_, dt) =
    let delta_alpha = dt / fade_time
    let alpha = max (alpha - delta_alpha) 0.0f
    Transparent (alpha, updateFadeOut alpha)

let initial =
    Transparent (0.0f, updateFadeIn 0.0f)

let update state x =
    match state with
    | Transparent (_, cont) | Blinking (_, cont) -> cont x

What I did here was move the guts of update into the state itself. A state now includes a function which when called returns a new state (which itself includes a function which when called... you get the idea).

Strengths and weaknesses of each approach

The first method I exposed looks nice and easy to understand, but it won't work as it is. The problem is that it retains full control of the execution. There is not update function which can be called every cycle to update the state.

A solution consists of executing this code on a separate thread, but that brings problems of its own. Access to shared data between the main thread which does the rendering and the update thread is one of them, another is stopping/continuing the update thread.

The second method has only one problem, it becomes hard to read and maintain when the number of states grows. It's perfectly viable for simple animations, but it can't be used for the top level of the application (which can itself be seen as some sort of animation, the complex and interactive kind).

Statistics show that the third method will cause 95% of the population of programmers to get headaches. You'll it's actually very close to the second method, once you get the idea. I'm sure motivated programmers can train themselves to master this technique, but in this context, it's pointless.

The only reason I showed the third technique is to introduce features of F# called computation expressions and custom workflows. These features make it possible to write code using an extended subset of F# usual syntax and have it processed and executed in a manner controlled by the programmer. Understanding continuations is required in order to implement new custom workflows, but it's not necessary to take advantage of existing workflows.

These features are described in the F# specification. There is also a chapter in the F# wikibook. Tomas Petricek has some articles (1 2) on his blog.