Sunday, January 9, 2011

Untying the game update loop

In a video game, what do the menu system, an AI agent and an animated HUD component have in common? They are all a pain in the neck to implement over the game update loop.

The difficulty arises from the gap between the concept and the code implementing it. For instance, a menu system is pretty simple to specify:
1. Identify the controller which is used to control the game,
2. Show the main menu
3. Wait for the user to select an entry
4. Depending on the entry, remove the menu and show another screen, which may be another menu, or the game itself.

The game update loop requires that we split up these few steps into tiny little chunks that fit in 16ms time slices. This requires the programmer to introduce variables to keep track of where the program currently is and where it's headed:

type GameState =
| PressStartFadeIn of ...
| PressStartWaitButtonPress of ...
| PressStartFadeOut of ...
| MenuFadeIn of ...

let update(gt : GameTime) =
  state <-
    match state with
    | PressStartFadeIn ...

The problem with this approach is that the workflow which was so obvious in the specification is now hidden in a state machine. This approach using state machines is common when implementing simple AI agents and animations.
When dealing with the menu system, another objected-oriented approach is often preferred, with a class per screen type. Transitions from one screen to another are implemented using events and handlers, or hard-coded into the screens themselves. For instance, the press start screen takes care of creating and showing the menu screen when it hides itself. In any case, figuring out the order in which screens come and go by reading the code is not trivial.

Ideally, one would like to program the steps using that sort of code:

while not exit_requested do
  let press_start_screen = new PressStartScreen()
  let player = press_start_screen.GetPlayer()

  let menu_screen = new MenuScreen()
  let entry = menu_screen.GetEntry()
  match entry with
  | Play -> play(); showScores()
  | Scores -> showScores()

Happily, F# makes this possible thanks to so-called computation expressions. I am not going into details in one single post, so for now I will simply refer you to the code I have written. It's all in XNAUtils my library for development of games for the Xbox 360.
I have developed a custom workflow and its associated builder TaskBuilder. There is a class which takes care of executing a set of tasks in type Scheduler. Here are some animations demonstrating how it's used. Another example, from the PressStartScreen:
// This task is chopped in blocks and each block is executed by the scheduler each frame (see Main.Update())
    let press_start_task = task {
        // subtask that makes the "press start" text blink. Executes concurrently
        let blinker =

        // Task to check if a button is pressed. Sets player when that happens.
        let player : PlayerIndex option ref = ref None
        while (!player).IsNone do
            for p in all_players do
                let state = GamePad.GetState(p)
                if state.IsConnected
                    && (state.Buttons.Start = ButtonState.Pressed
                        || state.Buttons.A = ButtonState.Pressed) then
                    player := Some p
            do! nextFrame()

        // Stop blinking
        // To be nice, wait until the blinker is done.
        // Depending on the blinking period, this could take long as we only check for the kill flag once per blink.
        do! sys.WaitUntil(fun () -> blinker.IsDead)

        // Return the index of the player that pressed start.
            match !player with
            | Some p -> p
            | None -> failwith "Unreachable"

All of this is put together in a sample application. Be sure to take a look at the main code.


Tomat said...

great article, keep it going!!!

its time to make a module tweening from animation.fs and make them chainable

Joh. said...

Thanks tomat.
I do not understand your suggestion, though. What do you mean by "tweening"?

Tomat said...

I mean by "tweening" is different kind of parameters animation. More in\out functions ( step, linear, quadric), wait-uprise-hold-fall-wait class ( _/-\_ ), etc.

Joh. said...

I see, and the goal is to be able to compose these functions.

The problem is that my current code for animations uses side effects to communicate its result, meaning it's not composable.

In general, I'm not quite happy with the way the update part communicates with the draw part, I will probably re-think that part.

Anonymous said...

Have you looked into Functional Reactive Programming at all?

I've been trying to get something going with WPF, but XNA might be a more suitable implementation target.

FRP's still an area of ongoing research though; apparently there are some efficiency issues in a lot of cases. I still haven't quite wrapped my head around it yet myself.

Joh. said...

reinux: No, I have not looked into FRP. I'm not much into GUIs, actually. Might sound strange, considering how much games are about interaction with the user...

rei said...

Ah, okay.

FRP was initially conceived for "interactive animations" actually. I think the researchers started pitching it as more of a GUI thing either due to the performance overhead or because GUIs have a broader audience.

I was looking at your use of the Eventually monad, and it looked a bit like FRP. Probably some conceptual convergence. Cool.