Showing posts with label xnautils. Show all posts
Showing posts with label xnautils. Show all posts

Monday, January 16, 2012

Units of measure to the rescue!

Physics can really improve immersion in a game, regardless of how faithful they are to reality. That's why I always enjoyed writing simple physics engine. Even though I have stuck to really simple physics engine, I always end up mixing accelerations and forces. That usually doesn't lead to much trouble in the final result, as masses tend to be constant, and physical properties of game objects are typically chosen after experimentation to maximize fun.

The feeling that there is something wrong with the math in my code is always annoying, though. It turns out F# has a solution for that, called units of measure.

A unit of measure is a type annotation that helps programmers write correct formulas. It's obviously useful for formulas in simulations, whether one is dealing with physics, finances or any other domain where models play an important role.

The code below shows how to declare a unit measure.
/// Position, meters
[<Measure>] type m

/// Time, seconds
[<Measure>] type s

/// Mass, kilograms
[<Measure>] type kg
Units in physics have a certain level of redundancy, one might say. For instance, forces can be expressed in Newtons or in kilograms time meters per squared seconds. Newtons are obviously more convenient to use, but you want that masses multiplied by accelerations be recognized as forces. This is how you capture Newton's law:
/// Force, Newtons
[<Measure>] type N = kg m/s^2
Units of measure can be used with primitive numeric types such as int, float and float32.
let integrateShips (dt : float32<s>) (ships : Ships) ...
dt above denotes a time duration in seconds represented using a 32-bit floating point value. Units of measure can also be applied to complex types. The code below shows the code for a wrapper around Xna's Vector3.
/// A three-dimensional vector with a unit of measure. Built on top of Xna's Vector3.
type TypedVector3<[<Measure>] 'M> =
    struct
        val v : Vector3
        new(x : float32<'M>, y : float32<'M>, z : float32<'M>) =
            { v = Vector3(float32 x, float32 y, float32 z) }
        new(V) = { v = V }

        member this.X : float32<'M> = LanguagePrimitives.Float32WithMeasure this.v.X
        member this.Y : float32<'M> = LanguagePrimitives.Float32WithMeasure this.v.Y
        member this.Z : float32<'M> = LanguagePrimitives.Float32WithMeasure this.v.Z
    end

[<RequireQualifiedAccessAttribute>]
module TypedVector =
    let add3 (U : TypedVector3<'M>, V : TypedVector3<'M>) =
        new TypedVector3<'M>(U.v + V.v)

    let sub3 (U : TypedVector3<'M>, V : TypedVector3<'M>) =
        new TypedVector3<'M>(U.v - V.v)


type TypedVector3<[<Measure>] 'M>
with
    static member public (+) (U, V) = TypedVector.add3 (U, V)
    static member public (-) (U, V) = TypedVector.sub3 (U, V)
This allows to add and subtract vectors with compatible units of measure. It took me some effort to figure out how to handle multiplication by a scalar. First, in module TypedVector:
let scale3 (k : float32<'K>, U : TypedVector3<'M>) : TypedVector3<'K 'M> =
        let conv = LanguagePrimitives.Float32WithMeasure<'K 'M>
        let v = Vector3.Multiply(U.v, float32 k)
        new TypedVector3<_>(conv v.X, conv v.Y, conv v.Z)
Then the type extension:
type TypedVector3<[<Measure>] 'M>
with
    static member public (*) (k, U) = TypedVector.scale3 (k, U)
Note the use of LanguagePrimitives.Float32WithMeasure<'K 'M> to produce a number with a specific unit of measure in a generic fashion.

I have designed the class to reuse Xna's implementation although it wouldn't have been hard to write my own from scratch. The key benefit, on Windows Phone 7, is to take advantage of some fast vector math that's only accessible through Xna's types. The PC and Xbox platforms don't support fast vector math, but who knows, it may come.

Finally, here comes an example of how to use all this:
    let speeds2 =
        Array.map2
            (fun speed (accel : TypedVector3<m/s^2>) ->
                let speed : TypedVector3<m/s> = speed + dt * accel
                speed)
            ships.speeds.Content accels.Content

    let posClient =
        ArrayInlined.map3
            (fun pos speed speed2-> pos + 0.5f * dt * (speed + speed2))
            ships.posClient.Content
            ships.speeds.Content
            speeds2
There is more to be said and written about units of measures, a future post will show how they can be used for safe access of array contents.

Thursday, January 12, 2012

Parallel draw-update XNA game component

Video games are often demanding when it comes to computation power, especially simulations and 3d games. The Xbox 360 has 3 cores with two hardware threads each. Of these 2 are reserved for the system, leaving 4 available to the programmer.
This article describes an easy to use custom XNA game component that allows to run computations in parallel with rendering.

The typical game loop is often divided in two steps, update and draw. I suggest a slightly different workflow divided in three steps, two of which run in parallel: update, compute and draw. The traditional update stage is divided in two new steps, update and compute.

In this new setting, update is used for receiving inputs from the player and the network, in the case of an online multiplayer game. Compute is potentially cpu-hungry operation implemented in a purely functional way. Rendering plays the same role as usual.

The code for the entire component fits in little over 100 lines, see below.
namespace CleverRake.XnaUtils

open Microsoft.Xna.Framework
open System.Threading

type IFramePerSecondCounter =
    abstract FramesPerSecond : float

/// An update-able and drawable game component which performs light updates on the main
/// thread, then draws on a separate thread in parallel of more computation-heavy updates.
/// initialize_fun is called when assets are loaded.
/// dispose is called when the component is disposed, and should be used to unload assets.
/// update_fun takes a GameTime and a state, and should produce draw data and computation
/// data.
/// draw_fun takes a game time and draw data and should return nothing.
/// compute_fun takes a game time and computation data and should return a new state.
type ParallelUpdateDrawGameComponent<'State, 'DrawData, 'ComputationData>
    (game,
     initial_state : 'State,
     initialize_fun : unit -> unit,
     update_fun : GameTime -> 'State -> 'DrawData * 'ComputationData,
     compute_fun : GameTime -> 'ComputationData -> 'State,
     draw_fun : GameTime -> 'DrawData -> unit,
     dispose : unit -> unit) =

    inherit DrawableGameComponent(game)

    let mutable state = initial_state
    let mutable draw_data = Unchecked.defaultof<'DrawData>
    let mutable compute_data = Unchecked.defaultof<'ComputationData>
    let mutable gt_shared = GameTime()

    let mutable enabled = true
    let mutable update_order = 0

    let signal_start = new AutoResetEvent(false)
    let mutable kill_requested = false
    let signal_done = new AutoResetEvent(false)

    let do_compute() =
#if XBOX360
        // Set affinity
        // 0 and 2 are reserved, I assume the "main" thread is 1.
        Thread.CurrentThread.SetProcessorAffinity(3)
#endif
        while not kill_requested do
            signal_start.WaitOne() |> ignore
            state <- compute_fun gt_shared compute_data
            signal_done.Set() |> ignore

    let compute_thread = new Thread(new ThreadStart(do_compute))

    // Must be called from the main thread.
    let post_compute_then_draw gt =
        if not kill_requested then
            let state = state
            gt_shared <- gt
            signal_start.Set() |> ignore
            draw_fun gt draw_data
            signal_done.WaitOne() |> ignore

    let mutable frameCounter = 0
    let mutable timeCounter = 0.0
    let mutable fps = 0.0
    let fpsUpdatePeriod = 0.3

    do
        compute_thread.IsBackground <- true
        compute_thread.Start()

    override this.Initialize() =
        base.Initialize()
        initialize_fun()

    override this.Update(gt) =
        if base.Enabled then
            base.Update(gt)
            let draw, compute = update_fun gt state
            draw_data <- draw
            compute_data <- compute

    override this.Draw(gt) =
        if base.Visible then
            base.Draw(gt)
            post_compute_then_draw gt
        else
            state <- compute_fun gt compute_data
        timeCounter <- timeCounter + gt.ElapsedGameTime.TotalSeconds
        frameCounter <- frameCounter + 1
        if timeCounter > fpsUpdatePeriod then
            fps <- float frameCounter / timeCounter
            timeCounter <- timeCounter - fpsUpdatePeriod
            frameCounter <- 0

    
    interface System.IDisposable with
        member this.Dispose() =
            base.Dispose()
            dispose()
            signal_start.Dispose()
            signal_done.Dispose()

    interface IFramePerSecondCounter with
        member this.FramesPerSecond = fps

    member this.FramesPerSecond = fps

    member this.RequestKill() =
        kill_requested <- false
        signal_start.Set() |> ignore

    member this.WaitUntilDead() =
        compute_thread.Join()

    member this.IsDead = not(compute_thread.IsAlive)

To be noted is that this component isn't meant to be extended the usual way which consists in inheriting and overriding. I'm experimenting with staying away from traditional OOP. I'm not sure it's the nicest way to do things, but building a wrapper from which to inherit shouldn't be hard. The OOP way will definitely be more appealing when using this component from C#, so I'll probably have to take this step anyway.

The constructor of the class takes an initial state and an initializing function which shouldn't be mixed. The initializing function is meant for loading assets. The dispose function should undo the effects of the initializing function and should dispose of any disposable asset.

The initial state represents the state of the world when the game starts. This is typically built from a level description when entering a new level, or by loading a previously saved session.

When the game is running, the state is passed to the update function, which isn't so well named, in retrospect. Its role is to prepare data for the compute and draw functions, which are run in parallel. In most cases I expect that ComputationData and State are the same type.

As is common in parallel update/draw scenarios, the draw function renders the state produced by the compute function in the previous frame. This is necessary to avoid race conditions between the compute and draw functions.

I am not yet sure whether I'm happy with my implementation of IDisposable, and this may change if turns out to be impractical or wrong. I've been using this component in a new game I'm working on, and I have been positively surprised. I hope you will find it useful!

Monday, December 12, 2011

Converting FS project files to target Xbox 360

Of interest to anyone using F# and XNA to make games targeting the Xbox 360: I'm working on a script to convert fsproj files for the PC platform to the Xbox platform.

https://bitbucket.org/johdex/xnautils/src/a2cc6e8c7455/WinPc/ConvertFsProj.fsx

It's not 100% ready yet, the converted files need some manual editing before they are usable.

The advantage of using a script over using the project template is that no additional and unnecessary directory is created. It also keeps all project content, no need to re-add all dll references and source files.

Here are some known issues:
- Project references are not automatically updated.
- System.Xml and System.Xml.Serialization and possibly other XNA dlls cannot be added from Visual Studio. It complains that those libs are not compatible with the targeted framework despite the fact that they are.
- You need the custom FSharp.Core.dll and accompanying files for Xbox360 somewhere in your solution. You get them as part of the F# + XNA templates, they are also in XNAUtils/FSharpCore.

Sunday, February 27, 2011

Replacing LIVE functionality in XNA 4.0

Although the XNA framework supports multiple platforms, including Xbox and Windows on PC, there are parts that are not available on Windows PC.

One such part is dedicated to interacting with Xbox LIVE, such as gamer profile information, permissions, avatars. (Actually, these parts are available to developers, but not to users). That can be a problem if you want to release your Xbox game to PC. Even if you don't intend a commercial release and only want to distribute your game to your friends and family, they typically don't want to install the full SDK just so that they can run your game.

Before XNA Game Studio 4.0, if you wanted to support the PC platform, you had to write an abstraction layer over these restricted features, or sprinkle your code with #ifdef. There was no way you could replace the implementation of restricted features with your own as the default implementation was embedded into the same DLLs as non-restricted parts of XNA (and you don't want to reimplement these).

The release of XNA Game Studio 4.0 saw a clean-up of the organization of all assemblies. All restricted features are now confined to specific DLLs, which you can replace with your own.

I have started work on my own implementation. My level of ambition is not pretty low, I only intend to achieve the kind of coverage I need for my own code to compile and run. In any case, it's available on bitbucket, so feel free to grab it, modify and extend it to your liking.

I have started with Microsoft.Xna.Framework.Storage, as this is what I use in the code I mentioned in a previous post about safe IO on Xbox. Here are some random observations and small things I learned in the process.

References to record types can't be null. The XNA framework is primarily meant for C#, and it uses null (to the delight of generations of evil peer-reviewers). I initially used records for StorageDevice and StorageContainer, and I had to change to classes when I tried my replacement with existing game code. Even F# classes aren't null-friendly by default, you have to mark classes with a special attribute to change that:

[<AllowNullLiteral>]
type StorageDevice =
    class
        val drive : DriveInfo
        val path : string
        new (d, p) = { drive = d; path = p }
    end 

Separating methods from data in class declarations help avoid circular dependencies. StorageDevice depends on StorageContainer because a method of StorageDevice is used to create instances of StorageContainer. StorageContainer depends on StorageDevice because each StorageContainer is owned by a StorageDevice.
It would seem there is a circular dependency, which in F# must be dealt with explicitly. A simple solution consists of declaring the types as mutually dependent (using "and" instead of "type" for the second type). Another one is to move the definition of StorageDevice.BeginOpenContainer and StorageDevice.EndOpenContainer after StorageContainer.

[<AllowNullLiteral>]
type StorageDevice =
    class
        val drive : DriveInfo
        val path : string
        new (d, p) = { drive = d; path = p }
    end


[<AllowNullLiteral>]
type StorageContainer =
    class
        val name : string
        val device : StorageDevice
        val mutable is_disposed : bool
    
        new(name, dev) = { name = name; device = dev; is_disposed = false }
    end
with interface IDisposable with
        member this.Dispose() = this.is_disposed <- true

type StorageDevice with
    member this.BeginOpenContainer(displayName : string, cb : AsyncCallback, state : Object) =
        let f = new Task<_>(StorageInternals.openContainer(this, displayName), state)

        StorageInternals.doThenMaybeCallback(f, cb)

        f :> IAsyncResult

    member this.EndOpenContainer(result : IAsyncResult) =
        let task = result :?> Task<StorageContainer>
        task.Wait()
        task.Result


Not everything needs to be in a module. By default, each new F# source file starts with
module Module1.fs

You can use "namespace" instead:
namespace Microsoft.Xna.Framework.Storage

If you need F# functions at the root-level (i.e. outside a class or a method), you can start a module right in the middle of your source file:

type StorageContainer =
    class
        val name : string
        val device : StorageDevice
        val mutable is_disposed : bool
    
        new(name, dev) = { name = name; device = dev; is_disposed = false }
    end
with interface IDisposable with
        member this.Dispose() = this.is_disposed <- true


module StorageInternals =
    let checkConnected(dev : StorageDevice) =
        if not dev.drive.IsReady then raise(StorageDeviceNotConnectedException())

type StorageContainer with

    member this.CreateDirectory(dir) =
        StorageInternals.checkConnected(this.device)
        let path = Path.Combine(this.device.path, this.name, dir)
        Directory.CreateDirectory(path) |> ignore 

Windows.Forms.FolderBrowserDialog isn't very useful. I was initially using it to let the user select the StorageDevice and StorageContainer, but it turned out I can't use it in the main thread because it's modal, and I can't use in a separate thread because I can't. Actually, that's not true, I can use a separate thread if I create it myself using some special options. It the end, that's not what I did. I just rolled up my own browser using a TreeView.



How do I create an IAsyncResult? There may be many different solutions, but an easy one that work for me was to use a Task (they implement IAsyncResult).

let f = new Task<_>(StorageInternals.openContainer(this, displayName), state)

F# Asyncs are nice for GUI. The following code shows the browser on the right thread (assuming you can get hold of the Threading.SynchronizationContext of the GUI thread), and disposes of the dialog nicely.

let openContainer(dev : StorageDevice, name) _ =
        let dialog = new FolderBrowser(sprintf "Select container directory [%s]" name, Some dev.path)
        async {
            try
                do! Async.SwitchToContext(gui_context)
                dialog.Show()
                let! _ = Async.AwaitEvent(dialog.Closed)
                return
                    match dialog.Selected with
                    | Some path ->
                        if not(Directory.Exists(path)) then
                            Directory.CreateDirectory(path) |> ignore
                        new StorageContainer(name, dev)
                    | None ->
                        null
            finally
                dialog.Dispose()
        }
        |> Async.RunSynchronously

Playing and testing with your library code is easy, just use an F# script. No need for an extra project building an executable.



That's all for this article. Lots of small interesting details packed in little code.

Saturday, February 12, 2011

Death by exception

The mini-OS I developed for cooperative multi-tasking did not support killing tasks at first. This limitation made it a bit tricky to implement a specific feature I wanted to include in the small game I am developing to demonstrate the library's features. The feature in question consists of sending the player back to the "log-in" screen when the player signs out.

My first attempt simply checked if the player had signed out, and if that was the case, the current screen was exited as if the player had aborted. This was possible because every screen supports abortion. The problem with this approach is that all animations and sound effects associated to screen transitions would be played at once.

To avoid that problem, I could have added a special abortion path where all these effects are not played, but it did not feel right.

Another alternative is to "restart" the game, i.e. kill all tasks and let the top level reinitialize the game. Instant death is actually easy: it's a matter of not calling Scheduler.RunFor and discarding the scheduler, replacing it by a new empty one.

There is a problem, though. The screen manager will still have references to the screens, only the tasks have been killed. This particular problem is easy solve by the addition of a RemoveAll method, but there is more to it. The real problem is that clean-up code in tasks is never executed.

The definitive solution requires all clean-up code to be located in finally blocks, or in Dispose methods of IDisposable objects bound with "use" or "using". That's where all clean-up code should be anyway. The code below shows a new method in ScreenBase which makes it easy to add a screen, do something the remove the screen.

type ScreenManager(game, ui_content_provider : IUiContentProvider) =
    ...
    member this.AddDoRemove(s : Screen, t : Eventually<'T>) = task {
        try
            this.AddScreen(s)
            return! t
        finally
            this.RemoveScreen(s)
    }

Once this condition is met, the process of killing can be implemented by throwing an exception. The environment is given a new field indicating whether killing is going on. All system calls check this field before and after yielding or sleeping, and raise a specific exception if needed.

exception TaskKilled of obj

type Environment(scheduler : Scheduler) =
    // When killing all tasks, the data to embed in TaskKilled exceptions.
    let killing_data : obj option ref = ref None

    let checkAndKill = task {
        match !killing_data with
        | Some o -> raise(TaskKilled(o))
        | None -> ()
    }

    member this.StartKillAll(data) =
        killing_data := Some data
        scheduler.WakeAll()

    member this.StopKillAll() =
        killing_data := None

    member this.Wait dt = task {
        do! checkAndKill
        do! wait dt
        do! checkAndKill
    }

Using an exception makes it possible to survive a killing attempt by catching the exception and discarding it. There are two ways to go at this point: Either refrain from doing such a thing (in which case one should never ever catch and discard all exceptions), or embrace the idea and use it for "targeted killing". The exception thrown during killing (TaskKilled) carries an object which can be used in any way programmers see fit. It can for instance be a predicate which when evaluated indicates if the exception should be rethrown or discarded. Beware though: Tasks wake up early from long sleeps when they are killed. If the task is meant to survive, it's up to the programmer to make sure the task "goes back to bed".

The last piece in the puzzle is to detect sign-outs and react by killing and reinitializing the game. This process should not be enabled at all time though, it depends in what "top state" the game is. What I call "top state" here is an abstract view of the game state. See the code below for the complete list of states:

type TopState =
    | Initializing
    | AtPressStartScreen
    | AnonPlayer
    | Player of SignedInGamer
    | KillingAllTasks

State AnonPlayer is active when a player is playing the game (i.e. has press "start" on the "press start screen") without being signed in.
State Player corresponds to a signed-in player playing the game.

A typical flow is Initializing -> AtPressStartScreen -> Player or AnonPlayer -> AtPressStartScreen...
Another flow involving signing out: Initializing -> AtPressStartScreen -> Player or AnonPlayer-> KillingAllTasks -> Initializing -> ...

The code below updates the state machine.

type TopState =
    | Initializing
    | AtPressStartScreen
    | AnonPlayer
    | Player of SignedInGamer
    | KillingAllTasks
with
    member this.Update(transition) =
        match this, transition with
        | Initializing, InitDone -> AtPressStartScreen
        | Initializing, _ -> invalidOp "Invalid transition from Initializing"

        | AtPressStartScreen, AnonPressedStart -> AnonPlayer
        | AtPressStartScreen, PlayerPressedStart(p) -> Player p
        | AtPressStartScreen, _ -> invalidOp "Invalid transition from AtPressStartScreen"

        | AnonPlayer, Back -> AtPressStartScreen
        | AnonPlayer, _ -> invalidOp "Invalid transition from AnonPlayer"

        | Player p, SignOut -> KillingAllTasks
        | Player p, Back -> AtPressStartScreen
        | Player p, _ -> invalidOp "Invalid transition from Player"

        | KillingAllTasks, AllTasksKilled -> Initializing
        | KillingAllTasks, _ -> invalidOp "Invalid transition from KillingAllTasks"

and TopStateTransition =
    | InitDone
    | AnonPressedStart
    | PlayerPressedStart of SignedInGamer
    | SignOut
    | AllTasksKilled
    | Back

See how I used parallel pattern-matching? Whenever I have to write this kind of code in C# I find myself swearing silently...

Finally, the piece of code doing the dirty business.

// Initialization and killing of tasks.
        // Killing happens when a signed in player signs out.
        // Initialization happens during start-up and after killing.
        match !top_state with
        | Initializing ->
            scheduler.AddTask(main_task)
            top_state := (!top_state).Update(InitDone)
        | Player p when not(Gamer.IsSignedIn(p.PlayerIndex)) ->
            top_state := (!top_state).Update(SignOut)
            sys.StartKillAll(null)
        | KillingAllTasks when not(scheduler.HasLiveTasks) ->
            sys.StopKillAll()
            top_state := (!top_state).Update(AllTasksKilled)
            // Ideally, screen removal is done in finally handlers, and
            // killing should take care of removing all screens.
            // Nevertheless, we remove all screens here to be on the safe side.
            screen_manager.RemoveAllScreens()
        | _ -> ()

Game state management using cooperative multitasking

The game state management sample on the App Hub shows how to organize a game in screens. I strongly recommend all new-comers to game programming to study it, regardless of their amount of programming experience. Modern graphical non-game applications seldom follow this pattern, with the notable exception of step-by-step wizards.

The overview of this sample states:


The sample implements a simple game flow with a main menu, an options screen, some actual gameplay, and a pause menu. It displays a loading screen between the menus and gameplay, and uses a popup message box to confirm whether the user really wants to quit.
The ScreenManager class is a reusable component that maintains a stack of one or more GameScreen instances. It coordinates the transitions from one screen to another, and takes care of routing user input to whichever screen is on top of the stack.

A typical problem with this sample is that it is sometimes difficult to handle transitions from a screen to the next screen in the game flow.
For me, it's easier to specify the flow of screens from a bird's view:
The game starts with the press start screen, then the main menu is showed. Depending on the entry selected, the game may go into actual gameplay, show a credits screen...
When you implement your game, this bird view is not available by default. Instead, it's up to each screen to tell the screen manager which is the next screen to show when it's time for the first screen to remove itself. It's not unlike continuation-passing-style, in a way.

It is possible to do the inter-screen wiring from the top using events and handlers, but I find that using events and handlers for workflows is a bit ugly. The introduction of async in C# 5 indicates I'm not alone thinking that way.

To make things worse, providing the next screen to show with data it needs to initialize itself can get tricky if not carefully planned during the design phase. It also tends to cause "field overgrowth" in screen classes.

For all these reasons, I've been looking for a nicer solution using Eventually workflows and cooperative multitasking.

From the original game state management I have kept screens and the screen manager (on a conceptual level, implementation is new). These encapsulate state well, and I like the decomposition of a game into individual screens.

In particular, screens each have their ContentManager and load specific content when added to the screen manager, and release assets when removed. Sharing a ContentManager and keeping assets in memory is of course still possible using conventional methods.

The significant change is the removal of Update() and HandleInput() methods from screens. Instead, each screen has a number of Eventually computation expressions (which I also call tasks) which implement the logic of the screen.

To give a more concrete picture of the whole thing, here are bits from the MenuScreen. For full code, see github.

type MenuScreen<'I when 'I : equality>(
   player : PlayerIndex,
   sys : Environment,
   items : ('I * string)[],
   anim : AnimationParameters,
   placement : PlacementParameters) =

'I is a type parameter used to distinguish between entries. For instance, this discriminated union can be used for the main menu of a typical game:

type MainMenuEntries =
    | Play
    | Instructions
    | Options
    | Scores
    | Credits
    | BuyFullVersion
    | Exit

Back to MenuScreen, each constructor argument has the following role:
  • player is the index of the player who has control, i.e. the player who pressed "start" on the "press start screen"
  • sys is the object used to interact with the scheduler, which is used to spawn new tasks, wait, yield control...
  • items is a list of (menu entry - text) pairs
  • anim is a record whose fields control fade-in and fade-out effects
  • placement is another records controlling where the menu is rendered

inherit ScreenBase()

    // A mutable cell holding the index of the entry currently selected.
    let current = ref 0

    // An object wrapping a number of variables controlling fading effects.
    let animation = new Animations.MultipleFadeIn(sys, items.Length, anim.period, anim.shift)

    // Keeps track of button presses on the gamepad of the player with control
    let input = new InputChanges.InputChanges(player)

    // Array keeping track of the state of visibility of each entry.
    // Typically entries are visible, but some must be hidden or showed as gray
    // depending on whether the user is running the full version of the game
    // or the trial.
    let visibility = items |> Array.map (fun _ -> Visible)

    do if items.Length = 0 then invalidArg "items" "items may not be empty"

In the full code functions dealing with menu entry visibility follow, I'm skipping them in this article.

The really interesting part (IMHO) comes now:

member this.Task = task {
        this.SetDrawer(this.Drawer)

        let animator = sys.Spawn(animation.Task)

        let selected = ref false
        let backed = ref false
        while not (!selected || !backed) do
            // If this screen is not active, i.e. it is not on top or the guide is visible, wait.
            // We don't want to react to input that's not for us.
            do! sys.WaitUntil(fun () -> this.IsOnTop)

            input.Update()

            if input.IsMenuDown() then moveDown()
            elif input.IsMenuUp() then moveUp()
            elif input.IsStartPressed() then selected := true
            elif input.IsBackPressed() then backed := true

            do! sys.WaitNextFrame()

        animator.Kill()
        do! sys.WaitUntil(fun() -> animator.IsDead)

        return
            if !selected then items.[!current] |> fst |> Some
            else None
    }

If you are not familiar with F#, it's worth pointing out that "!selected" means the value of mutable cell "selected", not the negation of the value of variable "selected". I keep getting confused by that when I read F# code even today.

If you have read my earlier articles about the Eventually workflow and cooperative multi-tasking, it should be clear what this code does. Critics may point out that it does not differ much from the typical content of HandleInput in the C# game state management sample, and they would be right.
A small but important difference resides in the last lines, composed of a return statement.

Interacting with the rest of the program is greatly simplified, as shown by this code snippet:

use menu =
            new MenuScreen<_>(
                controlling_player,
                sys,
                [| Play, "Play now"
                   Instructions, "How to play"
                   Options, "Options"
                   Scores, "Scores"
                   Credits, "More information"
                   BuyFullVersion, "BuyFullVersion"
                   Exit, "Exit" |],
                menu_animation,
                menu_placement
            )

        // Show the menu
        screen_manager.AddScreen(menu)
        // Execute the menu's code, and get the selected item as a result
        let! action = menu.Task
        // We are done with the menu, hide it.
        screen_manager.RemoveScreen(menu)

        // Deal with the selection in the menu.
        match action with        
        // Back to the board.
        | Some Exit ->
            exit_game := true


If you are like me, you may have experienced that dealing with seemingly trivial tasks such as showing and saving highscores after "game over" is more pain than it should be. It involves multiple screen transitions and asynchronous file I/O that must be spread over multiple update cycles.

Here how it looks in F#:

// Deal with the selection in the menu.
match action with        
// Back to the board.
| Some Exit ->
    exit_game := true
        
// Start playing.
| Some Play ->
    // Create the screen showing the game.
    use gameplay = new GameplayScreen(sys, controlling_player)

    // Show the gameplay screen. Gameplay itself is in gameplay.Task
    let! gameplay_result = screen_manager.AddDoRemove(gameplay, gameplay.Task)

    // If the game wasn't aborted, and if a new high score was achieved,
    // add it to the score table and show the table.
    match gameplay_result with
    | Aborted _ -> ()
    | TooEarly (_, points) | TooLate (_, points) ->
        use results = new ResultScreen(sys, controlling_player, gameplay_result)
        do! screen_manager.AddDoRemove(results, results.Task)

        let player_name =
            match SignedInGamer.SignedInGamers.ItemOpt(controlling_player) with
            | None -> "Unknown"
            | Some player -> player.Gamertag

        let is_hiscore = (!scores).AddScore(player_name, points)

        if is_hiscore then
            // save the scores.
            if storage.TitleStorage.IsSome then
                do! storage.CheckTitleStorage
                let! result =
                    storage.DoTitleStorage(
                       score_container,
                       saveXml score_filename !scores)

                match result with
                | Some(Some()) -> ()
                | _ -> do! doOnGuide <| fun() -> error "Failed to save scores"
            // Show the scores screen.
            do! showScores

There is a lot more to be said, but that's enough for a single article. I think that these code extracts show how F# can simplify the development of games. If you are a C# programmer used to think "functional programming is too complicated for what I need", I hope I have managed to introduce the idea there are clear benefits to be gained by introducing F# in your toolbox.

This is still work in progress, you can follow it on bitbucket.
You can also follow me on twitter, I am @deneuxj there. The full source code of a small game demonstrating task-based game state management is also available on github, under Samples/CoopMultiTasking.
This game demonstrates the following features:
  • A typical "press start screen -> menu -> game" flow
  • Safe IO using StorageDevice, used for best scores and user preferences
  • Throwing back to the "press start screen" when sign-outs occur
  • Screen transitions
  • Input handling and pausing (not complete at the time of writing)
  • Content loading and unloading

Sunday, January 30, 2011

Safe IO on the Xbox 360 in F#

... or how computation expressions can help you write concise, clean and exception-safe code.

The XNA framework offers a number of APIs to access files. The Storage API, described on MSDN, is a popular one.

All seasoned XBLIG developers know that this API has a number of pitfalls that are not always easy to avoid. Here are those that come to my mind:
  1. Files can only be accessed after getting access to a storage device, which requires interaction with the user as soon as more than one storage device (hard-disk, memory unit, usb stick...) is available. As all of the steps cannot be performed within a single iteration of the update-loop, this forces the programmer to spread the steps over multiple iterations.
  2. Attempting to get a storage device while the guide is open results in an exception. The guide is a graphical interface to the console's "operating system" which is available at any time.
  3. At most one storage container may be in use at any time (a storage container is a collection of files, it can be seen as a directory).
  4. The user may at any time remove a storage device, which results in exceptions being thrown while accessing the device.
  5. File access is quite slow. In order to keep the GUI responsive, games must perform IO asynchronously.
Attempting to use the XNA API as it is almost invariably leads to bugs. I would say storage-related crashes are among the top 3 reasons games fail peer review. EasyStorage is a popular C# component that simplifies safe IO in games. In this article, I describe an alternative component written in F#.

Let us look at each pitfall and consider ways to avoid them.

Problem 1: Getting a storage device asynchronously


A simple popular solution consists of requesting the storage device, which is an asynchronous operation, and busy-wait until the operation completes when the user chooses a device.

let getUserStorageDevice player = task {
    let! async_result = doOnGuide(fun() -> StorageDevice.BeginShowSelector(player, null, null))
    do! waitUntil(fun() -> async_result.IsCompleted)
    let device = StorageDevice.EndShowSelector(async_result)
    return
        if device = null then
            None
        else
            Some device
}

This function takes a PlayerIndex and returns an Eventually computation expression (which I call a task). doOnGuide is another task which I describe shortly hereafter. Busy-waiting occurs in "do! waitUntil" on the third line.

Problem 2: Avoiding GuideAlreadyVisible exceptions


Whenever you want to open the guide to ask the user to choose a device, to show a message box, send a message to a friend, open the virtual keyboard, you must check whether Guide.IsVisible is false. Even if it is, you have to surround your call to the guide with a try...with block, as GuideAlreadyVisibleException may be thrown. It may surprise beginners, but so is the case, as I have experienced during peer review of Asteroid Sharpshooter.

let rec doOnGuide f = task {
    do! waitUntil(fun() -> not Guide.IsVisible)
    let! result = task {
        try
            return f()
        with
        | :? GuideAlreadyVisibleException ->
            do! wait(0.5f)
            let! eventually_some_bloody_result = doOnGuide f
            return eventually_some_bloody_result
    }
    return result
}

doOnGuide is a recursive function which repeatedly busy-waits until Guide.IsVisible is false. Then it tries to execute the provided function f. If GuideAlreadyVisibleException is thrown, it is caught, discarded, and doOnGuide calls itself again after waiting a short while. This additional wait for half a second is not strictly necessary, I put it there mostly because the idea of raising one exception per update cycle disturbed me a bit.

I don't find this repeated get-rejected-and-retry particularly pleasing to the eye, but if you have seen it's "hacked-the-night-before-sending-to-peer-review" variant in C#, you'll probably find my version decently pretty.

Problem 3: At most one storage container opened at any time


The solution is again pretty simple in principle: keep track in a central place whether a storage container is already opened. If it is, busy-wait until it isn't.

type Storage() =
    let is_busy = ref false
    member this.DoTitleStorage(container_name, f) = task {
            do! waitUntil(fun () -> not !is_busy)
            try
                is_busy := true

                let! result = doInContainer device container_name f
                return result
            finally
                is_busy := false
    }

Class Storage is the class that coordinates access to storage devices. Only parts of the class relevant to problem 3 are shown here.

The first line of method DoTitleStorage busy-waits until is_busy becomes false. When this happens, it goes ahead and immediately sets is_busy to true again. Readers concerned about race conditions and multiple waiters proceeding into the critical section unaware of each other may rest reassured: multiple tasks are picked and executed one a time using cooperative multi-tasking. True concurrency and its pitfalls are out of the picture.

Note the finesse about using finally to reset is_busy. We are not quite sure of what f will do in the container. Should it do something nasty and get surprised by an uncaught exception, the storage component won't be left in an unusable state. Doing proper clean-up and recovery in traditional asynchronous programming using events and callbacks can be difficult. Actually, the difficult part is to remember to do it when the code is turned "inside out".

Problem 4: Uncaring users yanking storage devices at inappropriate times


The only solution here is to sprinkle your code with try...with and checks for StorageDevice.IsConnected. Again, the availability of try...with in computation expressions makes it relatively painless in F#. See problem 2 above for a code example.

Problem 5: Asynchronous file operations


I haven't tackled this problem yet, mostly because I have only dealt with very small files so far (score tables and user settings). I will leave this for another post, if the need arises.
The only point I wanted to mention is that programmers should be wary of simultaneous progression in the GUI and asynchronous IO. Typical tricky situations include users quitting the game while data is being saved, triggering new IO while previous IO operations are still ongoing. For these reasons, it is advisable to limit the responsiveness of the GUI to showing a "please wait" animation, and busy-waiting until IO finishes.

Wrap-up

That's all for now. Complete code is available in XNAUtils. It's still work in progress, but it's already usable. It can be interesting to compare to an earlier attempt I did at dealing with the storage API, using state machines. The previous attempt is both longer in lines-of-code and harder to read. I think it's a lot easier to convince oneself or detect bugs in the newer version using Eventually computation expressions and cooperative multi-tasking.

Friday, January 21, 2011

Cooperative multitasking using the Eventually workflow

In cooperative multitasking at most one task executes at any time. In order for another task to execute, the task currently in control must explicitly pause itself. The scheduler keeps track of which task is executing, which tasks are ready to be executed and which are blocked or sleeping.

This form of multitasking lacks concurrency, which makes it easy for multiple tasks to synchronize and communicate. On the downside, it is not suitable for improving performance of cpu-bound computations.

I have implemented a cooperative-multitasking "operating system" consisting of a scheduler and a couple "system calls" which I believe will make it easier for me to develop the menu systems of my future games. In this article I describe the design and API of this light-weight operating system.

The scheduler


The scheduler is implemented in class Scheduler in CoopMultiTasking.fs, where these methods are available:
  • AddTask: A task is an Eventually<unit> computation expression, and can be added to the scheduler using this method. The task won't execute until method RunFor is called. A task is removed from the scheduler after it completes.
  • HasLiveTasks indicates if the scheduler has at least one task which hasn't completed.
  • RunFor executes all ready tasks for a specified amount of time. Typically, this should be 1/60 for a game running at 60 frames per second, but any value will do. It is for instance possible to "fast-forward" execution by passing durations that exceed the amount of real time that has passed. See "Simulated time vs real time" below for details.

The system calls


Class Environment makes it possible for tasks to interact with the scheduler to control their execution and spawn sub-tasks.
  • Spawn allows a task to add a sub-task to the scheduler. The scheduler returns an instance of TaskController which can be used to instruct the sub-task to complete early and to wait for the sub-task to complete early. Spawn does not actually take a task, but a function which takes a reference to a Boolean and returns a task. The Boolean indicates when the task should kill itself. See "Killing sub-tasks" below form more information.
  • SpawnRepeat is a variant of Spawn which executes a sub-task in a loop. It returns a TaskController which can be used to interrupt the loop. Unlike Spawn, this method expects a task. The sub-task should be very short, as an iteration of the loop cannot be interrupted.
  • Wait causes the task to wait a specific duration. Note that this duration does not correspond to real time, but to durations as passed to RunFor.
  • Yield causes the task to stop executing, but remain ready for execution. If another task is ready, the scheduler executes it, otherwise the task continues executing.
  • WaitNextFrame causes the task to stop executing until the next time the scheduler's RunFor is called.
  • WaitUntil takes a function with signature unit -> bool. The task is paused until the function returns true. The function is first evaluated in the current frame without waiting, then once per call to RunFor. Note that the first evaluation of the function is preceded by an implicit call to Yield.

Simulated time vs real time


The time inside this environment, which I call simulated time, does not correspond to real time. Simulated time passes every time RunFor is called by the amount of time specified to RunFor.

Even if you always pass to RunFor the amount of real time that has passed, the amount of time tasks wait is not coupled to real time. This is due to RunFor never sleeping, even when all tasks are waiting. Instead, it directly advances the simulated time.

Tasks which are waiting for durations exceeding the frame time wake up during the correct frame. Within a frame, tasks wake up in the correct order, in accordance to their amount of time left before waking up.

Killing sub-tasks


It is not possible to forcibly kill a sub-task. Instead, a notification mechanism using a reference to a Boolean cell is used. It is the responsibility of the sub-task to test this cell often enough that excessively long delays after requesting termination do not occur. I realize this may not be a popular design decision, as this forces one to sprinkle the code of tasks with checks for termination requests. The rationale behind this decision is that uncontrolled termination can leave an application in an incorrect state. I don't feel strongly about that point, though.