F# for game development

Units of measure for array indices

2012-02-14T10:21:00.000-08:00

In F#, arrays play an important part in optimizing performance-critical parts of your code. This is especially true on Xbox 360, where arrays of value types can help avoid snags due to slow garbage collection.Unfortunately, index out-of-bound exceptions are common when working with arrays. This post shows a little trick to help detect cases where the wrong variable is used as the index.

/// An array whose index has a unit of measure
type MarkedArray<[<Measure>] 'K, 'T> = MarkedArray of 'T[]
with
    member this.Content =
        let (MarkedArray arr) = this
        arr

    member this.First : int<'K> =
        LanguagePrimitives.Int32WithMeasure 0

    member this.Last : int<'K> =
        let (MarkedArray arr) = this
        LanguagePrimitives.Int32WithMeasure (arr.Length - 1)

    member this.Item
        with get (i : int<'K>) =
            let (MarkedArray arr) = this
            arr.[int i]
        and set (i : int<'K>) (v : 'T) =
            let (MarkedArray arr) = this
            arr.[int i] <- v

The interesting bit lies in the definition of this.Item. It allows to access the content of a MarkedArray using the usual array notation arr.[idx]

To illustrate how this is used, imagine you are making an Asteroids clone. You'll probably need arrays for the positions and velocities of the ships (assuming it's a multiplayer game), and similarly for the asteroids. Using units of measures as shown in the previous post will help avoid mixing speeds and positions, but it's still possible to pick a position from the wrong array.

This is the problem that MarkedArray solves, see below.

[<Measure>] type Ship
[<Measure>] type Asteroid

type State =
  { shipPositions : MarkedArray<Ship, TypedVector3<m>>
    shipVelocities : MarkedArray<Ship, TypedVector3<m/s>> 
    asteroidPositions : MarkedArray<Asteroid, TypedVector3<m>>
    asteroidVelocities : MarkedArray<Asteroid, TypedVector3<m/s>> }

let getShipPosition (state : State) (idx : int<Ship>) : TypedVector3<m> =
  state.asteroidPositions.[idx] // Fails: idx has the wrong type, expected int<Asteroid>

Note also that creating marked arrays isn't as tedious as one might fear, thanks to type inferrence

let state' = { state with shipPositions = state.shipPositions.Content |> Array.map f |> MarkedArray }

A small remark to finish off, this is how to iterate over all positions in a marked array, note the 1<Ship> increment:

for idx in state.shipPositions.First .. 1<Ship> .. state.shipPositions.Last do
  ...

By the way, both TypedVector3 and MarkedArray are available in XNAUtils on bitbucket.

Units of measure to the rescue!

2012-01-16T13:48:00.000-08:00

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.

Parallel draw-update XNA game component

2012-01-12T13:31:00.000-08:00

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!

Converting FS project files to target Xbox 360

2011-12-12T07:27:00.000-08:00

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.

Defeating the blank page

2011-11-12T08:38:00.001-08:00

Programmers have two ways to approach implementation of complex programs:

Start by building bricks, combine them to build larger bricks, repeat until the brick is actually a house.

Work the other way around.

The second approach is actually the more sensible one for new problems. In general, you know what is the problem you want to solve, not how to solve it. It's therefore easier to write the top-level of an application first.
The obvious problem is: On what do you build the top level?

There is a trick I used in F# that I wanted to share.
Consider the following problem: I want to implement a racing game, which requires multiple data structures to represent the track. In the track editor, the track is basically a curve controlled by a number of points and directions. In the game, the track is a set of triangles used for rendering and simulation.The problem is to convert a track segment defined using the first representation to the second.
A track segment is either linear (it connects two control points), a fork (for the entrance and exit of the pit lane) or a bridge. We can imagine other kinds of segments (+ and T -shaped crossings), but that's enough for a start.
I start with this function:

let triangulate segment =
   match segment with
   | Linear data -> ()
   | Fork data -> ()
   | Bridge data -> ()

It's not doing much, obviously. Let's look at the easy case first. A solution would be to get an ordered set of vertices for one side of the road segment, and another set for the other side.

| Linear data ->
   let leftSide = getLeftSide data
   let rightSide = getRightSide data
   knit triangles leftSide rightSide

This code isn't valid, because getLeftSide, getRightSide knit and triangles aren't defined. Let's add them as parameters to triangulate:

let triangulate getLeftSide getRightSide knit triangles segment =
   match segment with
   | Linear data ->
      let leftSide = getLeftSide data
      let rightSide = getRightSide data
      knit triangles leftSide rightSide

After a few more iterations of this I get the following function:

let triangulate getLeftSide getRightSide getLeftSideOfFork getLeftInner getRightSideOfFork getRightInner intersect glue knit triangles segment =
    let triangulateLinear data =
        let leftSide = getLeftSide data
        let rightSide = getRightSide data
        knit triangles leftSide rightSide

    match segment with
    | Linear data ->
        triangulateLinear data

    | Fork data ->
        let outSide0 = getLeftSideOfFork data
        let inSide0 = getLeftInner data
        let outSide1 = getRightSideOfFork data
        let inSide1 = getRightInner data
        let inSide0, inSide0', inSide1, inSide1' = intersect inSide0 inSide1
        knit triangles outSide0 (glue inSide0 inSide1')
        knit triangles outSide1 (glue inSide1 inSide0')
        knit triangles inSide0' inSide1'

    | Bridge data ->        
        triangulateLinear data.under
        triangulateLinear data.over

The function takes quite a few parameters, maybe too many. I can clean this up later after I have implemented getLeftSide and all other functions.

Notice how far I can get never worrying about types, yet I never need to worry about whether the parts fit together.

This way of writing code has helped me get over a number of situations where I was suffering some sort of "blank page syndrome", not knowing where to start to tackle a complex problem.
Of course, there is no guarantee that the final implementation will keep the same architecture, but at least I'm going forward!

An example of inheritance gone wrong

2011-09-23T13:13:00.000-07:00

In an earlier post entitled Why inheritance for code reuse should be avoided I pointed out that the key problem was conforming to the Liskov Substitution Principle.

Although I guess there is nothing controversial in what I wrote, I fear I probably did not convince anyone who wasn't already convinced.

Today at work, I had the pleasure of being hit by a bug that is a wonderful example of inheritance gone wrong.

Let me give a bit of context. Once upon a time there was an application that allowed viewing and editing a database in a nice and user-friendly somewhat buggy GUI. As it was felt the application could be user-friendlier and more stable, additional development efforts were planned to improve it. This logically led to the decision of distributing what was a stand-alone file-oriented program over a server-client architecture.

In case you hadn't noticed, I'm being a bit sarcastic, but the fact is that the original plans for the application included extensions to a server-client architecture, and the source code was cleanly organized in modules, keeping the GUI and the database separated by a middle layer.

When moving to the new architecture, it felt natural to turn the middle layer into a web service. This required all data types in the API of the middle layer to be serializable so that they could be sent over the net between the client (the GUI) and the server. This was fairly easily achieved using WCF and DataContract.


[DataContract]
class Item {
   [DataMember]
   public int Data { get; set; }
}

Today, I opened a bug report with an unexpected exception stating that a type named "...Dialog+GuiItem" could not be serialized. Indeed, I could recognize the "Item" part, which was serializable thanks to DataContract, but the GUI component most certainly wasn't! What was going on there?

Looking at the definition of Item, I could see it was a fairly simple type GuiItem augmenting a simple data-type (called Item) with GUI thingies.


class GuiItem : Item {
   public Gui SomeGuiStuff;
}

The problem is, the GUI-augmented type couldn't provide all features the basic type did: It could not be sent over the net.

In the first version of the software, passing the GUI-augmented instance to the middle layer was not a problem. The middle layer expected a basic Item or anything that can be implicitly converted to such an item. As long as all passing of arguments occurs within the same process, no additional effort or processing was needed.


class MidLayer {
   public void DoSomething(Item item);
}
...
void OnClick(GuiItem item) {
  midlayer.DoSomething(item); // Fine, GuiItem is also an Item.
}

In the new version, passing arguments is a significantly more complex operation involving doing a deep dump of the content of the instance, streaming over the net, and summoning a new instance stuffed with the dump on the other side of the wire. This only works for types which are purely data-oriented. Inject any kind of "live" resource in there, and you are out of luck.


[WebService]
class MidLayer {
   [WebMethod]
   public void DoSomething(Item item);
}
...
void OnClick(GuiItem item) {
  midlayer.DoSomething(item); // Exception: can't serialize GuiItem!
}

The solution was simple enough, simply include the basic Item as a member of the GUI-augmented type, and provide a getter to easily send it from the GUI to the server.


class GuiItem {
   Item item;
   Item Item {
      get {
         return item;
      }
   }

   public Gui SomeGuiStuff { get; set; }
}

void OnClick(GuiItem item) {
  midlayer.DoSomething(item.Item); // Fine again.
}

When inheriting from a type, you don't just get its nice features, but also its responsibilities.

New e-book: FRIENDLY F# with game development and XNA

2011-08-21T00:28:00.000-07:00

I received a mail from Giuseppe Maggiore, one of the authors of a new book: FRIENDLY F# with game development and XNA. Giuseppe helped me put together the project templates for F# and XNA on the Xbox 360.

The main subject of the book is the F# language and its various
constructs, but every single chapter is centered around a game-related
problem. Each one of the first 5 chapters describes a problem, shows
and discusses its solution and then discusses in depth the F#
constructs used. The book has a (relatively rare) "problem-solution"
approach where everything is explained because of how well it works in
solving the problem, and not just "because". The 5 problems we present
are:
- a bouncing ball
- the Saturn V rocket
- an asteroid field
- a large asteroid field optimized with quad trees
- a police starship that must fight off a pirate ship attacking a
cargo freighter
In the last two chapters we use XNA to build a 2D and 3D renderer for
two of the samples we have seen. We show the basics of the SpriteBatch
class, the Model class, input management and audio with this powerful
framework. Basically, we cover the most important aspects of XNA in a
simple and succint way.

I had a quick look at the book and I think Giuseppe's description is a fair one. In other words, this is not a book primarily about game programming, but an introduction to F#. Although it touches some advanced topics such as custom workflows, it is not a comprehensive coverage of the language.
All in all, if you are looking for a gentle and quick introduction to the language, and you are interested in game programming, you should definitely check this book.

The book is available on Amazon and Smashwords.

The forgotten control flow construct

2011-08-03T09:32:00.000-07:00

There is a truly powerful control flow construct that many programmers have forgotten. It helps implement complex flows that ifs, whiles and matches can't handle. Not even throwing and catching exceptions can measure itself to this construct.

You may wonder what kind of situation would require something that traditional constructs can't handle. Here is an example taken from Go To Statement Considered Harmful: A Retrospective.

int parse()
{
    Token   tok;

reading:
    tok = gettoken();
    if (tok == END)
        return ACCEPT;
shifting:
    if (shift(tok))
        goto reading;
reducing:
    if (reduce(tok))
        goto shifting;
    return ERROR;
}

Let's see how using a while turns out:

type Token = END

type ParseState = Reading | Shifting | Reducing | Accepted | Errored
type Status = ACCEPT | ERROR

let parse gettoken shift reduce () =
    let mutable state = Reading
    let mutable tok = Unchecked.defaultof<Token>
    
    while state <> Accepted && state <> Errored do
        state <-
            match state with
            | Reading ->
                tok <- gettoken()

                if tok = END then
                    Accepted
                else
                    Shifting

            | Shifting ->
                if shift tok then
                    Reading
                else
                    Reducing

            | Reducing ->
                if reduce tok then
                    Shifting
                else
                    Errored

            | Errored | Accepted -> failwith "Invalid state"

    match state with
    | Errored -> ERROR
    | Accepted -> ACCEPT
    | _ -> failwith "Non-final state"

(Note that I have introduced extra parameters gettoken, shift and reduce; I wanted to be able to write concise code that syntactically correct without explicitly defining these functions).

It looks OK, but we had to introduce an extra type, ParseState. There are also some issues with mutability and initialization of tok.

If you have some experience with functional programming, you are probably thinking that recursion is the right tool. I will leave writing a recursive version of parse to the reader, and jump to a slightly different idea that many might have missed.

type Token = END | SOMETHINGELSE

type Status = ACCEPT | ERROR

let parse gettoken shift reduce () =
    let rec do_read() =
        match gettoken() with
        | END -> ACCEPT
        | _ as tok -> do_shift tok

    and do_shift tok =
        if shift tok then
            do_read()
        else
            do_reduce tok

    and do_reduce tok =
        if reduce tok then
            do_shift tok
        else
            ERROR

    do_read()

do_read, do_shift and do_reduce are mutually recursive functions. All recursive calls are in tail position, which makes it possible to avoid stack overflows (on some platforms...).

Here you have it: calls in tail position are basically safe versions of goto.

The fantastic control flow construct that many have forgotten is simply the procedure call. Every programmer uses it a countless number of times every working day, but fear of recursion and stack overflows have kept many from using it in situations where it fits well.

Is it worth it?

2011-08-02T08:58:00.000-07:00

In my previous post, I explained why inheritance for code reuse is a bad idea. The blog was a bit on the theoretical side, and I wanted to know if I wasn't sitting in an ivory tower.

For this reason, I have decided to rewrite one of my uses of inheritance by composition. The piece of code in question is the BaseScreen class in XnaUtils.

Before I go any further, I need to give you a bit of context. The user interface of video games is usually composed of screens. The library provides a class called ScreenManager which is responsible for managing stacks of screens, notifying each screen when to load/unload resources such as textures...

I have created an interface named "Screen" which serves as the interface between the framework and the screens in a game. The framework also provides a few screens which can be used in simple games, namely TextScreen, MenuScreen and PressStartScreen.

These screens all share common functionality which I needed to put somewhere to avoid code duplication. In my first version, BaseScreen was an abstract class from which screen implementations inherited, overriding a few key methods to customize rendering.

Differences in ScreenBase

The changes are not very extensive. Abstract methods were replaced by fields. Instead of defining overrides, inheritors set properties using lambdas.

+    let post_drawer : ('T -> unit) ref = ref (fun _ -> ())
...
-    abstract member EndDraw : 'T -> unit
-    default this.EndDraw(_) = ()
-
+    member this.PostDrawer
+        with get() = !post_drawer
+        and set(d) = post_drawer := d

Differences in inheritors

A few "this" had to be replaced by "impl", the name of the variable I have used to hold the instance of ScreenBase.

type PressStartScreen(sys : Environment, fade_in, fade_out, blink) =
-    inherit ScreenManager.ScreenBase<unit>()
+    let impl = new ScreenManager.ScreenBase<_>()
+    let impl_screen = impl :> ScreenManager.Screen

// Task to check if a button is pressed. Sets player when that happens.
let player : PlayerIndex option ref = ref None
while (!player).IsNone do
-            do! sys.WaitUntil(fun () -> this.IsActive)
+            do! sys.WaitUntil(fun () -> impl.IsActive)
for p in all_players do
let state = GamePad.GetState(p)
if state.IsConnected

Boiler-plate code had to be written to implement interfaces Screen and IDisposable, forwarding calls to "impl". As ScreenBase implements these interfaces explicitly, I had to introduce an extra variable "impl_screen" to refer to impl's implementation of Screen. Otherwise, I would have had to use casts in all forwarding code, as shown in the implementation of IDisposable.

+    interface ScreenManager.Screen with
+        member this.ClearScreenManager() = impl_screen.ClearScreenManager()
+        member this.Draw() = impl_screen.Draw()
+        member this.LoadContent() =
+            impl_screen.LoadContent()

+
+    interface System.IDisposable with
+        member this.Dispose() = (impl :> System.IDisposable).Dispose()
+

Advantages of composition and delegation over inheritance

1. Inheritors can reuse code from multiple classes (F# does not have multiple inheritance).
2. The code for ScreenBase is a bit shorter.
3. Inheritors have more control.

Advantages of inheritance over composition and delegation:

1. The "IDisposability" of ScreenBase is implicitly propagated to its inheritors.
2. No risk of errors in delegation.
3. The code for inheritors is shorter.

Conclusion

Although I believe most of the weaknesses of the approach using composition and delegation could be lifted by additions to the F# language, in its current shape, I would not dare to force users of my library to use composition.

The ideal solution is to write my library code to allow users to use the approach they prefer, which I expect would be inheritance in most cases. Providing this approach as the only one is not acceptable, as it would prevent users to reuse features from multiple classes.

Why inheritance for code reuse should be avoided

2011-07-17T03:21:00.000-07:00

The question of when to use inheritance and when not to has been asked many times. I have noticed answers can be put in one of three categories:

1. Use as much as you can. It's a convenient way to maximize code reuse with very few keystrokes. Actually, this answer is seldom explicitly given, but if I judge by the code I see, this is a wide-spread opinion.

2. There are situations when inheritance is appropriate, and situations when it isn't. Namely, inheritance is appropriate to express IS-A relationships.

3. Never use it for the purpose of code reuse. Some take it even further and say never use it at all. Inheritance is flawed by design.

Throughout my life as a programmer, I have gone through all of these stages, in order. I think most of the controversy focuses on inheritance for the purpose of code reuse, and I'll start with that.

Inheritance for the purpose of code reuse
The first answer is easy to discard, as explained in this answer on the programmers stackexchange. Systematically using inheritance quickly leads to excessively large objects. The author of the code probably won't see this as a problem at first, and may indeed be oblivious to the problem. Unfortunately, this makes it very easy to fall into this trap.

The second answer begs for an answer to the question "what is an IS-A relationship?". I find that all IS-A relationships can be expressed as HAS-A, and vice-versa. Taking the usual example of cars, we can say a car has four wheels, and it is a four-wheeled vehicle. A car has an engine, and it is an engine-powered vehicle. Which is the correct way of expressing relationships between cars and their components?

Instead of relying on IS-A vs HAS-A, one can use the Liskov Substitution Principle (LSP), as pointed out in this other answer.

Informally, the principle states that if B inherits from A, then B must be usable in all places where A is used.

This is a bit of a loose definition, and even the more formal definition by Barbara Liskov and Jeanette Wing stated below invites further questions.

Let q(x) be a property provable about objects x of type T. Then q(y) should be provable for objects y of type S where S is a subtype of T.

What is the proof system assumed here? What kind of sentences can be expressed? Do the axioms include knowledge about the program?

Informally, how should "usable" be interpreted in the informal statement of the principle?

I don't think there is a single fit-all answer to this question. There are a number of aspects to consider, which all affect the initial development time and degree of maintainability of a software project.

Language Semantics.
Note that a language which allows to query the concrete type of an object makes it impossible to meet the LSP.

let f (x : A) =
    match x with
    | :? B -> failwith "Failing!"
    | _ -> x.DoSomething()

Obviously, an instance of B cannot be used with f, as it would cause the program to behave differently as when provided with instances of A (or some other subtype of A).

Notion of equivalence.
That instances of B can be used instead of A means that the behavior of the software when B is used is "observably equivalent" to that of the software when A is used.

There are different levels of strictness regarding equivalence. Including internal state in the observable behavior is a bad idea, as this forbids method overriding and polymorphism.

Even limiting oneself to "user-visible events" may be too limiting, as this closes the door to plug-ins that extend or modify functionality.

In the end, I think a popular but very weak notion is whether the program crashes or not. And even that may be too strong, as it's probably acceptable for instances of B to work where instances of A crash (OK, that's nit-picking).

Scope.
Does "all places where A is used" refer to the places as they exist in the current form of the software, in the current and expected future forms, or in all possible forms?

There is a bit of overlap with the first aspect. When assuming the scope is limited to the current state, and if no concrete type tests on instances of A are made anywhere, then meeting the LSP seems feasible.

Assuming the second alternative (current and expected future forms) requires either a clear idea of what the future looks like, or a coding standard prohibiting the use of all language constructs potentially incompatible with the LSP.

If you are designing a library or framework to be used by other parties you don't control, you are condemned to the last option, "all possible forms". Unless you have a low level of ambition on the notion of equivalence, the LSP is impossible to meet in this setting.

There may well be other aspects I haven't thought of, but I hope I made it clear that the LSP isn't quite as simple as it may seem at a first glance. Using inheritance only "when it conforms to the LSP" often equates to "never" if one really cares about the LSP. Moreover, it requires an understanding of the principle itself as well as clearly identifiable decisions on all the points mentioned above, two conditions which are not met that often out-there-in-the-real-world.

Note that it's possible and indeed desirable to specify limitations on language features, equivalence and scope on a per-type basis. Doing it on a project-wide level would probably make it impossible to respect the LSP.

Inheritance limited to interfaces
My standing on the question of inheritance when limited to interfaces is not quite clear yet. I can't quite put my finger on the exact problem yet, so I'll leave it to another day to express my thoughts in details on the subject.

Shortly, it seems to me this kind of inheritance brings little, if anything at all, over composition. The argument of the "keystroke minimality" applies only to subtyping between interfaces, which I have had little practical use for so far.

Alternatives to inheritance
Composition is often cited as the right way to take advantage of code reuse. To put it mildly, mentioning it often fails to trigger the enthusiasm of proponents of inheritance for code reuse. It's easy to understand why:

type A =
   ...
   member this.DoSomething1() = ...
   ...
   member this.DoSomething15() = ...

type OhForGodsSake_B =
   let an_a : A = ...
   member this.DoSomething1() = an_a.DoSomething1()
   ...
   member this.DoSomething15() = an_a.DoSomething15()

type WhatABreeze_B() =
   inherit A()

Indeed, there is something to be said for the second approach. I wish F# had some way to achieve the conciseness of inheritance through composition, but that's not the case. This may be an oversight, or may be by design. As Matthieu M. writes in his answer, forcing verbosity can be beneficial:

[It] means that at least a couple keystrokes are needed for each method, and suddenly people begin to think about whether or not it's such a great idea to reuse this "fat" class for just a small piece of it.

I would add that this would also force the author of B to think about whether all 15 DoSomething() methods really are needed in B, or if it's enough to provide just a few of them.

By the way, should the methods in B have the same name as their counter-parts in A? If A is "VehicleWithWeels", and "B" is "Airplane", it makes sense to expose "VehicleWithWeels.Brake" as "Airplane.BrakeWithWheels", as airplanes have different means of braking. It's easy to miss that subtle point when using inheritance.

All-in-all, I don't think I should value my laziness and comfort over cleaner code, at least not in a professional setting. Still, I can't help being lazy... Programming isn't all about writing clean code, it's about having fun too.

When dealing with implementation relationships between concrete types and interfaces, I am happy with seeing it as "HAS-A" kind of relationship, or more precisely (and verbosely) "OFFERS-FUNCTIONALITY-AS-SPECIFIED-BY-INTERFACE". This can be achieved in two ways in F#:

// Explicit implementation
type B1 =
   ...
   interface A with
      method this.DoSomething() = ...

// Composition using object expressions
type B2 =
   ...
   member this.AsA() =
      { new A with
           member x.DoSomething() = ... // Note "x" vs "this". "this" refers to B2.
      }

The first approach can be used when it's clear B1 can only provide A in one single sensible way at all times, the second approach is more general and flexible. One might wonder if the second approach shouldn't always be preferred. Where do extremes end? ;)

OOP without classes in F#

2011-07-15T03:04:00.000-07:00

Did you know that F# allows to use some object-oriented features with types that are not classes? This includes methods, dynamic dispatch, open recursion and encapsulation.

Methods are functions or procedures which are tightly coupled to a type of object.

Dynamic dispatch is the ability to execute different implementations of an operation depending on the concrete types of arguments. A special case which often has dedicated syntax is when the operation is a method, and the argument controlling the dispatch is the object itself.

Open recursion makes the object available to its methods through an identifier, typically called this or self.

Encapsulation restricts access to the internal data and operations of an object to a restricted area of the code. Typically this area is the methods of the object itself, F# works at the module level instead.

The code below shows how a vector type can be defined using records.

[< CustomComparison >]
[< CustomEquality >]
type Vector2 =
    private { x : float
              y : float }
with
    // Constructors
    static member New(x, y) = { x = x; y = y }
    static member Zero = { x = 0.0; y = 0.0 }

    // Accessors
    member this.X = this.x
    member this.Y = this.y
    member this.Length = let sq x = x * x in sqrt(sq this.x + sq this.y)

    // Methods
    member this.CompareTo(other : obj) =
        match other with
        | null -> nullArg "other"
        | :? Vector2 as v -> this.CompareTo(v)
        | _ -> invalidArg "other" "Must be an instance of Vector2"

    member this.CompareTo(other : Vector2) =
        let dx = lazy (this.x - other.x)
        let dy = lazy (this.y - other.y)

        if dx.Value < 0.0 then -1
        elif dx.Value > 0.0 then +1
        elif dy.Value < 0.0 then -1
        elif dy.Value > 0.0 then +1
        else 0
        
    // Overrides for System.Object
    override this.ToString() = sprintf "(%f, %f)" this.x this.y
    override this.Equals(other) = this.CompareTo(other) = 0
    override this.GetHashCode() = (this.x, this.y).GetHashCode()

    // Explicit interface implementations
    interface System.IComparable<Vector2> with
        member this.CompareTo(other) = this.CompareTo(other)

    interface System.IComparable with
        member this.CompareTo(other) = this.CompareTo(other)

    interface System.IEquatable<Vector2> with
        member this.Equals(other) = this.CompareTo(other) = 0

The use of private on line 4 makes the representation (not the type itself or its methods) private to the enclosing module (Thanks to Anton for pointing that out in the comments).
Members can access the object through an identifer (this), and open recursion is covered.
Vector2 can be used as one would expect to be able to use an object, as illustrated below.
Dynamic dispatch is exercised by Array.sortInPlace (which calls CompareTo).

let playWithIt() =
    let v = Vector2.New(0.0, 2.0)
    let v2 = Vector2.New(v.y, -v.x)
    printfn "%s and %s have %s lengths"
        (v.ToString())
        (v2.ToString())
        (if (let epsilon = 1e-6 in abs(v.Length - v2.Length) < epsilon)
            then
            "close"
            else
            "different")
        
    let rnd = System.Random()
    let vs = [| for i in 1..10 -> Vector2.New(rnd.NextDouble(), rnd.NextDouble()) |]
    Array.sortInPlace vs
    printfn "%A" vs

I cannot write an entire article about OOP and not mention inheritance. F#-specific datatypes do not support inheritance, but I will try to show in a later post why this is not as big a problem as one might think.

Reference-counting just isn't enough and actually is harmful

2011-07-08T07:04:00.000-07:00

I recently came across a blog entry titled "Why Garbage Collection is not Necessary and actually Harmful".

I used to share the same opinion in my C++ days, when I used to think no better language could be written. A few years later, I have drastically changed my opinion on the subject. I am not going to address all points made against garbage collection, and instead will focus on one issue: The claim that reference-counting is a viable alternative.

Reference-counting is an automatic memory management system where memory allocated to an object is freed when the object is no longer referred to. C++ makes it relatively easy to replace pointers by wrappers that act like pointers, with the addition that reference counts in objects are automatically increased and decreased, as wrappers are created and destroyed.

Reference-counting by itself is flawed as it does not account for cycles. The aim of automatic memory management is to deallocate memory when it is no longer reachable from the program. Reference-counting deallocates memory when it is no longer reachable from reference-counted objects. These two coincide only in the absence of cycles (and provided a number of other conditions are met, e.g. all reference-counted objects are referenced through wrappers)

Edaqa says:

simple reference counting also covers the vast majority of memory management needs. Sweeping collection has a distinct feature of being able to resolve cyclic dependencies. That is when A points to B and B points to A. Reference counting cannot manage this in the general case.

Obviously if you have such a feature you will make use of it. I don’t see however that cyclic dependencies are a significant obstacle in most programs. Such object relationships can normally be resolved, or significantly mitigated, by one of a number of other techniques.

I strongly object to the claim that cyclic dependencies are not a significant obstacle in most programs. It may be so in version 1.0 of a program, but even that is stretching it. A reference-counting based memory recollection can introduce enough chaos into a software product that early retirement may be needed earlier than expected.

Potential cyclic dependencies are hard to detect.

It might seem at first that it should be possible and easy to detect cycles when looking at the class diagram. In practice, detecting loops involving more than 3 steps is in my experience tricky. Maybe not when you first design your classes, but when you or someone else alters it later. A developer who does not have the entire class diagram at his disposal or in his mind simply cannot know whether an addition can introduce cycles or not.

Actual cyclic dependencies are harder to detect.

Cycles at the class level are not necessarily problematic. There are moreover very common. Consider for instance the usual definition of lists:

template<typename T>
struct Node<T> {
   T data;
   struct Node<T>* next;
};

Although it is in theory possible to create a cyclic list, this should never happen in any run of the program. How does one convince oneself that this is indeed the case? The problem is solved for lists through the use of a safe API, but home-made more complex types seldom offer such an API.

There is no easy way to deal with cycles.

In order to avoid memory leaks, cycles must be broken in one way or another. This involves manually decreasing the count of an object, or simply not accounting for a reference.

The problem here is which link to choose in the cycle? Obviously, the link must be part of the cycle. Finding a candidate can be difficult by itself for the reasons mentioned above, and there is another restriction. The candidate link must never be a potential member of a cycle-free path for any run of your program, or you might end up deallocating objects that are still in use.

Conclusion

The real problem with reference-counting and avoiding cycles is that there is no good way to convince oneself of the absence of bugs through static analysis or inspection of source code. Absence of cycles is a dynamic property of program runs, and is therefore difficult to analyse. Testing might help, but to my knowledge, few write and maintain test cases specifically for the purpose of validating reference counting.

What makes matters worse is that it's very easy to mistake reference-counting pointer wrappers for substitutes to classic pointers. Systematically using the wrappers often ends up introducing memory leaks. Fixing them introduces dangling pointers.

Mark-and-sweep is no silver bullet, but at least it's a bullet aimed in the right direction.

My impressions of F# after three years

2011-06-26T02:02:00.000-07:00

It will be soon 3 years that I have been using F# both professionally and privately.

At work, I have used it to implement the simulator module of Prover iLock. This is a complete rewrite of the first version of the simulator, which was initially written in C#. The rewrite was necessary for a number of reasons. As is often the case with the first version of any software, its design did not age well, leading to bugs, excessive memory use and long execution times. I think the main reason was simply that requirements were not clear when the project was started.

The main challenge of this simulator is to support distributed systems where components use different execution models and link protocols. The term "execution model" is a bit specific to the field, namely railway signalling systems. Historically, these systems were implemented using relays. Their modern counter-parts include relays (they are still popular), software which emulates relays (to take advantage of existing field knowledge and practices) and to a lesser extent procedural languages.
The second category include platforms such as VHLC and Microlok, but there are many other similar yet different technologies. Although similar, they all differ slightly in how they handle communication with remote devices, how timers are handled, in what order instructions are executed...

I am happy to report that so far, most of the objectives for the new implementation have been reached or exceeded:

Adding a new platform takes little effort.
Memory use has drastically gone down, despite massive use of short-lived arrays to hold state.
Run-time efficiency is OK, although a bit worse than the first version in some cases. The main reason here is that I made no attempt to perform some of the optimizations that introduced bugs in the first version (maintaining consistency with respect to time when simulating distributed systems is difficult).
Few known bugs.

Time will tell how this second version ages, but so far, I haven't needed to spend a lot of time extending or fixing it. Which is a bit sad, as it means I am not spending as much time working with F# as I would like :)

Another important F# module I developed was a bridge translating the C# representation of systems from the main program to the simulator module. This other project is also successful. The main lesson learned is not to reuse data between different software modules. This may sound surprising at first, but the gains of designing data structures that do one thing well outweigh the costs of maintaining similar types which appear to duplicate code. The data structures in the main program are designed to make it easy to build and modify them via a scripting API. The data structures in the simulator are designed for efficiency of simulation.

Defining types in F# is easily done thanks to records and discriminated unions. Translating from one type hierarchy to another is facilitated by pattern matching. I'm inclined to think the lack for these constructs in other languages leads to excessively large and complex data-types, as they try solve multiple problems at once. Although the evils of code duplication are well known, there are also risks associated to excessive code sharing. Getting the right balance in the number of data types requires a flexible and rich family of types, and it's now clear to me that C# is too poor in that respect. Classes and enums are not enough.

I have used F# in a range of projects, mostly game-related. Asteroid Sharpshooter was released in January. Although not a commercial success (168 copies sold so far), it showed it was possible to write games with high performance requirements in F#, despite the weaknesses of .Net on the Xbox 360. I have not gotten a single bug report so far, but this may be due to the small amount of users. Its rating of slightly over 3 stars out of 5 seems to indicate users are moderately satisfied with the game.

I have also developed a "new" way of developing game user interfaces which I think blows the "old" way out of the water. The new way I am referring too allows to write reactive UIs over the game update loop in a simple way, allowing for much faster development and more robust software. The old way either leads to unresponsive interfaces or buggy ones that fail to deal with storage management or any other lengthy processing requiring asynchronous programming. I doubt many programmers without a functional background realize the power of computation expressions in F#.

By the way, I often hear and read that "F# is not good for UI". This is total nonsense. I normally try to express myself in a gentle, moderate, non-controversial way on this blog, so just to emphasize how I feel about this:

"F# is not good for UI" is total nonsense.

There are basically two problems with UI.

Lots of boring code to write: widget layout, boiler-plate...
Achieving good responsiveness

Point 1 is addressed by tools and code generation, and is actually language-independent. What do I care if automatically-generated code is in C#, IL or F#? As long as I don't have to write it...

Even in the case when I do write the code myself, I don't find C# and F# to differ significantly in that matter. F#'s supported for nested variable and function definitions help limit the number of members in a class, which avoids one of C# problems, namely over-blown classes with numerous private fields and methods.

Point 2 is solved by F#'s async. In that respect, I wonder how people have been dealing with the problem in C#? BackgroundWorker and threads are not so fun to use.

In all my projects, I think I have noticed two strong differences with developing in a C++-like procedural language:

I spend a lot less time debugging. Modulo trivial bugs, functional code that is correctly typed just works out of the box. Any time I went out of the pure functional path to introduce mutability, direct access to items in arrays... I introduced bugs.
The relatively low verbosity of F# and its high-level constructs make it easier to implement more complex algorithms. For instance, I could never get my head around Runge-Kutta(4) in C++, implementing it in F# was trivial, all while learning F#.

On the negative sides, I found that Visual Studio's debugger can be difficult to use with F#. In other words, it's good you don't spend a lot of times debugging, because it can be hard to understand what's going on in the debugger. Two of the main issues, I think, reside on the one hand in the fact that a debugger is statement and line oriented, where a functional language is expression-oriented, and on the other hand in a somewhat confusing handling of F# closures and lambdas by the debugger. For instance, debugging code in computation expressions is close to impossible.

That's all for now. If you are decision-taker in your company, and .Net is part of the technologies you use, I think you simply cannot afford not looking at F#. I know every time a new language is introduced, productivity gains are claimed by its inventors.

I did not invent F# and don't work for Microsoft, but I can vouch for the alleged productivity gains. Your mileage may vary, but I don't think it will.

Is that a cloud, or is it a storm?

2011-06-10T02:42:00.000-07:00

I was recently forced to spend some time at a hospital due to a bowel inflammation. The inflammation is due to a chronic disease whose cause is still unknown. It's also not clear whether there are non-surgical treatments to completely cure the disease. I won't go into details in this post, suffices it to say the event has distracted me a bit from my usual focus on games, Xbox360 and XNA.

Let me start with a few words about nutrition journals. Although there is little scientifically established information about the link between food types and inflammations of the digestive tract, many patients report that specific diets do help. The problem is that there does not seem to be any single diet that fits all.

It is therefore important for each individual to assess the effect of each food type on one's digestive system. Any good programmer knows it: before you optimize, you need to measure. The same goes for nutrition. Before doing changes to one's regime, it is important to keep track of what goes in and, well, what comes out.

The difficulty is that keeping such a journal requires discipline, as it's best to record that information as soon as meals are eaten, and directly after visits to the bathroom.

This is were mobile devices and the net comes into the picture. Smart phones make it easy to fill in the journal. The journal itself is probably best kept on a central server (in the "cloud") in order to be accessible from anywhere at any time through any device.

All of this is a good excuse for me to start having fun with WebSharper and F#, of course. WebSharper makes it possible to design web applications entirely in F#. The client code is compiled into javascript and executed in the browser.

The recent panic about .NET and Silverlight being dropped from Windows 8 is interesting in many aspects. .NET developers are reluctant to switch to javascript, a feeling I share and understand. The current tendency however seems to use javascript as a virtual machine targeted by a range of nicer technologies. Examples include F# through WebSharper, XNA, emulators... I for one rejoice in Microsoft's adoption of open standards.

But do I? I see Windows 8 as an attempt to regain control over the Web. What place will have competing web browsers (Firefox, Google Chrome, Opera...) in the new operating system when it includes it's own browser as a mandatory component? If the web view of Windows 8 succeeds in pushing out other browsers, Microsoft will be free to invent new technologies, forcing others to play catch up. Are we getting back to the Windows 98 and "optimized for IE6" days?

Happily, I don't see that happening. Non-Microsoft smart phones and tablets have conquered large portions of territory once owned by Microsoft and Intel. Hopefully HTML5+js will gain adoption and proper support across all platforms.

Note that the irrelevance of platform-specific technologies such as Silverlight applies to others as well. Why keep making iPhone and Android apps when you can make a web app instead? Are the specificities of GUIs compelling arguments to redevelop client apps multiple times? Will users be willing to pay for apps when free web apps become ubiquitous?

We can turn to the PC platform to find hints of answers. The computing power they offer still has no equivalent in the cloud, and demanding applications such as development tools, CAD and video games will always feel best at home on a PC. I expect those applications to keep being developed using a mix of native and VM-based languages and frameworks.

Is there a similar place on the smart phone? Applications requiring unrestricted access to the mobile's resources come to my mind. This includes media players, games, device management... I expect however that a very large eco-system based on "silly apps" will soon disappear, possibly in a very sudden manner.

The myths about the risks of introducing F# in your development team

2011-05-03T14:52:00.000-07:00

At work we are a couple people who have been using F#. All people who have used it are enthusiastic, yet I was surprised today when I heard a project leader had asked to limit the use of F#.

There is a question on programmers' stack exchange which touches the subject titled "Real world pitfalls of introducing F# into a large codebase and engineering team". I'm quoting:

1) Everyone has to learn F#, and it's not as trivial as switching from, say, Java to C#. Team members that have not learned F# will be unable to work on F# parts of the codebase.
2) The pool of hireable F# programmers, as of now (Dec 2010) is non-existent. Search various software engineer resume databases for "F#", way less than 1% of resumes contain the keyword.

The fear is that maintaining F# code might be difficult because current employees and job applicants lack functional programming skills.

It seems some decision makers are still stuck at the time when C# 1.0, C++ and Java 2 were the languages of choice. Since then, a few things have happened.

Firstly, Python has become hugely popular. Although many were horrified by its use of white space to delimit blocks, it would be difficult to take seriously a programmer who claims he can't adjust to Python's syntax. Some love it, some hate it, but all can write Python code.
Why would the syntax of F# be any harder to adopt?

Secondly, C# has introduced a number of functional programming and other high-level concepts in each new version that has come out. Modern C# programmers are expected to master LINQ to objects, lambdas and yield return. The next version will introduce a specific syntax for asynchronous programming. Would you consider hiring a programmer would admits he knows nothing about these features and is unwilling to learn about them?
F#'s higher order functions, functions as first-class citizen, sequence expressions and asynchronous workflows match directly the modern features of C#. Why would these be harder to use in F# than in C#?

Dear reader, if you are a decision maker, I hope these two simple remarks dissipated your fears. You may be wondering why adopt F# when C# is evolving? You won't hear it from Microsoft, but the fact is that C# is breaking at the seams in its attempts to bring in new constructs. I won't give an exhaustive list, but here are a few examples of the limits of C#:

Limits of iterator blocks (yield return). No such restriction in F#.
Closures capture variables, not values. In F#, closures capture values, which is in my opinion a much saner design decision.
Language-integrated queries are nice, but they don't sound as generic as they actually are. F#'s notion of quotation is more elegant, and makes it easier to see the applicability of LINQ beyond SQL.
Although it's nice that C# is "stealing" async from F#, why not introduce the more general concept of custom workflows?

Moreover, F# supports a few data-types that somehow got forgotten when class-based OOP became dominant, namely records and discriminated unions. Together with pattern-matching, they are doing their come-back in the main stream and I have no doubt they will shortly become tools top programmers are expected to master.

Now, I'm not saying you should ditch C# and replace it "en masse" by F#. C# has better tooling support, features implicit conversions and a lighter syntax for implicit interface inheritance. I don't think these features are a must-have in all situations, but they can be handy at times.

Adopting all new hyped technologies has its dangers, but if you refrain from getting on with the times because of a few dinosaurs among your developers, your business will eventually go the way of the dinosaurs.

Planing and designing WorldConquest

2011-04-30T01:39:00.000-07:00

I have been using fogbugz from FogCreek to plan and track my previous project, Asteroid Sharpshooter. So called "on-demand" installations are free for single developers. I chose fogbugz over other free alternatives because it's the only platform that I know of supporting a time planning process that has been thoroughly thought out, namely evidence-based scheduling (EBS for short).

One of the dev teams at work is also using fogbugz, but we haven't been able to validate the value of EBS, possibly because I'm the only one interested enough in both programming and planning to follow the process in a disciplined way. One of the problems of the method is that it basically requires a waterfall design process, which isn't very popular these days in professional circles.

I am curious to see whether my use of EBS for the development of WorldConquest will validate the nice ideas upon which EBS is built.

My time estimates for implementing simultaneous turns in the game have shown to be wildly off-target. I thought writing to state update function would take 3 hours. I am now reaching 16 hours, and I am still in the testing phase.

It turned out executing orders in parallel can be tricky due to conflicts. For instance, how do you handle a melee attack order and a regular move order. The first order causes the attacking unit to move towards the targeted unit and attack it when it reaches it. But what happens if the targeted unit has an order to move away? The same kind of issues arise for units embarking and disembarking, if the transporting unit moves or is destroyed.

There are quite a few ways to resolve these issues, solving is really just a matter of deciding. Still, having a clear understanding of the design before implementing it is necessary, and I find that using data-flow graphs really helps. I use yED to draw graphs. This tool can redo the layout of graphs all by itself, a feature I cannot live without. It really beats drawing on paper or drawing on screen without automatic layout.

I ended up with the design below:

Boxes are operations, octagons are data. It's not a very complex process, but trying to implement it without a proper design (as I was hoping to do at first) is not an option.
Here is the implementation of the function that puts all parts together:

let update (gs : GameState) (orders : Order[][]) =
    let damages =
        seq {
            for player in 0 .. gs.player_units.Length - 1 do
                let player_id = PlayerId player
                let attacks = extractAttackOrders gs.player_units.[player] player orders.[player]
                yield! computeDamages gs player attacks |> accumulateDamage                
        }
        |> dict

    let getDamages u =
        match damages.TryGetValue(u) with
        | false, _ -> 0.0f
        | true, x -> x

    let gs = applyDamage gs getDamages

    let dead_units = getUnitDeaths gs damages

    let isDead u =
        dead_units.Contains u

    let player_units =
        [|
            for player in 0 .. gs.player_units.Length - 1 do
                let player_id = PlayerId player
                let units = gs.player_units.[player]
                let orders = orders.[player]

                let isThisDead u = isDead(player_id, u)
                let move_orders =
                    extractMoveOrders units player orders
                    |> filterDeadMoveOrders isThisDead

                let early_disembark, late_disembark = extractDisembarkOrders units player orders
                let late_disembark = filterDeadDisembarkOrders isDead player late_disembark
                let disembark_orders = Array.concat [early_disembark ; late_disembark]

                let embark_orders =
                    extractEmbarkOrders units player orders
                    |> filterDeadEmbarkOrders isDead player
                                
                let units = applyMoves move_orders units

                yield
                    units
                    |> growUnitTree embark_orders disembark_orders
                    |> shrinkUnitTree embark_orders disembark_orders
        |]

    { gs with player_units = player_units }

I have found that comprehensions and the pipeline operator |> are very nice tools to process arrays of units.

My next project: WorldConquest

2011-04-30T01:03:00.000-07:00

I started working on a new project during the 2010 Christmas break. It's a turn-based strategy game whose working title is WorldConquest. The final title will differ, as there already are quite a few strategy games with identical or similar names.

The game is loosely based on a game for Atari ST written by Alois Felber from WisiSoft games in 1992.

The new game will feature the same units as the original game. I am planning improvements of my own, some of which are already implemented.

The original game used square tiles, I will be using hexagonal tiles. Although the new game will be turn-based it will use a simultaneous variant where players plan their moves simultaneously. When all players are ready, orders are executed simultaneously. The game will support on-line and hot-seat multiplayer. I have been thinking about and planning AI from day one. Although my experience in this domain
At this point, I have implemented map generation and some parts of AI, namely path finding. Execution of orders is what I am working on now. Design and basic implementation are done, I am testing and fixing bugs.

I am still open about the platforms I will target. The genre should fit hand-held devices such as smart phones and iPad-style tablets. PC and Mac will probably be first, as these are the only platforms that might have the CPU required to run a rough and slow AI. I would also love to publish on Xbox Live Indie Games, but the prospects are uncertain. On one hand this is a genre that isn't much represented on this market, but on the other hand I am not sure console gamers are the right customer base. Moreover, the .Net platform on Xbox features a poor garbage collector which requires code to be written in a very specific way, and I feel designing and implementing AI is challenging enough as it is. Adding constraints on allocation of temporary objects would add to the difficulty, and "optimising" code to work around the weakness of the garbage collector isn't my idea of fun.
To summarize, the platforms will may include the following, ordered by decreasing order of priority and likeliness:

PC / Windows using XNA
Mac and PC/Linux using Mono and possibly a port of XNA
Windows Phone 7 with XNA; although the garbage collector there currently suffers the same problems as on Xbox, announcements were made during MIX11 that the Mango update would introduce a new ephemeral garbage collector
Xbox 360 with XNA if the next update includes improvements to the garbage collector. No announcements have been made, but I'm hoping that Gamefest 2011 will bring positive news.
Android using Mono. I have no idea what technical limitations Mono on Android has when it comes to efficiency and garbage collection, but I'm hopeful the Mono team will be working hard to lift whatever limitations there might be. Unlike Microsoft's .Net, it's also easier to see where Mono is heading.
iPhone and iPad using Mono would be nice, but it does not seem feasible at this time. F# relies on generic virtual methods for function values, which are a corner stone of functional programming. Unfortunately, restrictions on run-time code generation on iPhone (and I guess iPad) make these hard to support. Sadly, this probably means no support for these platforms.

Although the game itself won't be free software, I will update XNAUtils with whatever reusable code I will write. This includes A* path-finding, a UI framework supporting menus and a network component.

I am planning several iterations, steadily moving toward a Civilization-style strategy game. I will release the source code of old iterations as new ones are published.

Using F# scripts for testing and performance measurement

2011-04-29T09:16:00.000-07:00

I have just heard about a new project being started by a game developer, NPerformant.

The developer writes

At various times in my “day job/career” I’ve used commercial profilers with varying results, but I don’t want or need to profile the whole application or even a whole library. I also don’t want to code two solutions into my product in order to let a normal profiler test them side by side in order to remove the loser later.

The problem about creating additional solutions also occurs in testing and when writing small utilities and editors while developing your game.

F# scripts help avoid this issue. You can add number of .fsx files to your project, and executing them using F# interactive (aka fsi) is very easy. For my current game, I have a script to render parts of my engine data using XNA and winforms, and another script to test some of the game logic. I don't know how long I will need these, but the day I lose the use for them, removing them is as easy as removing a single file from your project. Compare that to removing an entire project, which in my case would involve getting out of Visual Studio and using Windows Explorer then TortoiseHg.

Back to the topic of measuring performance, did you know about the #time command you can use in fsi:

> #time "on";;

--> Timing now on

randomTest();;
Real: 00:00:15.761, CPU: 00:00:54.725, GC gen0: 1917, gen1: 2, gen2: 0

Note that you get information about garbage collection too, which is interesting information when developing games for the Xbox 360.

Regarding testing, I just found out yet another case when pattern matching saves the day. In the code extract below, I'm using it to express the expected result of the code being tested.

match gs'.player_units with
    | [| _; [| { health = x } |] |] when x < 1.0f -> true // Injured
    | [| _; [||] |] -> true  // Killed
    | _ -> false

player_units is an array of player units, where players units are represented using arrays of units. My test has an artillery belonging to the first player fire at a helpless infantry of the second player.

The first branch of the pattern matching says: "An array composed of two elements where the first element can be anything, and the second element is a one-element array of units where x is the value of field health, and x is strictly less than 1".

I don't know how I would have written that in C# in a similarly concise fashion.

Informally, my pattern match checks that the unit of the second player was injured or killed.

"I'll Whack Your Fingers"-Oriented Programming

2011-04-18T06:01:00.000-07:00

Every now and then, a question about how to transfer data between game screens pops up on the App Hub forums. The source of the problem is that many try to solve this problem using synchronous programming. This does not work because game screens require interaction with users, which cannot be handled in a synchronous manner without freezing the game.

Although F# gives you tools to solve that problem using e.g. async workflows, most people are using C#.

How do you solve that problem in this language? Usually, people use a combination of events and public fields. This solution is fine, but I just don't like events much. They make bugs tricky to track, because I lose track of where handlers fit in the expected flow of execution of my code. Moreover, the only practical way that I know of to pass data from an event handler to the main code is through a shared variable (which I call "I'll Whack My Own Fingers"-oriented programming).

For this reason, I suggested to use Begin-End-style asynchronous programming. This requires an implementation of IAsyncResult if you want to do it in a nice .NET-ish kind of way. I am not aware of any such implementation (EDIT: Here is one, thanks mausch), so I wrote my own:

///  
  /// An implementation of IAsyncResult that wraps result data. 
  /// 
 
  /// Type of the result data. 
  class AsyncResult<T> : IAsyncResult, IDisposable { 
    public AutoResetEvent signal = new AutoResetEvent(false); 
    public bool isDone = false; 
    public T result = default(T); 
 
    public object AsyncState { 
      get { return state; } 
    } 
 
    public WaitHandle AsyncWaitHandle { 
      get { return signal; } 
    } 
 
    public bool CompletedSynchronously { 
      get { throw new NoneOfYourBusinessException(); } 
    } 
 
    public bool IsCompleted { 
      get { return isDone; } 
    } 
 
    public void Dispose() { 
      signal.Dispose(); 
    } 
  }

Did you notice how I made all fields public? I think many a modern programmer would wince when reading this. What if some careless programmer accessed isDone and modified it? Bad things can follow, and surely we should restrict access to these fields using the private keyword.

I like to call this "I'll whack your fingers if you touch this"-oriented programming. Beside "private" and "protected", which were probably invented to tempt stressed programmers to replace them with "public", enthusiasts of this approach enjoy using "sealed" to punish users who might be tempted to reuse your code.

There are better ways to prevent accidental tempering with an object's internal state: access objects via interfaces.

For instance, here is the code for the Begin-End pair of methods that use my AsyncResult:

///  
        /// Open a MessageBoxScreen asynchronously. 
        /// 
 
        /// The screen manager to which the screen is to be added. 
        /// The index of the player who has control, or null. 
        /// The text of the message to show. 
        /// An object which can be used to wait for the request to complete and retrieve the result. 
        public static IAsyncResult BeginShowMessage(ScreenManager sm, PlayerIndex? player, string msg) { 
          var result = new AsyncResult(); 
 
          var screen = new MessageBoxScreen(msg); 
          screen.Accepted += (src, args) => { 
            result.isDone = true; 
            result.result = true; // User accepted the message box. 
            result.signal.Set(); 
          }; 
          screen.Cancelled += (src, args) => { 
            result.isDone = true; 
            result.result = false; // User cancelled the message box. 
            result.signal.Set(); 
          }; 
 
          sm.AddScreen(screen, player); 
 
          return result; 
        } 
 
        ///  
        /// Wait for the user to complete interaction with a MessageBoxScreen opened with BeginShowMessage. 
        /// 
 
        /// The object returned by BeginShowMessage. 
        /// Whether the user accepted or cancelled the message screen. 
        public static bool EndShowMessage(IAsyncResult r) { 
          var result = r as AsyncResult; 
          if (result == null) 
            throw new ArgumentException("Wrong type or null", "r"); 
 
          result.signal.WaitOne(); 
          result.Dispose(); 
          return result.result; 
        }

Note how BeginShowMessage and EndShowMessage return and take respectively an IAsyncResult. Unless users of these methods really want to take risks getting intimate with AsyncResult, there is no risk of tampering. And if they really want to work directly with the inner parts of AsyncResult, why prevent them to do so?

I wonder, what's the point with "private" and "protected" anyway?

UPDATE:

Thinking a bit more on the subject, I think another overused feature resides in non-virtual public methods (and fields). Anything public in the API of a class should belong to an interface, with the exception of constructors and construction helpers (which maybe should be internal to assemblies).

I would however not advise to use abstract data types in all situations. Navigating in the call tree is a good way to learn a new code base, and typically abstract methods defeat this. One could say abstraction through interfaces is a form of obfuscation, as it effectively hides implementations.

Asteroid Sharp Shooter: Post-mortem

2011-03-04T07:50:00.000-08:00

Introduction

Asteroid Sharpshooter is a game published on the Xbox LIVE Marketplace, under the independent games section.

It is written in F# and C#, using XNA Game Studio 3.1. The game falls in the category of 3d space shooters. Inspired by a classic, Asteroids, the game puts the player in space, in a field filled with rocks. Some of these can be destroyed by shooting at them. The goal of the game is to shoot and destroy a number of rocks. To make things challenging, the controls of the ship are consistent with what you would expect from a ship drifting in space. There is no friction, and the ship does not necessarily point where it's headed. Controlling the ship to collect power-ups and approach asteroids to shoot requires skill. The higher difficulty levels feature enemies in the form of drones that track the player's ship and detonate themselves when they come close enough.

In this article, I present my thoughts about the development process of the game and the reception of the game by players.

Development

The game was written using Visual Studio in C# and in F#. C# is used for the higher levels of the software, which consist of menus, parts of the rendering, loading assets, loading and saving user progress.
Menus use the game state management sample from the App Hub.

Using F#

F# is a good programming language in general, and contributed positively to the development. Features such as discriminated unions and pattern matching are lacking in C#.

Although the game uses multiple threads, it does not use async workflows (these are primarily intended to ease the development of asynchronous code, but they also have interesting properties for parallel programming, as shown in my earlier blog entries).

Some of F# features were at the time not supported on Xbox and resulted in run-time errors: sprintf and async workflows. I haven't had the occasion to try async workflows with the current version of F#, but sprintf now works!

Building the game was tricky before I managed to hack project files.

I initially used the free versions of Visual Studio: the Express edition for XNA Game Studio and C#, Visual Studio Shell for F#. This worked OK, even for debugging, but wasn't as practical of using Visual Studio Pro, which I ended up using at the end. You can use the free editions to try and see if F# works for you, but for regular development, you will probably want to use the Pro edition or higher.

I was a bit worried that using F# on the Xbox might not fully work, and might even be impossible as new versions of XNA or F# are released. Although there have been problems, all could be resolved, and the mix got better or more stable with every new release. Although F# is still not officially supported on Xbox, the fact that Microsoft Research has developed an XBLA game that uses F# sounds positive.

F# uses reference types for most of its data types: lists, tuples, records, classes, discriminated unions, function values, mutable cells (ref). This can cause problems because of the limitations of the current garbage collector on Xbox. I decided to design my code so that garbage collections would have a low latency, and not care too much about how often they would occur. This worked well enough. The game triggers a garbage collection every 6 frames, which each last for 3.5ms. The remaining time was enough to update the physics and render all objects, but a more complex game with more models and more complex class hierarchies could have difficulties.

F# does not allow circular dependencies between types unless they are declared in the same file and marked as mutually dependent. I was aware of this restriction, and it did not cause me any trouble. I started the project with all C# code in one project, and all F# code in another. Toward the end, I started moving reusable code into separate libraries. For my F# code, this was little more work than moving files to a new project and changing namespaces. The task was notably more difficult in C#, as the language supports circular dependencies within assembly bounds. Breaking apart an assembly will require the introduction of interfaces at the bounds. Although F# and C# do not differ on that point, the fact that F# forces you to work that way has benefits the day you want to split your code, in addition to all other benefits that non-circular designs have (better tool support, easier to understand...).

I don't know of any way to declare pass-by-reference parameters in F#, the way you can in C# using the "ref" keyword. In the XNA framework, some methods use passing by reference to save time. Although it is possible to call such functions from F# code, I don't know of any way to declare new functions.
There is however an F# way of avoiding copying large structs when calling functions: use inlining. Last time I checked, it was not fully reliable though, as the F# compiler tends to introduce lots of unnecessary variables in inlined code. Whether the .net CLR notices that and removes these variables isn't clear to me.

Project planning and tracking

I have used a free account on fogbugz to organize my work and keep track of bugs. Although it may seem to be overkill, it allowed me to look at what went wrong when writing this article, as I had a record of most of the bugs. It also simplifies working on a project part-time. During my day job I can focus on my job and forget about the project. When the week-end comes, I can pick up the project where I left it, and start new tasks which were planned but not started.

Obstacles encountered

Although the game state management sample was very helpful to get the menu system up and running in no time, it's not obvious at first how to integrate user interaction forced by the StorageDevice API. One needs to keep track whether a device is selected, whether the user is currently selecting one... The first solution that comes to mind, using Boolean variables isn't maintainable when the number of variables grows. For instance, the device selection screen had to keep track of whether the user was signed in, currently signing in, if a title-specific storage device was chosen, being chosen, whether a user-specific storage device was chosen, being chosen. Mix that with event handlers that may need to display alert boxes, and it becomes tricky. I used handlers to deal with storage disconnection and I/O operation notification.
Even after writing my own version of EasyStorage in F#, cleaning up code, the Update() method of my game object still looked too complicated for its own good:

protected override void Update(GameTime gameTime)
        {
            base.Update(gameTime);

            if (titleStorageLost == GuideStates.Requested)
            {
                if (!Guide.IsVisible) try
                {
                    Guide.BeginShowMessageBox("Storage device disconnected",
                        "The storage device used for scores was disconnected. " +
                        "Scores will not be saved unless a new device is selected. " +
                        "Would you like to select a device now?",
                        new string[] { "Yes", "No" }, 0, MessageBoxIcon.Alert,
                        (result) =>
                        {
                            var choice = Guide.EndShowMessageBox(result);
                            if (choice.HasValue && choice.Value == 0)
                                requestTitleStorage = true;
                            titleStorageLost = GuideStates.None;
                        },
                        null);
                    titleStorageLost = GuideStates.Pending;
                }
                catch (GuideAlreadyVisibleException) { }
            }

            if (titleStorageLost == GuideStates.None && requestTitleStorage)
            {
                storage.RequestTitleStorage();
                requestTitleStorage = false;
            }

            if (titleStorageLost == GuideStates.None && !requestTitleStorage && userStorageLost == GuideStates.Requested)
            {
                if (!Guide.IsVisible) try
                {
                    Guide.BeginShowMessageBox("Storage device disconnected",
                        "The storage device used for player progress was disconnected. " +
                        "Progress will not be saved unless a new device is selected. " +
                        "Would you like to select a device now?",
                        new string[] { "Yes", "No" }, 0, MessageBoxIcon.Alert,
                        (result) =>
                        {
                            var choice = Guide.EndShowMessageBox(result);
                            if (choice.HasValue && choice.Value == 0)
                                requestUserStorage = true;
                            userStorageLost = GuideStates.None;
                        },
                        null);
                    userStorageLost = GuideStates.Pending;
                }
                catch (GuideAlreadyVisibleException) { }
            }

            if (titleStorageLost == GuideStates.None && userStorageLost == GuideStates.None && !requestTitleStorage && requestUserStorage)
            {
                var screens = screenManager.GetScreens();
                if (screens.Length > 0)
                {
                    var topScreen = screens[screens.Length - 1];
                    if (topScreen.ControllingPlayer.HasValue)
                        storage.RequestUserStorage(topScreen.ControllingPlayer.Value);
                }
                requestUserStorage = false;
            }

        }

Since then, I have developed a better way of solving that kind of problem. All this code now becomes:

task {
  do! storage.CheckPlayerStorage
}

Shorter, isn't it? The point is that F# has features that make it possible to compose code using a notation similar to traditional function calls, yet the execution can differ from a traditional call. The idea is so neat that the normally conservative C# design team decided to add a variant of it to the next version of the language.

Back to the post-mortem, another related problem is to deal with screen transitions. There are several approaches: Hard-coding, events and delegates.

Using hard-coding, screen A creates and displays screen B when a certain action is performed.
This requires the class for screen A to know about the class for screen B, and must have the data needed during instantiation of B at hand. I found this approach was not very flexible, and caused me some trouble when I added support for local multiplayer (which wasn't planned from start).

The two other approaches, events and delegates make it easier to forward the data needed to instantiate new screens, as it's typically available in the class which registers the event handler, or creates the delegates which captures the data in question.

All these approaches share the same problem: the transition code is spread out all over the place, making it hard to debug, modify and extend. Of the 50 bugs I registered in fogbugz, 13 involved screen transitions at some level. For a game programmer who is interested in getting the gameplay right, getting 26% extra bugs because of menus is a very frustrating, even if most of those bugs are easy to fix.

Art assets

Asteroid models, ship models and textures were provided by Benoit Roche. The title and menu music is from Partners in Rhyme, sounds from Soundsnap. The game backgrounds and the box art were done by myself using The Gimp and a tutorial on starfields. When doing sky boxes, it's a good idea to test them on a PC screen. I failed to notice on my TV that the sides of the box had light levels that did not match. Happily, a tester on the App Hub noticed that and reported the problem.

The community on App Hub...

... was very helpful. Thanks to all of you fellow developers for your feedback and suggestions!

Due to my earlier involvement in free software and Linux, I thought that sending your game to playtest early and often was a good thing. While it was, don't expect feedback for every release. Other developers will not test your game time and again every month. Getting comments from other is a motivation boost, but you should not rely on that. I think it's a good idea to send to playtest as soon as your gameplay is done, to see how well it's received. After that, sending updates every time won't get you much feedback. It may actually be better to wait until a new milestone is reached, e.g. menus are done, art is done, game is ready for evil-checklist testing.

Reception of the game

The mix between a classic 2d game and a 3d space shooter was not well received by the market. After five weeks, the game sold 143 copies with a conversion rate of 8.06%
Few reviews were written, most of them judging the game as dull and hard to control. This is what xboxindiegames had to say about the game:

You can't steer, you can't see, you can't aim and you can't shoot. You can avoid this game, though...

The Yellow Pages from Pencil Shavings sounded more positive:

Looks fantastic and plays well, just a little redundant [...]. Nice game, enjoyable, but lacking variety.

I also registered the game for Dream-Build-Play 2010, but the game did not make it to the best 20.
The game is rated 3 stars of 5 in the American Xbox LIVE Marketplace, which I think is characteristic of well-done but uninspiring games.

Conclusions

Technically, the game was a success and showed the feasibility of using F#. It took me way too much time (about two years), though. I hope I will be able to increase the production rate for my upcoming games.

Replacing LIVE functionality in XNA 4.0

2011-02-27T03:34:00.000-08:00

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.

Why we need better garbage collection on the Xbox

2011-02-26T04:20:00.000-08:00

George Clingerman started a discussion on the App Hub where he asks developers what they would like George and other MVPs to discuss with the XNA dev team.

I took the chance to request that improvements be made to the garbage collector (GC for short) on Xbox. What's wrong with the current one, you may ask? Unlike GC on the PC platform, the Xbox GC is non-generational. A generational (also called ephemeral) GC distinguishes between newly allocated objects and older objects. Reclaiming memory early from "young" objects makes it possible to diminish the frequency of reclaiming memory from older objects, because many young objects are short-lived. This is important as reclaiming memory from older objects is an expensive operation.

To work around this limitation, Shawn Hargreaves has written articles on how to minimize or avoid altogether garbage collection during gameplay phases which must run at a constant 60 fps. To summarize, there are two ways: Make sure each collection is fast (the so-called low latency path) or avoid allocating memory to avoid triggering garbage collections.

The good thing with the first approach is that you don't need to worry much about allocations that happen "behind your back", i.e. allocations that are introduced by the compiler or the core library. The bad thing is that you must avoid complex object graphs. Note that this includes even objects allocated outside of the performance-critical parts of your code, such as menu code, art assets...

The second approach is by far the most popular. It works well with object-oriented designs which rely on mutability. This approach also has problems. Developers must avoid all kinds of allocation at all time during gameplay, which implies refraining from using many language constructs. This includes events, delegates and lexical closures in C#, tuples and closures in F#.

Having two options to avoid performance drops due to GC sounds nice until you realize you can't combine the two. You have to choose one or the other, but you can't mix the two. That's sad, because in practice an attractive design for games is to use OOP and mutability for menus and low-level array-based computations for gameplay.

And this is why we need better garbage-collection on the Xbox.

Death by exception

2011-02-12T11:51:00.001-08:00

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

2011-02-12T11:51:00.000-08:00

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

Notes on safe use of StorageDevice in XNA

2011-02-06T03:26:00.000-08:00

I recently found a bug in StorageTasks.fs, an exception that I did not expect can be thrown in some situations. I am therefore going over the code and checking if I'm handling all exceptions correctly.

The bug I just fixed was an uncaught InvalidOperationException when attempting to open a StorageContainer after pulling the memory unit (which was picked as the storage device). The method that threw that exception was StorageDevice.EndOpenContainer. Sadly, the msdn documentation does not mention that.

I thought I would use EasyStorage as a reference. Unfortunately, even EasyStorage isn't 100% correct. For instance, see SaveDevice.OpenContainer: It does not catch InvalidOperationException. Although unlikely, this can happen if the user disconnects the storage device after BeginOpenContainer and before EndOpenContainer.

Anyway, I'll just go on and rely on testing to get it right... In the mean time, here are my findings regarding exceptions thrown by the StorageDevice API in XNA.

StorageDevice.BeginShowSelector

GuideAlreadyVisibleException

StorageDevice.EndShowSelector

None known

StorageDevice.BeginOpenContainer

InvalidOperationException (from msdn)
ArgumentNullException (from msdn)
StorageDeviceNotConnectedException

StorageDevice.EndOpenContainer

InvalidOperationException
StorageDeviceNotConnectedException

StorageContainer.OpenFile

StorageDeviceNotConnectedException
FileNotFoundException

StorageContainer.CreateFile

StorageDeviceNotConnectedException
Possibly other exceptions, e.g. if no space is left on the device?

I have listed StorageDeviceNotConnectedException under most methods. Although it's never mentioned explicitly on msdn in the method documentation, it seems reasonable to expect it in any situation where the device might be accessed.

There are other failure scenarios associated to Stream and serialization which I'm not listing here. In particular, XML de-serialization of F# types (discriminated unions, records, tuples, lists...) will fail at run-time due to these types being immutable and lacking a default constructor.

Post-asteroid trauma

2011-02-05T08:04:00.000-08:00

December and January have been hectic months for me.

December saw the publishing of a number of templates facilitating the use of F# with XNA:

For the Xbox 360: library template, which has been downloaded 360 times. Does that mean there are 360 F# games coming to the Xbox? If you are working on a game, don't hesitate to let me know!
For the Windows Phone 7 platform: library and full application templates. Although I am not personally involved in WP7 development, I would love to hear about ongoing projects too!

I am not done yet with project templates. I am planning to make a full game template for the Xbox 360, and update all existing templates with the script for interactive development using fsi.

In January, the discovery of custom workflows and how they can dramatically increase the readability of one's code fascinated me. I think that's a feature that even functional programming sceptics should love.

My game, Asteroid Sharpshooter passed peer review and became available on the Xbox LIVE Marketplace. I doubt it will make me rich, but for a first try, it's not too bad.

What are February and the following months going to be like? First, I want to understand whether custom workflows are safe to use in the absence of tail call elimination. I'm still a bit confused... If they are safe, as I suspect they are, I will go ahead and make an XNA game starter kit, similar to the XNA Game State Management sample. It will include file IO and menus based on the Eventually workflow and cooperative multi-tasking.

At the end of February, Dream-Build-Play 2011 will open for registration, which will be the starting point for my next game.

I will also try to be more active in the XNA community and let people know C# is not the only language available in their toolbox. To this effect, I have registered on twitter. I'm deneuxj there. I'll be posting a few pre-paid codes for Asteroid Sharpshooter there, so stay tuned!

Is it possible to use F# to write and publish a game on the Xbox LIVE Marketplace?

2011-02-03T11:45:00.000-08:00

Yes, it is.

Safe IO on the Xbox 360 in F#

2011-01-30T13:23:00.000-08:00

... 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:

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.
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.
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).
The user may at any time remove a storage device, which results in exceptions being thrown while accessing the device.
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.

Cooperative multitasking using the Eventually workflow

2011-01-21T01:57:00.000-08:00

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.

The Eventually workflow

2011-01-18T13:34:00.000-08:00

The F# specification gives an example of custom workflow in its section on computation expressions. I have extended it as shown below:

type Eventually<'R> =
    | Completed of 'R
    | Blocked of float32 * (unit -> Eventually<'R>)
    | BlockedNextFrame of (unit -> Eventually<'R>)
    | Running of (unit -> Eventually<'R>)
    | Yield of (unit -> Eventually<'R>)

An Eventually computation can be in one of the following states:

Completed, in which case the state includes the result of the computation.
Blocked, when the computation is paused, and the state contains the amount of time remaining before it resumes.
BlockedNextFrame, when the computation is paused for a short while, until the start of next frame. The meaning of "next frame" is up to the scheduler, which is described in an upcoming article
Running, which indicates the computation is ready to proceed.
Yield, when the computation is willing to pass control to another computation which is in state Running, if any. Otherwise, the computation is ready to proceed.

All states but the first one, Completed contain a function value which when executed produces a new state. It represents the work that the computation can perform "in one block" before returning control to the scheduler. When that happens, the scheduler updates the state of the computation.

Although it is possible to build computations "manually" using this discriminated union, F# makes it possible to do so conveniently using a subset of F# extended with a few keywords, namely yield, yield!, return, return!, let! and do!. The meaning of these keywords is up to the designer of the custom workflow, but they have an expected behaviour which should be respected.

yield and yield! are used to produce values in sequences. The second variant allows to insert sequences from other sequence expressions. Here I use sequence expression as a synonym for "a computation expression used to produce sequences". Below is an interesting example (from the F# Programming wikibook).

let allEvens = 
  let rec loop x = seq { yield x; yield! loop (x + 2) }
  loop 0;;

loop is a function which takes an integer x and returns a sequence expression which when evaluated produces the integer, followed by the result of a recursive call to loop using x+2. In clear, this will produce x, x+2, x+2+2, x+2+2+2..., one value at a time. Note the difference between yield and yield!: the first produces a single value, the second produces the values of another sequence expression.

let! allows to "nest" computation expressions. In other words, a computation expression can "call" another computation expression. I'm being pretty vague here, so let's look at an example using asynchronous computations (also from the wikibook).

let extractLinksAsync html =
    async {
        return System.Text.RegularExpressions.Regex.Matches(html, @"http://\S+")
    }
 
let downloadAndExtractLinks url =
    async {
        let webClient = new System.Net.WebClient()
        let html = webClient.DownloadString(url : string)
        let! links = extractLinksAsync html
        return url, links.Count
    }

return and return! are used for the final results of a computation expression. The example above uses return. My guess is return! should behave as

let! x = ...
return x

I am not quite sure if return is meant to have imperative semantics, i.e. discarding the remainder of a computation when encountered. My attempts to use such C-like semantics have not succeeded yet.

Going back to my library, XNAUtils, I have written a computation builder which is used to turn computation expressions (code between curly brackets) into state machines that can be executed in a controlled manner. The builder takes the form of a class with methods are called at selected places in a computation expression. A builder allows to override the meaning of certain keywords and specify the effect of the special keywords I listed above. The code is in CoopMultiTasking.fs

let rec bind k e =
    match e with
    | Completed r ->
        Running(fun () -> k r)
    | Running f ->
        Running(fun () -> f() |> bind k)
    | Blocked(dt, f) ->
        Blocked(dt, fun () -> f() |> bind k)
    | BlockedNextFrame f ->
        BlockedNextFrame(fun () -> f() |> bind k)
    | Yield f ->
        Yield(fun () -> f() |> bind k)

...

type TaskBuilder() =
    member x.Bind(e, f) = bind f e
    member x.Return(r) = result r
    member x.Combine(e1, e2) = combine e1 e2
    member x.Delay(f) = delay f
    member x.Zero() = result ()
    member x.TryWith(e, handler) = tryWith e handler
    member x.TryFinally(e, compensation) = tryFinally e compensation
    member x.While(cond, body) = whileLoop cond body
    member x.For(xs, body) = forLoop xs body
    member x.Using(e, f) = using e f

let task = TaskBuilder()

The module-level variable task can be used to create instances of Eventually. I have provided a few helpful tasks that can be used to wait a fixed amount of time, wait until next frame, give control to another task:

// Wait a fixed amount of time.
let wait dt =
    Blocked(dt, fun () -> Completed())

// Wait until next frame, i.e. next call to Scheduler.RunFor
let nextFrame () =
    BlockedNextFrame(fun() -> Completed())

// Stop executing, let some other task execute, if any is ready. Otherwise, we get control back.
let nextTask () =
    Yield(fun() -> Completed())

// Wait until a specified condition is true.
// nextTask is always called, then the condition is checked.
// If it's false, we wait until next frame, check the condition,
// call nextTask if it's not true, and so on...
let waitUntil f = task {
    let stop = ref false
    while not !stop do
        do! nextTask()
        if f() then
            stop := true
        else
            do! nextFrame()
            stop := f()
}

waitUntil uses a while loop, it could have used recursion too. I initially refrained from using recursion in all code meant to be executed on the Xbox 360, because tail calls are not available on this platform. On second thoughts, I don't think that's a problem, as the kind of recursion that would appear inside of tasks is of the loose kind. Recursive calls a interrupted by calls to nextTask and nextFrame, which should prevent the stack from overflowing.

Although I have not had any use for synchronization between tasks yet, I have provided two functions to that effect:

// Lock, can be used for mutual exclusion.
// Locks should not be shared across instances of Scheduler.
type Lock() =
    let mutable locked = false;

    member this.Grab() =
        task {
            do! waitUntil (fun() -> not locked)
            locked <- true
        }

    member this.Release() =
        task {
            locked <- false
            do! nextTask()
            ()
        }

// A blocking channel which can be used for cross-task communication.
// Note that sending blocks until the message is received.
type BlockingChannel<'M>() =
    let mutable content = None
    let mutable flag_send = false
    let mutable flag_receive = false

    member this.Send(m : 'M) =
        task {
            do! waitUntil (fun () -> not flag_send)
            content <- Some m
            flag_send <- true
            do! waitUntil (fun () -> flag_receive)
            flag_send <- false
            content <- None
        }

    member this.Receive() =
        task {
            do! waitUntil (fun () -> flag_send)
            let ret = content.Value
            flag_receive <- true
            do! waitUntil (fun () -> not flag_send)
            flag_receive <- false
            return ret
        }

Cooperative multi-tasking makes synchronization between tasks easy, as there is no concurrency involved.

That's all for this time, in the next article I will describe how multiple tasks are executed by a single scheduler.

How to spread a computation over multiple update cycles

2011-01-13T13:04:00.000-08:00

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:

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.
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...
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.

Untying the game update loop

2011-01-09T12:23:00.000-08:00

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()
  press_start_screen.Show()
  let player = press_start_screen.GetPlayer()
  press_start_screen.Hide()

  let menu_screen = new MenuScreen()
  menu_screen.Show()
  let entry = menu_screen.GetEntry()
  menu_screen.Remove();
  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 =
            sys.Spawn(anim.Task)

        // 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
        blinker.Kill()
    
        // 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.
        return
            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.

Project templates for F# games on Windows Phone 7 using XNA

2010-12-28T05:01:00.000-08:00

The recent presentation of the Windows Phone 7 platform and its marketplace by Microsoft has attracted a lot of attention. The success of the iPhone and its App store has opened new markets to independent developers.

Both .NET and F# are considered very attractive development platforms, and some have shown interest for a set of project templates allowing the use of F# for developing applications for Windows Phone 7.

Taking advantage of the experience I gained building a project template for F# + XNA for Xbox 360, I have created two new templates for F# + XNA for WP7.

They are now available on the Visual Studio Gallery:

F# + C# Game For Windows Phone (XNA)

F# Library for Windows Phone (XNA)

I must also mention the earlier templates by Dan Mohl, which target WP7 through Silverlight:

F# and C# Win Phone App (Silverlight)

F# and C# Win Phone List App (Silverlight)

F# and C# Win Phone Panorama

I am now considering to work on the following templates:
- PC hosted game
- PC XNA+winforms app
- PC lib (with the script I mentioned in Interactive Game Development with XNA and FSI)
- Xbox360 hosted game

Please let me know which template you think would be most valuable.

Interactive game development with FSI and XNA

2010-12-26T11:01:00.000-08:00

I recently looked at a presentation by Don Syme about the future of F# and type providers. The entire demo was conducted using F# interactive and a Windows Forms.

The same can be done for XNA. First, you need to get the code sample that shows how to embed XNA into a Windows Forms control. It's available in the education catalog on the App hub.

Then, you need to wrap the control into a form, and add some functionality to easily couple plug in an F# function.

#r @"D:\Documents\WinForms\WinFormsGraphicsDevice\bin\Release\WinFormsGraphicsDevice.exe"

#I @"C:\Program Files\Microsoft XNA\XNA Game Studio\v4.0\References\Windows\x86"
#r "Microsoft.Xna.Framework.Graphics.dll"
#r "Microsoft.Xna.Framework.dll"
#r "Microsoft.Xna.Framework.Game.dll"

open System.Windows.Forms
open Microsoft.Xna.Framework

type XnaControl() =
    inherit WinFormsGraphicsDevice.GraphicsDeviceControl()

    let mutable drawer = fun (dt : GameTime) -> ()
    let watch = new System.Diagnostics.Stopwatch()
    let mutable last_time = watch.Elapsed

    member this.Drawer
        with get ()  = drawer
        and  set (v) = drawer <- v
        
    override this.Initialize() =
        watch.Start()
        last_time <- watch.Elapsed

    override this.Draw() =
        let diff = watch.Elapsed - last_time
        last_time <- watch.Elapsed
        GameTime(diff, watch.Elapsed)
        |> drawer

type XnaForm() =
    inherit Form()

    let ctrl = new XnaControl()
    let animationHandler = new System.EventHandler(fun _ _ -> ctrl.Invalidate())
    do
        ctrl.Dock <- DockStyle.Fill
        base.Controls.Add(ctrl)

    member this.XnaControl = ctrl

    member this.EnableAnimation() =
        Application.Idle.AddHandler(animationHandler)

    member this.DisableAnimation() =
        Application.Idle.RemoveHandler(animationHandler)

This is how I use it:

let form = new XnaForm()
form.Show()
let content = new Content.ContentManager(form.XnaControl.Services)
content.RootDirectory <- @"D:\Documents\WorldConquest\ContentLibrary\bin\x86\Debug\Content"

let units : Graphics.Texture2D = content.Load("units")

let batch = new Graphics.SpriteBatch(form.XnaControl.GraphicsDevice)

let draw _ =
    try
        batch.Begin()
        batch.Draw(units, Vector2.Zero, Color.White)
    finally
        batch.End()


form.XnaControl.Drawer <- draw

You'll probably want to load some content (fonts, textures...) otherwise you won't be able to draw much. I don't have any nice way to build content interactively yet. For now, this is what I have to do:
1. Add a C# XNA game library
2. Add an XNA content project
3. Reference the content project from the library created in step 1, and configure the library to use the "Reach" API. This is done from the project's properties.

How to make a visual studio project template

2010-12-24T08:15:00.000-08:00

Here is the simple 14-step procedure to build a template for F# projects targeting exotic platforms.

Mixing F# and XNA's dna:

0. Get a build of the F# core library for the exotic platform.

1. Create a new C# XNA library project

2. Create a new F# library project

3. Create a directory "Dependencies" in the F# library.
Put the custom-built F# core dll files there.
Add these files to the project.

4. Merge the XNA "dna" from the C# XNA library project file (with extension .csproj) into the F# library project (with extension .fsproj)
This includes:
a) Fixing platforms (remove "Any CPU", add the XNA platform)
b) Fixing configurations (the common one, as well as the release and debug ones too)
c) Adding all references to XNA dlls (simple copy-paste from the XNA csproj file)
d) Importing the XNA targets file (after the F# targets file)
c) and d) are easy, a) and b) is mostly text merging, using the csproj file whenever there are conflicts.

5. Fix references in the .fsproj file.
a) Replace or add the reference to FSharp.Core.dll, using a hint path pointing at "Dependencies".
b) Check that any reference to "mscorlib.dll" has no HintPath element.

6. Save your work, commit it if you are using revision control (advised)

7. Try to build the project. If you are lucky it will be successful. Look at the command line in the output window to check that the right version of FSharp.Core.dll was used (the one in Dependencies).

8. Clean the project

9. Choose "Export template" in the file menu. Don't install the template in Visual Studio.
If you mistakenly installed it, you can remove it by deleting the zip file from "My Documents\Visual Studio 2010\Templates\Projects".

10. You will get a zip file under "My Exported Templates"

11. Open the zip file, copy __TemplateIcon and MyTemplate files into the F# library project.

12. Edit MyTemplate to add the following lines under .

     <Folder Name="Dependencies" TargetFolderName="Dependencies">
        <ProjectItem ReplaceParameters="false" TargetFileName="FSharp.Core.dll">FSharp.Core.dll</ProjectItem>
        <ProjectItem ReplaceParameters="false" TargetFileName="FSharp.Core.xml">FSharp.Core.xml</ProjectItem>
        <ProjectItem ReplaceParameters="false" TargetFileName="FSharp.Core.optdata">FSharp.Core.optdata</ProjectItem>
        <ProjectItem ReplaceParameters="false" TargetFileName="FSharp.Core.sigdata">FSharp.Core.sigdata</ProjectItem>
     </Folder>

13. Remove the bin/ and obj/ directories, if any.

14. Zip the content of the F# library project directory (not the directory itself!). You now have a project template file.

On the performance of F# on the Xbox 360

2010-12-11T08:53:00.000-08:00

I recently mentioned on the App Hub (the gathering place for indies targeting Windows Phone 7 and the Xbox 360) that I was using F#. Someone asked what programming in F# was like.

Obviously, I enjoy it very much, and I sincerely hope that other XNA game programmers will decide to give F# a place in their development tools.

I bet there are programmers out there who wonder if all these nice features that F# supports don't come at too high a cost when it comes to performance. I managed to write a fairly computationally-intensive game for the Xbox 360 in F#, so obviously writing a game in F# is feasible. However, the question remains whether I could have done a significantly better job using C#?

In an attempt to answer this question, I am comparing in this article the performance of four implementations of an octree: Two in F# and two in C#.

Problem area

An octree is a data structure often used in 3d games for collision detection. There are different ways to design and implement an octree and its associated algorithms, depending on one's requirements. In my case, the requirements are, in increasing order of importance:

1. Fast querying. Building the octree should be reasonably fast, but need not be as fast as querying. Typically, octrees are built once (possibly at compile time) and queried every frame.
2. Generic. The implementation should be suitable for use with spheres, boxes, triangles, rays...
3. Maintainable source code. Note that this requirement has higher importance than efficiency. As an independent developer, I am not trying to compete with the big guns in number of polygons and objects. Moreover, my time available for programming games is very limited, and I don't want to get stuck with an implementation that may be fast now, but hard to maintain.

Data structure

With this in mind, I came up with the following design for the data structure in F#:

type Node<'TS> =
    { bbox : BoundingBox
      data : Data<'TS> }
and Data<'TS> =
    | Leaf of int * 'TS          // sequence length, sequence of items
    | Inner of Node<'TS> array   // Array of 8 items exactly

Six lines, all in all. Each node has a bounding box covering all volumes contained in this node and its descendants. Each node is either an internal node, in which case it has references to its 8 children, or a leaf, and it has references to the shapes it contains. The type TS denotes a sequence of shapes.

Construction

The function below is used to insert an item into a node of a tree (or into one of its descendants). In the case where the item to insert overlaps the boundaries of the bounding boxes, it will be inserted into multiple leaves. Some implementations avoid this by splitting shapes, but that's too advanced for my needs.

let rec insert max_count max_depth intersect node item depth =
    assert (
       intersect node.bbox item
    )
    
    match node.data with
    | Leaf(count, items) when (depth >= max_depth || count < max_count) ->
        { node with data = Leaf(count + 1, item :: items) }
    | Leaf(count, items) ->
        let node' = split intersect node
        insert max_count max_depth intersect node' item (depth + 1)
    | Inner(children) ->
        { node with
            data = Inner(
                    children
                    |> Array.map (fun child_node ->
                            if intersect child_node.bbox item
                            then insert max_count max_depth intersect child_node item (depth + 1)
                            else child_node
                        )
                    )
        }

The function above has quite a few arguments, but the first three are typically constant. One can therefore define an additional function using currying:

let myInsert = insert 20 5 myIntersectionPredicate

Using myInsert, the tired programmer is saved the effort of repeatedly passing the first three parameters.

Note that the function is limited to nodes which are of the type Node<'T list>. The Node type is immutable, and in this setting, F# lists are fairly efficient. An alternative would have been to use mutable nodes and resizeable arrays, an approach I picked for the implementations in C#.

There is another function named "split" which I am not showing in this article. Given a leaf node, it produces an inner node and 8 children with equivalent content.

My early measurements showed that lists might not be the most appropriate data structure to use once the octree is built. Arrays can be iterated over more efficiently. The function below translates an octree "under construction" into a "query-able fast octree".

let rec freeze (node : Node<'T list>) : Node<'T[]> =
    match node.data with
    | Leaf (count, ts) -> { bbox = node.bbox ; data = Leaf (count, Array.ofList ts) }
    | Inner (children) -> { bbox = node.bbox ; data = Inner (children |> Array.map freeze) }

Querying

Checking for overlap of items contained in the octree with another item is done using a recursive function, which goes into the relevant leaves, thus avoiding unnecessary item-to-item intersection checks.

let checkIntersection intersectBbox intersectSomeItem node =
    let rec work node =
        intersectBbox node.bbox
        &&
        match node.data with
        | Leaf(_, items) ->
            intersectSomeItem items
        | Inner(children) ->
            children |> Array.exists work
        
    work node

Something that might be puzzling about this function is that it seems it lacks an "item" parameter. Actually, it's hidden in the "intersectBbox" and "intersectSomeItem" predicates. Those are typically constructed using closures that capture the item of interest, as shown below:

let intersectBBox2 (spheres : BoundingSphere[]) (i : int) =
    let sph = spheres.[i]

    fun (box : BoundingBox) ->
        box.Intersects(sph)

let intersectBSphere (spheres1 : BoundingSphere[]) (spheres2 : BoundingSphere[]) (i1 : int) =
    let sph = spheres1.[i1]

    fun i2s ->
        i2s
        |> Array.exists (fun i2 -> sph.Intersects(spheres2.[i2]))

let checkIntersection_BoundingSpheres spheres_octree spheres2 node item =
    checkIntersection (intersectBBox2 spheres2 item) (intersectBSphere spheres2 spheres_octree item) node

Alternative implementations

The code showed above originates from an implementation which I labelled "Virtual". It makes heavy use of function values. Calls to the functions behind these function values are called "virtual calls", and are often slower than direct calls.

F# has a feature which other .NET languages lack, namely inlining. Inlining can be used to avoid virtual calls, which in theory allows to achieve the speed of direct calls without losing genericity. Moreover, it can enable compilation-time optimizations that are not available to the JIT at run-time. The down-side is that they increase the size of the generated code. Inlining can also lead to slower code when used inappropriately. I wrote a variant which uses inlining labelled "Inline". It uses the following replacement for Array.exists:

let inline exists (pred : 'T -> bool) (xs : 'T[]) : bool =
    let mutable i = 0
    while i < xs.Length && not (pred xs.[i]) do
        i <- i + 1
    i < xs.Length

The implementation of "insert" in this variant is also inlined, but "checkIntersection" isn't. Time measurements show that inlining clearly is beneficial in this case.

How do these implementations in F# fare compared to implementations in C#? I wrote two variants in C#. The first one is inspired from the F# code and maintains its level of genericity. It uses delegates where F# uses function values, and LINQ where F# uses functions from the Array and List modules. The second C# variant ("Specific") is based on the first one with genericity removed, thus allowing the removal of delegates (direct method calls are used instead). Hand-made loops (using foreach and for) are used instead of LINQ.

Benchmark

Three different octrees are used with different levels of space density. The number of shapes they contain are identical, but the size of each shapes is different. The larger the shapes, the denser the space. Three sets of external shapes are created, also with varying levels of density. The timings measure on the one hand the creation of each octree, the total amount of time to query each octree using each set of external shape. The queries are repeated in order to give significant run times, and avoid wide variation due to GC interruptions on the Xbox 360.

Results

Results vary depending on the specific sets of shapes, and vary from a run to the other. The results I'm listing here are qualitatively representative of the runs I made.

For the PC platform:

Virtual sparse: 0.016 / 1.185
Virtual: 0.011 / 1.136
Virtual dense: 0.096 / 1.029

Inline sparse: 0.016 / 0.777
Inline: 0.011 / 0.743
Inline dense: 0.093 / 0.651

Delegate sparse: 0.009 / 1.194
Delegate: 0.007 / 1.150
Delegate dense: 0.045 / 0.941

Specific sparse: 0.007 / 0.913
Specific: 0.007 / 0.890
Specific dense: 0.043 / 0.759

For the Xbox platform:

Virtual sparse: 0.170 / 1.062
Virtual: 0.194 / 0.972
Virtual dense: 2.193 / 1.800

Inline sparse: 0.117 / 0.574
Inline: 0.146 / 0.558
Inline dense: 2.082 / 0.677

Delegate sparse: 0.082 / 1.605
Delegate: 0.098 / 1.543
Delegate dense: 0.752 / 2.172

Specific sparse: 0.068 / 0.568
Specific: 0.094 / 0.542
Specific dense: 0.656 / 0.423

The pairs of numbers are the time to build and the time to query, in seconds. The datasets for the PC platform are much larger than those for the Xbox 360 platform. With identically sized datasets, the PC times were too low to be significant.

Observations

The time to build is always smaller for the C# implementation. This is not surprising, as I'm comparing two different algorithms, one using mutable structures (in the C# implementation), the other using immutable data structures requiring significantly more short-lived objects.

Using inlining improves the performance of the F# implementation, regardless of the platform. The generic C# implementation is the slowest, regardless of the platform. It's not showed here, but earlier measurements on the Xbox 360 showed that the problem was in LINQ.

The performance profile of F# on the Xbox 360 is not the same as on the PC. The F# does remarkably well on the PC, the inline implementation being the fastest. On the Xbox 360, the non-generic versions wins, but the F# versions holds its ground pretty well.

Conclusions

As far as I am concerned, F# is more than good enough when it comes to performance, compared to C#.

This does not mean that F# is better than C#, though. I spent my optimising efforts on the F# implementations, I can imagine a proficient C# programmer could do better than my variants in this language.

By the way, I used Red Gate's Reflector to analyse the code generated by the F# compiler and optimise it. I also used a profiler (Jet Brain's dotTrace Performance 4.0), but its measurements on my PC were not a good indication of the performance on the Xbox 360.

All source code is available on bitbucket.

Update: 2010 dec 14

I have updated the C# and F# implementations to match each other more closely:
- The C# implementation now uses List during construction of the octree, and arrays during querying. Apparently, iterating over an array is faster than iterating over List<t>.
- The F# implementation now uses mutable ResizeArray<t> (the F# synonym for List<t>, which I find more appropriate as the term "list" is coupled to "linked list" in my mind). Unlike the C# implementations, new nodes are still created when splitting leaves.

Updated results follow:

On the Xbox 360:

Batch	Build time (s)	Query time (s)
Virtual sparse	0,155	0,954
Virtual normal	0,247	0,873
Virtual dense	1,331	1,472
Inline sparse	0,110	0,548
Inline normal	0,199	0,480
Inline dense	1,202	0,497
Delegate sparse	0,084	1,629
Delegate normal	0,165	1,537
Delegate dense	0,927	2,406
Specific sparse	0,068	0,503
Specific normal	0,149	0,404
Specific dense	0,855	0,405

On the PC:

Batch	Build time (s)	Query time (s)
Virtual sparse	0,016	1,179
Virtual normal	0,017	0,994
Virtual dense	0,084	1,038
Inline sparse	0,014	0,809
Inline normal	0,016	0,671
Inline dense	0,082	0,685
Delegate sparse	0,010	1,199
Delegate normal	0,011	0,954
Delegate dense	0,053	0,955
Specific sparse	0,007	0,802
Specific normal	0,011	0,680
Specific dense	0,055	0,685

From these updated results, one can observe the following points:
- When it comes to querying, on the PC, the optimized F# and C# implementations (called Inline and Specific) are now running at more-or-less identical speeds. The non-optimized implementations are also very similar.
- On the Xbox 360, the C# optimized version is the fastest one, with the F# optimized close behind. The F# non-optimized version is noticeable faster than the C# non-optimized one. I think this is all due to the inefficiency of LINQ on the Xbox 360.
- Regarding build times, the F# versions are now closer to the C# versions, but still significantly slower. Although not a problem in practice (octrees are typically not re-built every frame), I wonder why.

The main conclusion from the first version of this article still holds: The performance of F# roughly matches that of C#.

I personally think that when it comes to beauty, the optimized F# version beats the C# version, but that's just my opinion :)

New trailer

2010-12-06T13:18:00.000-08:00

My game for the Xbox 360 has been renamed to "Asteroid Sharp Shooter".

They say "Ignorance is bliss", and they are right. After uploading a freshly made trailer for my game, I did a search on "Asteroid Hunter" on youtube. In the results, an indie game for mobile phones (Android and iPhone) turned up. It's dated from July 2010. Its author hasn't contacted me and as far as I know, probably does not know about me. I decided to rename my game nevertheless. I must say I don't like the new name as much, but "c'est la vie".

Anyway, here is the new trailer!

The music for the trailer is "Remnants of Yesterday" by "SynthR", under cc-by-sa 2.5.
My video is also protected by a Creative Commons license, namely cc-by-sa 3.0.

XNA GS 4.0 + F# 2.0 + Xbox 360 = love !

2010-11-27T09:21:00.000-08:00

Those of you who read the previous entry could notice in the comments that it did not take long for Don Syme, the designer of F#, to offer to help resolve the issue.

Less than a week later I had a new version of the FSharp core library tailored for the Xbox 360 in my mailbox. To the F# OSS team (Don Syme, Laurent Le Brun and Tomas Petricek): big thanks to all of you!

What took a bit more time was to build a Visual Studio 2010 template for projects using the new F# core library. Thanks a lot to Dan Mohl for his help. He is the author of templates for F# + Silverlight + WP7 projects, which are available on the Visual Studio gallery.

It's the first time I make a Visual Studio extension package, I hope I got it right. It's available on the Visual Studio gallery. If you try it out, please let me know if it worked for you (or if it did not).

A small but important note: In the project properties, the build tab has "generate tail calls" unchecked, both in Release and Debug builds. That's the way it is meant to be. If checked, your game will crash with an InvalidProgramException.

Enjoy!

XNA GS 4.0 + F# 2.0 + Xbox 360 = no love (yet...)

2010-11-15T07:57:00.000-08:00

I have good news and bad news.

Update

Actually, it's all good news, see the next post.
I considered erasing this article, but finally decided against it, as it shows how fast and helpful the people behind F# are.

So, just to clarify things: It is possible to write games for the Xbox 360 in F# using Visual Studio 2010 and XNA Games Studio 4.0

A word of caution: I don't want to give the impression that F# is officially supported by the XNA team at Microsoft. It isn't. As far as technical matters go, it works, and that's all I need as far as I'm concerned.

End of update

Good news first

1. I have posted Visual Studio templates, both for PC and the Xbox. I have only tested the Xbox one so far. Located on bitbucket, see http://bitbucket.org/johdex/fsxnalibtemplate

2. I have posted an example on how to use XNAUtils, it's included in the repository under "Samples". Hosted on bitbucket too.

Bad news

1. The templates are a bit rough around the edges still. Not so easy to install, in particular. I should probably upload them to the template repository so that they are accessible from with Visual Studio. However, I have other cats to whip at the moment, see below (I could have said bigger fish to fry ;)

2. When you attempt to run the example, you will get an "InvalidProgramException", which I suppose means the IL code generated by the F# compiler cannot be handled by the new XNA framework. I had been using XNA GS 3.1 and F# 1.9.9.9 (dating from may 2010, I believe). I don't know where the problem lies, XNA GS 4.0 or F# 2.0.

There is hope!

The source code for the F# compiler and the core library are now available on Codeplex. If the problem is indeed some hard-to-digest IL instruction, it should be fixable.

(Small note: The source code for the F# compiler has been available for some time now, but building was not a walk in the park. Now there are instructions, and the result can be legally used and distributed).

The next steps for me is to confirm my guesses, produce minimal reproduction cases, hope Microsoft will do something about it. That's quite a long shot though. As far as I know, there is no official support from Microsoft for languages other than C# in XNA.

Anyway, I'll see if I can get to grips with the source code of compiler and the core library and solve these issues.

By the way, I guess similar issues may exist on the Windows Phone 7 platform.

In the mean time...

XNA and F# can be used together for the PC platform. Don't let this post scare you from trying F# + XNA.

XNAUtils released under the Apache 2.0 license

2010-11-13T03:00:00.000-08:00

I have just created a public repository on bitbucket containing various reusable F# modules that I developed for Asteroid Hunter.

It's all there: https://bitbucket.org/johdex/xnautils/

I had a quick look over the code, it's all pretty clean and short, but it lacks documentation and examples on how to use it.

I ported the code and project files to XNA 4.0 and F# 2.0, but I have not tested the binaries. Chances are, they do not work yet.

Nevertheless, I hope it will be useful to others out here, and help more Xbox games to be written in F#.

UPDATE (Nov 25):
Asteroid Hunter was written for XNA Game Studio 3.1 using F# 1.9.9.9 (from may 2010). As I describe it in further details in the next post, the latest versions of XNA Game Studio and F# are not compatible.

Asteroid Hunter box art

2010-11-12T12:57:00.000-08:00

I'm working on Asteroid Hunter at a very steady pace: Every week, I do half of all the work that's left to do.

At this point, I had just enough motivation left to do the virtual box art which will appear on the Xbox marketplace when/if the game passes peer review.

Realized with Wings 3D, POVRAY and GIMP 2.

By the way, I have now submitted the game to peer review. If you are a member of the XNA Creator's Club, please consider reviewing the game. You are more than welcome to fail it if you find something wrong :)

Final development stages of Asteroid Hunter

2010-10-01T02:10:00.000-07:00

Things are a bit slow on the XNA development front on my side these days. I have stopped adding features to Asteroid Hunter, and am now in the process of getting the last feedback from testers before submitting the game to peer review. There are also a couple of art pieces that aren't ready yet, such as the box art and the introduction screen.

I thought I would post a couple screen shots from the game running on Xbox.

This first screenshot shows off an asteroid from short range, with Jupiter in the background. Professional and amateur astronomers might notice that the stars in the view don't match any known part the galaxy. Those were made by myself, using random noise and this tutorial. The asteroid model was made by an artist I am working with. I'm very happy with the looks, much better than anything I could have made.

The goal of the game is pretty simple: shoot a number of asteroids, then move on to the next level. Repeat until your ship is destroyed in a collision with an asteroid or other nasty stuff that hides in asteroid fields.
Not all asteroids are destructible, which forces the player to look for those that can be destroyed. As nothing looks more like an asteroid than another asteroid, spotting destructible asteroids can be challenging (or boringly difficult, according to testers).
To counter this problem, I added a scanner to the game. When activated, destructible asteroids are visible in shiny green color, other asteroids are darker. The image above illustrates this.
Notice also the radar in the lower right. It provides another way to track destructible asteroids.

The image above shows some of the nasty stuff that hides in asteroid fields that I mentioned earlier. A missile is flying towards the player's ship. To help spot missiles (spotting small things in space is a task many find difficult, it seems), a square-shaped marker is drawn around them.

This last image is self-explanatory. What it doesn't show is static and motion blur effects. I found those cool and easy to implement, but not very practical to have during while playing. I think they fit pretty well in the game over screen.

The game also features local multiplayer on splitscreen, in coop mode or deathmatch.
I hope to make it available on the Xbox Live Indie Games section for 80 MS points before the end of the year.

How to build an F# library for the Xbox 360 using msbuild

2010-06-06T01:26:00.000-07:00

In earlier post I described the difficulties of building F# libraries that will run on the Xbox 360.
I have been thinking all along that this was a bug in the integration of F# in Visual Studio, but I realized yesterday that it may be otherwise. Out of curiosity, I investigated how customization of msbuild works.
If you create a C# XNA project and open the csproj file, you should see these lines at the end:

If you go ahead and open Microsoft.Xna.GameStudio.Common.targets (located in C:\Program Files\MSBuild\Microsoft\Xna Game Studio\v3.1\), you will find some code dedicated to resolving assembly references:

<AssemblySearchPaths Condition=" '$(XnaPlatform)' != 'Windows' ">

I don't quite understand exactly what happens in these targets files, but it seems the XNA dev team had to do some magic to have assembly resolution work.
From there, I got the idea to import the XNA targets files in an F# project and see if it works. I tried that, mixing a C# XNA library project file with an F# library project. Guess what? It worked!

To summarize, here are the steps to build and F# XNA library project:
1. Make a copy of your F# library project, naming it "Xbox 360 Copy of my project.fsproj"
2. Find the section which sets the default platform, change it from AnyCPU to Xbox 360:

<Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration>
- <Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform>
+ <Platform Condition=" '$(Platform)' == '' ">Xbox 360</Platform>

3. Under the target framework version, add some specific XNA properties:

4. Find the two sections controlling the project settings depending on the configuration and platform. Change AnyCPU to Xbox 360, change the output directory, add some constants:

- <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
+ <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|Xbox 360' ">
<DebugSymbols>true</DebugSymbols>
<DebugType>full</DebugType>
<Optimize>false</Optimize>
<Tailcalls>false</Tailcalls>
<OutputPath>bin\Debug\</OutputPath>
- <DefineConstants>DEBUG;TRACE</DefineConstants>
+ <DefineConstants>DEBUG;TRACE;XBOX;XBOX360</DefineConstants>
<WarningLevel>3</WarningLevel>
</PropertyGroup>
- <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
+ <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|Xbox 360' ">
<DebugType>pdbonly</DebugType>
<Optimize>true</Optimize>
<Tailcalls>true</Tailcalls>
- <OutputPath>bin\Release\</OutputPath>
- <DefineConstants>TRACE</DefineConstants>
+ <OutputPath>bin\Xbox 360\Release\</OutputPath>
+ <DefineConstants>TRACE;XBOX;XBOX360</DefineConstants>
<WarningLevel>3</WarningLevel>
</PropertyGroup>

5. Remove the sections dedicated to the x86 platform.

- <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|x86' ">
- <DebugSymbols>true</DebugSymbols>
- <DebugType>full</DebugType>
- <Optimize>false</Optimize>
- <Tailcalls>false</Tailcalls>
- <OutputPath>bin\Debug\</OutputPath>
- <DefineConstants>DEBUG;TRACE</DefineConstants>
- <WarningLevel>3</WarningLevel>
- <PlatformTarget>x86</PlatformTarget>
- </PropertyGroup>
- <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|x86' ">
- <DebugType>pdbonly</DebugType>
- <Optimize>true</Optimize>
- <Tailcalls>true</Tailcalls>
- <OutputPath>bin\Release\</OutputPath>
- <DefineConstants>TRACE</DefineConstants>
- <WarningLevel>3</WarningLevel>
- <PlatformTarget>x86</PlatformTarget>
- </PropertyGroup>

6. Add some XNA-specific stuff (no idea what it does, not sure if it's needed):

+ <ItemGroup>
+ <BootstrapperPackage Include="Microsoft.Net.Framework.2.0">
+ <Visible>False</Visible>
+ <ProductName>.NET Framework 2.0 %28x86%29</ProductName>
+ <Install>false</Install>
+ </BootstrapperPackage>
+ <BootstrapperPackage Include="Microsoft.Net.Framework.3.0">
+ <Visible>False</Visible>
+ <ProductName>.NET Framework 3.0 %28x86%29</ProductName>
+ <Install>false</Install>
+ </BootstrapperPackage>
+ <BootstrapperPackage Include="Microsoft.Net.Framework.3.5">
+ <Visible>False</Visible>
+ <ProductName>.NET Framework 3.5</ProductName>
+ <Install>true</Install>
+ </BootstrapperPackage>
+ <BootstrapperPackage Include="Microsoft.Windows.Installer.3.1">
+ <Visible>False</Visible>
+ <ProductName>Windows Installer 3.1</ProductName>
+ <Install>true</Install>
+ </BootstrapperPackage>
+ <BootstrapperPackage Include="Microsoft.Xna.Framework.3.1">
+ <Visible>False</Visible>
+ <ProductName>Microsoft XNA Framework Redistributable 3.1</ProductName>
+ <Install>true</Install>
+ </BootstrapperPackage>
+ </ItemGroup>

7. Fix references:

<ItemGroup>
<Reference Include="Microsoft.Xna.Framework">
- <HintPath>..\..\..\..\..\..\..\..\..\Program Files\Microsoft XNA\XNA Game Studio\v3.1\References\Windows\x86\Microsoft.Xna.Framework.dll</HintPath>
+ <Private>False</Private>
</Reference>
<Reference Include="Microsoft.Xna.Framework.Game">
- <HintPath>..\..\..\..\..\..\..\..\..\Program Files\Microsoft XNA\XNA Game Studio\v3.1\References\Windows\x86\Microsoft.Xna.Framework.Game.dll</HintPath>
+ <Private>False</Private>
</Reference>

8. Insert the C# and XNA target files, before the F# targets file:

+ <Import Project="$(MSBuildBinPath)\Microsoft.CSharp.targets" />
+ <Import Project="$(MSBuildExtensionsPath)\Microsoft\XNA Game Studio\Microsoft.Xna.GameStudio.targets" />
<Import Project="$(MSBuildExtensionsPath32)\FSharp\1.0\Microsoft.FSharp.Targets" />

You are almost there. You now have a project file you can open in Visual Studio. From there, you can add a reference to the correct FSharp.Core assembly (the one for .Net CF 2.0)

That should be it. There are a few more things that need to be fixed, such as project GUIDs, but Visual Studio will happily do that for you, all you have to do is open the fsproj file with Visual Studio.

When building, remember to choose "Xbox 360" as the platform in the build settings.

Discriminated unions: a powerful tool for implenting state machines

2010-05-15T00:16:00.000-07:00

When writing a game using XNA Game Studio, the programmer quickly faces the problem of dealing with persistent data. Typically, a game will need files to store high-scores, game progress, user settings...
On the PC platform, the programmer has two ways of dealing with file I/O: synchronously, which is OK for dealing with small amounts of data, or asynchronously, which is used to avoid leaving the user with an unresponsive application when large files (or large numbers of small files) are read or written.
On the Xbox, the only available option is the asynchronous one. Another odd side of XNA on the Xbox is the fact that programmers cannot decide on which storage device files should be located. If the Xbox on which the game is running has memory cards plugged in, the user must be asked which device (hard disk or memory card) he/she wishes to use.
In other words, performing I/O on the Xbox requires to go through several steps, and all these steps must be spread out over multiple iterations of the game update loop.

This is one of these situations where state machines are very handy. Considering the file I/O example mentioned above, I have designed a state machine with the following states:

- Ready
- Start requesting user storage
- Requesting user storage
- Start sign in
- Signing in
- Start requesting global storage
- Requesting global storage
- Doing I/O
- Failed I/O
- Successful I/O

User storage is used to store user-specific files, e.g. user preferences. Global storage is used for scores.
Some of these states have specific data. For instance, requesting user storage requires an user id.

In C#, state machines can be a bit cumbersome to implement. Typically, one would use an object containing an enum for the state, and all fields needed for each state.
This last part annoys me a bit, as it hides the relation between states and their data. With time, it's easy to lose track of this connection.

In F#, I see two ways of implementing state machines. The more elaborate way uses a custom workflow and an algorithmic representation of the state machine. Actually, presenting workflows as an implementation technique for state machines is a bit clumsy, as it's really the other way around. I'll stop here for now with custom workflows, more on this subject in a later post.
The simpler way for someone who is not too familiar with functional languages and monads consists of using a discriminated union.

type State =
| StartReqTitleStorage
| RequestingTitleStorage
| StartSignIn of PlayerIndex
| SigningIn of PlayerIndex
| NotSignedInInfo
| StartReqUserStorage of PlayerIndex
| RequestingUserStorage
| DoingIO
| FailedIO of (unit -> unit)
| SuccessfulIO of (unit -> unit)
| Ready

Then comes the data type for the storage component.

type Data =
{ state : State
titleStorage : StorageDevice option
userStorage : StorageDevice option }

As an example of a non-trivial operation, here is the code to request user-specific storage.

let requestUserStorage (p : PlayerIndex) data =
match data.state with
| Ready when Gamer.SignedInGamers.[p] = null -> { data with state = StartReqUserStorage(p) }
| Ready                                      -> { data with state = StartSignIn(p) }
| _     -> raise (new InvalidOperationException())

I particularly like the way pattern matching and the "when clause" combine nicely to express the fact that a user must be signed in before user-specific storage can be requested.
Note also how the programmer is forced to handle the erroneous case of calling requestUserStorage when the storage component is not ready.

This style of implementation using immutable data and functions would not feel very C#-ish for someone using this code from C#. This is easily solved by wrapping all the code in a class:

type StorageComponent(game) =
inherit GameComponent(game)

let data = ref { state = Ready ; titleStorage = None ; userStorage = None }

let getDoSet f =
data := f !data

member x.RequestUserStorage(p : PlayerIndex) =
getDoSet (requestUserStorage p)

For the curious, getDoSet is a helper function I introduced to hide some locking mechanism. The implementation shown here is not the one I actually use. I left it here just because I love to pass functions around ;)

The full code is available on bitbucket, as a part of XNAUtils.

Things that don't work on Xbox

2010-03-26T14:06:00.000-07:00

Although it is possible to write F# code that runs on the Xbox 360 using XNA Game Studio, not everything works.

There are API problems, probably due to the fact that the F# core assembly I am using is built for the compact framework. Although the .NET framework on the Xbox 360 is based on the compact framework, there are obviously significant differences.
I hope I will be able to take a look at this when Microsoft releases the source code of the F# code library in an easily compilable form (the F# team has said that they intended to release the F# compiler and libraries under an Open Source license when it reaches a stable state).

For instance a call to sprintf (for debugging purposes) resulted in an exception, due to a missing method, it seems.

Similarly, attempts to use async workflows also fail. This is really a shame, as it means you are on your own when it comes to concurrent applications. For instance, the map_parallel function I used in tutorial 7 raises an exception.

In addition to binary compatibility issues specific to F#, there are also generic practical issues.

After implementing my own version of Async.Parallel, I realized it probably would not be much help, as the overhead of multi-threading is a bit too much for the time intervals of computations which must run in a 60th of a second (16.7 ms). Using parallel_map resulted in a factor two performance drop, in my case. For those interested, here is the code I was using (no guarantee of correctness of any kind!):


let map_parallel (func : 'T0 -> 'T1) (data : 'T0[]) : 'T1[] =
    let results = Array.zeroCreate data.Length
    let num_threads = 4
    let ranges = Array.init num_threads (fun i -> i * data.Length / num_threads, (i + 1) * data.Length / num_threads - 1)

    let count = ref num_threads
    let notify = new System.Threading.AutoResetEvent(false)
    
    for (start, stop) in ranges do
        System.Threading.ThreadPool.QueueUserWorkItem (
            fun _ ->
                try
                    for i in start..stop do
                        results.[i] <- func data.[i]
                finally
                    let n = System.Threading.Interlocked.Decrement count
                    if n = 0 then
                        System.Threading.Thread.MemoryBarrier()
                        notify.Set() |> ignore
        )
        |> ignore
    
    notify.WaitOne() |> ignore
    results

What works well is to dispatch rendering and updating on two threads. The rendering thread must remain on the "main" thread, the updating thread can run on a separate thread.

Is F# worth the trouble on Xbox? I would say it is. Compared to C#, the language has good support for manipulating arrays, an "inline" keyword that comes very handy when writing generic code that must run fast. This makes it a good language for computation-heavy applications (of which simulation-oriented games are).

Another area where the language should shine is in high-level UI code. I have thoughts about using custom workflows to conveniently map operations spanning over multiple frames on the game update loop.

Array-oriented programming

2010-03-04T10:40:00.000-08:00

I have been working for quite some time now on Asteroid Hunter. This has not left me much time for exploration and experimentation with F#, but there is quite a bit a learned during the process anyway.

One of the biggest technical challenges of developing games for the Xbox platform using XNA Game Studio is probably how to keep garbage collection from eating too much performance.

The classical way which I think all developers are using is to preallocate your objects, and recycle them during gameplay. As a complement, one can also use structs instead of classes, as structs do not require garbage collection. The goal here is to never allocate new space, as every megabyte allocated triggers a new garbage collection. Depending on the number of objects the heap contains, a garbage collection can take from a few milliseconds to fractions of seconds, the latter being unacceptable for a game refreshing the screen 60 times per second.

There is another way, and I know no one who uses it. In this approach, it's ok to allocate a lot of memory space, as long as it's used by few objects. In other words, an array of value types, such as floats or structs, is cheap to allocate.

In a first version of the game, I used records to model asteroids, and stored these records in immutable arrays. This approach quickly showed its limits. I modified the code to use arrays of structs, also immutable. It was better, but this method incurred very high copying costs, as changing one field, for instance the position, required to copy the entire struct (composed of a couple more vectors for the speed, orientation, angular velocity...).

In the current version, I no longer have a datatype representing a single asteroid. Instead, I use multiple arrays of vectors, one array for the positions, one array for the speeds, etc. I rely heavily on higher order functions in the Array module, such as Array.map, Array.map2 and Array.mapi.

The code below illustrates the kind of programming style I am describing above. Take it with a nip of salt, it was written in quite a rush, and the Dream Build Play deadline left me little (as in "none at all") time for code cleanup.


type AsteroidArrays =
    { pos : Vector3[] ;
      speed : Vector3[] ;
      wspeed : Vector3[] ;
      wpos : Quaternion[] ;
      bsph : BoundingSphere[] ;
      heat_level : float32[] ;
      mass : float32[] ;
      radius : float32[] ;
      rank : int[] ;        // -1 means dead.
      heat_rate : float32[] ;
      color : Vector3[] }


let integrate (V : Vector3) (dt : float32) (impulses : Pair list) (arr : AsteroidArrays) =
    let speed = Array.copy arr.speed
    for impulse in impulses do
        let idx = impulse.fst
        let impulse = impulse.snd
        speed.[idx] <- speed.[idx] + impulse
        
    let pos =
        Array.map2 (fun pos speed -> pos + dt * speed |> WarpCoord.warp V) arr.pos speed

    let rot =
        Array.map (fun wspeed -> new Quaternion(dt * wspeed, 0.0f)) arr.wspeed

    let wpos =
        Array.map2 (fun wpos rot ->
                let x = wpos + Quaternion.Multiply(rot * wpos, 0.5f)
                x.Normalize()
                x)
            arr.wpos
            rot

    let bsph =
        Array.map2 (fun pos radius -> new BoundingSphere(pos, radius)) arr.pos arr.radius
                    
    { arr with
        pos = pos ;
        speed = speed ;
        wpos = wpos ;
        bsph = bsph }

When I dived into redesigning my asteroids from arrays of structs to a record of arrays, I was nervous I would never make it in time. When all you have is four days work, you don't want to spend two days on a redesign. Happily, it took less than four hours, which positively surprised me. The F# mode in Visual Studio may lack most of the refactoring tools available in C#, yet rewriting code goes a lot faster than I would have expected.

This immutable approach does not perform too badly compared to the mutable way, as all values typically need to be touched anyway. I haven't actually done any measurements, but I don't expect the immutable approach to be worse than twice as slow as in-place modifications.

I don't know if memory fragmentation could be a problem. The arrays in question are small enough that they are allocated on the regular heap (as opposed to the large object heap), and the remote performance monitor reports zero compactions. Moreover, all my arrays have fixed sizes, which should keep fragmentation at bay.

If you read some of my earlier posts in this blog, you might have guessed that I have my doubts about object-oriented programming. As far as performance-critical parts of the code are concerned, I am now convinced that one should stay away from objects, be it in the form of structs or classes. Whether one can get away with immutable arrays or not (as opposed to mutable arrays) probably depends on how much performance is needed.

That will be all for now, I am planning to write about concurrency and generic space-partitioning in my next posts.

Asteroid Hunter submitted to Dream Build Play

2010-03-04T10:31:00.000-08:00

Asteroid Hunter, the 3d variant of "Asteroids" written in F#, is participating in Dream Build Play.

The game features 12 levels of increasing difficulty. In addition to the solo mode, you can also play against up to 3 of your friends on split screen.

I am hoping to publish the game on the XBox Live Indie Games channel later this spring.

Asteroid Hunter, 3rd play test

2010-01-04T12:07:00.000-08:00

I've been busy with Asteroid Hunter during the Christmas break.

The result is visible in this video:

If you are a premium member of the XNA Creator's Club, feel free to play test the game and leave me your impressions there.

The next version will also be available on PC to the general public.

From the technical point of view, the nicest new feature is probably an AI capable of steering ships and missiles toward moving targets, avoiding asteroids in the process.

The program also feels a bit more like an actual game now, with scores, explosions, levels of difficulty, powerups to pick up... There is obviously a lot of polishing left to do, though. I'm leaving that to the end.

It was surprising how easy it was to pick up the coding where I left it this summer, even though I hardly touched the code this autumn.

Inheritance nightmares

2009-12-13T08:58:00.000-08:00

I was first exposed to object-oriented programming when learning C++. I am now starting to realize how confusing that has been. In particular, inheritance in C++ is often used and abused to implement various kinds of relationships between classes. I am writing "abused", because the only legitimate use of inheritance is for IS-A relationships. Other relationships such as HAS-A and IS-IMPLEMENTED-IN-TERMS-OF should not use inheritance. In these cases composition is preferable. It is therefore important to be able to differentiate between the different kinds of relationships.

However understanding IS-A relationships is not as easy it might seem. To illustrate the problem, the case of squares and rectangles is sometimes used.

All squares are also rectangles, and it seems natural that a class "Square" should be related to a class "Rectangle": Square IS-A Rectangle.

In C#, this could be written:


class Rectangle
{
}

class Square : Rectangle
{
}

Now that we have our class hierarchy, let us start adding methods and fields:


class Rectangle
{
    float length;
    float width;

    public Rectangle(float l, float w)
    {
        length = l;
        width  = w;
    }

    public float GetLength() { return length; }
    public float GetWidth()  { return width; }
}

So far, no problem. Things get tricky when we want to add setter methods:


class Rectangle
{
    float length;
    float width;
    ...
    public void SetLength(float l) { length = l; }
    public void SetWidth(float w)  { width  = w; }
}

class Square : Rectangle
{
    ...
    public void SetSize(float s) { SetLength(s); SetWidth(s); }
}

The problem is that Square inherits SetLength and SetWidth, which makes it possible to have squares with non-matching lengths and widths. A non-satisfactory solution consists of overriding SetLength and SetWidth in Square:


class Rectangle
{
    float length;
    float width;
    ...
    public virtual void SetLength(float l) { length = l; }
    public virtual void SetWidth(float w)  { width  = w; }
}

class Square : Rectangle
{
    ...
    public override void SetLength(float s) { base.SetLength(s); base.SetWidth(s); }
    public override void SetWidth(float s)  { base.SetLength(s); base.SetWidth(s); }
}

This solution is not satisfactory because users of Rectangle may expect that it should be possible to set widths and lengths independently.


void SetWidthAndLength(Rectangle rect)
{
    rect.SetWidth(1.0);
    rect.SetLength(2.0);
    Debug.Assert(rect.GetWidth() == 1.0);
    Debug.Assert(rect.GetLength() == 2.0);
}

These assertions fail when SetWidthAndLength is passed an instance of Square. Many articles go on by stating that Rectangle and Square are in fact not IS-A related, although the initial intuition told otherwise. This is usually the point where the Liskov Substitution Principle is introduced. While understanding this principle is certainly a good thing for anyone learning about object-oriented programming, one of the biggest selling points of object-oriented design is that it is supposed to be intuitive.

After all, all squares are rectangles, aren't they? Indeed, this is true of immutable squares and rectangles. Remove the setters, and all problems disappear. The substitution principle falls in line with what intuition tells us.

Going a bit further, let us consider a function which transforms squares.


Square TransformSquare(Square square, SquareScaling scale)
{
    float scaleFactor = ...;
    return scale.Do(square, scaleFactor);
}

If we have at hand a library which provides translation and rotation operations on rectangles, we are very close to being able to use these with "Transform". All we need is to write a bit of code to turn rectangles which have identical lengths and widths into squares:


class RectangleUniformScalingAdapter : SquareScaling
{
    RectangleUniformScaling adaptee;
    ...
    public override Square Do(Square square, float factor)
    {
        Rectangle tmp = adaptee.Do(square, factor, factor);
        Debug.Assert(tmp.GetLength() == tmp.GetWidth());
        return new Square(tmp.GetLength());
    }
}

On the other hand, if we are provided a function working on rectangles, a library providing transformations on squares would not be very valuable.

In other words, we could say that RectangleUniformScaling IS-(almost)-A SquareScaling. Note how the IS-A relationship is reversed.

If different parts of the interfaces of Rectangle and Square do not agree on the direction of the relationship, we have a problem.


class Rectangle
{
    float width;
    float length;

    public virtual float GetWidth() { /* Easy to implement */ }
    // Uniform scaling
    public virtual void Scale(float scale) { /* could use Square.Scale() */ }
    public virtual void Scale(float scaleWidth, scaleLength) {...}
}

class Square
{
    public virtual float GetWidth() {/* could use Rectangle.GetWidth() */ }
    public virtual void Scale(float scale) { /* Easy to implement */ }
    public virtual void Scale(float scaleWidth, scaleLength) { /* Impossible to implement */ }
}

Who should inherit from who?

At this point, readers interested in F# and functional programming languages might wonder what all this has got to do with F#. I think that the common mix of mutability and inheritance is not a very strong basis for good software design. I never really realized that until I took a look at functional programming and immutability.

A bit of F# in your C#

2009-12-06T10:23:00.001-08:00

At work, I'm using way more C# than F#.

I have however noticed that functional programming concepts from F# have found their way into my C# code. The first sign of this is when LINQ extension methods start appearing where foreach loops used to be.

F# has a higher-order function called "fold" which can be used for collecting information from a sequence into a single object. A common use is for summing, but it can also be used for extracting one item from the sequence. For instance, it can be used for finding the minimal item according to a specific ordering.

This is a problem Jon Skeet has tackled in a blog from 2005 entitled A short case study in LINQ efficiency.

For instance, given a sequence of pairs of string*number denoting names and ages of people, find the youngest person. Note that we are not only interested in finding the age of the person, we want both the name and the age.

Here is a solution in F# which uses "fold".


let people = [("me", 32.0); ("someoneelse", 75.0)];;
let cmp a b =
    match a, b with
    | Some (_, a1), (_, a2) when a1 <= a2 -> a
    | _ -> Some b;;

let youngest = List.fold cmp None people;;

Function "fold" iterates over each item in the list. For each item, it invokes a function to which it passes the item together with a value called the accumulator. The function returns the new value for the accumulator.

In the example above, the type of the accumulator is "Some person or None", where "None" denotes "no one".

Function cmp simply compares an accumulator with a person, and returns the person if the accumulator is "None", the youngest of the person and the accumulator otherwise.

This solution, when translated to C# 4.0, gives an elegant and efficient solution. I wonder why Jon Skeet did not mention it. If he missed it, he's not alone, a search on Google for how to implement one's own LINQ extension method shows many articles using precisely this problem as illustration.


var people = new Tuple<string, double>[] {
    Tuple.Create("me", 32.0),
    Tuple.Create("someoneelse", 75.0) };

var youngest =
    people.Aggregate(null as Tuple<string, double>,
                     (youngestSoFar, v) =>
                     (youngestSoFar != null && youngestSoFar.Item2 <= v.Item2) ?
                         youngestSoFar : v);

I haven't done any time measurements, but this solution should iterate over the array of people no more than once, and might even be just as efficient as the method using foreach.

F# on the Xbox 360

2009-12-06T03:37:00.001-08:00

This article describes how to build an XNA Game Studio application using an F# library in such a way that it can be run on the Xbox 360. It applies to the current version of F#, 1.9.7.8

A method was first described in this blog by Jack Palevich. Most of his blog post still applies, except for step 2.

In order for an .net assembly to be usable on the Xbox 360, it must be linked against dlls for the Xbox 360, which can be found in <Program Files directory>\Microsoft XNA\XNA Game Studio\v3.1\References\Xbox360.

In particular, it must be linked against mscorlib.dll for the Xbox 360, which is the difficult part.

By default, when you create an F# library in Visual Studio, it is linked against FSharp.Core.dll, which references mscorlib for the PC.

In order to avoid conflicts between versions of mscorlib, one must build an F# library targeted at the Compact Framework 2.0, which is what the XNA .net framework is built upon.

The problem is that neither Visual Studio nor msbuild support this for F# libraries. The only solution is to compile the F# library using the F# compiler directly:

"C:\Program Files\FSharp-1.9.7.8\bin\fsc.exe"
-o:obj\Release\XBox360.dll
--standalone --noframework --define:TRACE --optimize+ --tailcalls+
-r:"C:\Program Files\FSharp-1.9.7.8\CompactFramework\2.0\bin\FSharp.Core.dll"
-r:"C:\Program Files\Microsoft XNA\XNA Game Studio\v3.1\References\Xbox360\Microsoft.Xna.Framework.dll"
-r:"C:\Program Files\Microsoft XNA\XNA Game Studio\v3.1\References\Xbox360\mscorlib.dll"
-r:"C:\Program Files\Microsoft XNA\XNA Game Studio\v3.1\References\Xbox360\System.Core.dll"
-r:"C:\Program Files\Microsoft XNA\XNA Game Studio\v3.1\References\Xbox360\System.dll"
--target:library --warn:3 --warnaserror:76 --fullpaths --flaterrors
<your F# source files here>

Beside specifying the correct XNA assemblies using "-r:", this command line also does the following:

- Enables optimization using --optimize+ and --tailcalls+
- Embeds the F# core library in the assembly, using --standalone

Not very pretty, and hopefully future versions of F# and its integration into Visual Studio will remove the need to call fsc.exe explicitly.

Asteroids 3d strikes back

2009-07-14T08:51:00.001-07:00

I got back to working on my asteroids clone, written in F# using the XNA framework.

Interfaces made convenient by type constraints

2009-07-08T09:49:00.000-07:00

If my previous entry convinced you to make extensive use of interfaces, you may have encountered a problem, namely that calling methods implementing interfaces requires casting:

let link = new Link("link", config, ...)
// We want to write:
link.Send(data)
// But that does not compile. Instead, we must write:
(link :> ILinkOutput).Send(data)

The bad news are that there is no work around. The good news is that this situation does not happen too often in practice, as the creator of a link is in general not the user. New instances are often forwarded to other objects or functions, which will see them as ILinkOutput, thus not requiring a cast:

let register (p : ISender) (l : ILinkOutput) =
    p.AddOutputLink(l)    // OK: p is an ISender, no need for explicit cast
    l.ConnectInputTo(p)   // OK: l is an ILinkOutput, no need for explici cast

let link = new Link(...)
let process = new Process(...)
register process link       // OK: process and link automatically upcasted

Now, what happens if we have a function taking a process and which needs to use two of its interfaces? There are two obvious solutions, which are not so pretty.

Ugly-ish:

let register (p1 : ISender) (l : Link) (p2 : IReceiver) =
    p1.AddOutputLink(l) // Nice
    p2.AddInputLink(l)  // Nice
    (l :> ILinkOutput).ConnectInputTo(p1)   // Not so nice
    (l :> ILinkInput).ConnectOutputTo(p2)   // Not so nice

Uglier:

let register (p1 : ISender) (l1 : ILinkOutput) (l2 : ILinkOutput) (p2 : IReceiver) =
    p1.AddOutputLink(l) // Nice
    p2.AddInputLink(l)  // Nice
    l1.ConnectInputTo(p1)   // Nice (is it?)
    l2.ConnectOutputTo(p2)   // Nice (is it?)

// Set up two processes communicating with each other.
// As links are uni-directional, use two links.
let p1 = new Process(...)
let p2 = new Process(...)
let link_p1_p2 = new Link(...)
let link_p2_p1 = new Link(...)

// p1 -> p2
register p1 link_p1_p2 link_p2_p1 p2  // Oops!!!
// p2 -> p1
register p2 link_p2_p1 link_p1_p2 p1  // Oops!!!

So many 1s and 2s... We really meant to write:

// p1 -> p2
register p1 link_p1_p2 link_p1_p2 p2 
// p2 -> p1
register p2 link_p2_p1 link_p2_p1 p1

The correct solution uses generics and type constraints:

let register
    (p1 : ISender)
    (l : 'L
        when 'L :> ILinkInput
        and  'L :> ILinkOutput)
    (p2 : IReceiver) =

    p1.AddOutputLink(l)
    p2.AddInputLink(l)
    l.ConnectInputTo(p1)
    l.ConnectOutputTo(p2)

// Set up two processes communicating with each other.
// As links are uni-directional, use two links.
let p1 = new Process(...)
let p2 = new Process(...)
let link_p1_p2 = new Link(...)
let link_p2_p1 = new Link(...)

// p1 -> p2
register p1 link_p1_p2 p2
// p2 -> p1
register p2 link_p2_p1 p1

Another use of type constraints is for cases when you want to pass lists of ISenders to a function.

Problem:

let sendAll (ps : ISender list) data =
    ps
    |> List.iter (fun p -> p.Send(data))

let p1 = new Process(...)
let p2 = new Process(...)

sendAll [ (p1 :> ISender) ; (p2 :> ISender) ] data  // Blah!

Solution:

let sendAll (ps : 'S list when 'S :> ISender) data =
    ps
    |> List.iter (fun p -> p.Send(data))

let p1 = new Process(...)
let p2 = new Process(...)

sendAll [ p1; p2 ] data

Which can also be written:

let sendAll (ps : #ISender list) data =
    ps
    |> List.iter (fun p -> p.Send(data))

let p1 = new Process(...)
let p2 = new Process(...)

sendAll [ p1; p2 ] data

Breaking up classes using interfaces

2009-07-08T08:23:00.000-07:00

When I started writing F# programs whose code span over multiple files, I was surprised to see that the order of compilation of these files matters. If the code in file B.fs refers to types or functions in A.fs, then A.fs must be compiled before B.fs.

Now, what happens if A.fs and B.fs depend on each other? In this case, you have a problem. The easy fix is to merge the two files, but this solution does not scale well. Another solution is to break code into smaller pieces, building small "islands" of circular dependencies, which can each be moved into their own file. Easily said, but not so easily said.

Consider an application involving processes and links. Processes can be executed, and can communicate with each other using unidirectional links.

The code might look like this:

type Process(name, config, ...) =
    // Construction
    ...

    // Methods
    //  Connection to links
    member x.AddInputLink(link : Link) = ...
    member x.AddOutputLink(link : Link) = ...

    //  Control execution
    member x.ExecuteInSomeWay(args) = ...
    member x.ExecuteInSomeOtherWay(args) = ...
    member x.CheckIsReady() = ...
    member x.MarkAsReady() = ...

    //  Debugging, and other stuff...
    member x.ToggleDebugging(b) = ...
    member x.SetDebugOutput(o) = ...
    ...

and type Link(name, config, ...) =
    // Construction
    ...

    // Methods
    //  Connection to processes
    member x.ConnectOutputTo(p : Process) = ...
    member x.ConnectInputTo(p : Process) = ...

    //  Read/Write data
    member x.Send(data) = ...
    member x.Receive() = ...

    //  Debugging ...
    member x.ToggleDebugging(b) = ...
    member x.SetDebugOutput(o) = ...
    ...

As Process and Link are mutually dependent, their code must be all in one file. That may seem OK at first, but things will become harder to manage as more code is added over time.

A first solution is to introduce interfaces for Process and Link, simply duplicating all their method signatures, and replace all occurrences of classes Process and Link by their interfaces. The interfaces can be moved to a separate file, which should be shorter, as it contains no code. Classes Process and Link can now each live in separate files.

Interfaces.fs:

type IProcess =
    //  Connection to links
    abstract AddInputLink : ILink -> ...
    abstract AddOutputLink : ILink -> ...

    //  Control execution
    abstract ExecuteInSomeWay : Args -> ...
    ...

    //  Debugging, and other stuff...
    member x.ToggleDebugging : bool -> unit
    ...

and type ILink =
    //  Connection to processes
    abstract ConnectOutputTo Process -> unit
    ...

Process.fs:

open Interfaces

type Process(name, config, ...) =
    // Construction
    ...

    // Interface implementations
    interface IProcess with
        member x.ExecuteInSomeWay(args) = ...
    ...

Link.fs:

open Interfaces

type Link(name, config, ...) =
    // Construction
    ...

    // Interface implementation
    interface ILink with
        member x.ConnectOutputTo(p : IProcess) = ...
    ...

Still, Interfaces.fs may be excessively long, and we may end up in a situation where all interfaces are defined in one large file. Not very pleasant.

The next step consists of breaking up the interfaces. The debugging-related methods obviously belong to a IDebugable interface, which need not be concerned with the details of processes and links.

A process which is connected to the input side of a link has no need to have access to the methods taking care and transferring data from the link to the process, which indicates that ILink could be split in e.g. IInputLink and IOutputLink.

There is another case of excessive method exposure. Links do not control the execution of processes, that's the task of the scheduler. The final decomposition may look as shown below.

IActivable.fs:

type IActivable =
    abstract CheckIsReady : unit -> bool
    abstract MarkAsReady : bool -> unit

IExecutable.fs:

type IExecutable =
    abstract ExecuteInSomeWay : Args -> ...
    abstract ExecuteInSomeOtherWay : Args -> ...

InputInterfaces.fs:

type IReceiver =
    abstract AddInputLink : ILinkInput -> unit

and type ILinkInput =
    abstract Receive : unit -> Data
    abstract ConnectOutputTo : IReceiver -> unit

OutputInterfaces.fs:

type ISender =
    abstract AddOutputLink : ILinkOutput

and type ILinkOutput =
    abstract Send : Data -> unit
    abstract ConnectInputTo : ISender -> unit

The techniques shown here are by no means specific to F#, and are part of the "proper programming" techniques every object-oriented programmer should know and use. Before using F#, I almost exclusively used interfaces for polymorphism, on "as-needed" basis. The fact is, interfaces are also useful for modular programming.

Decomposing programs into interfaces and implementation helps writing reusable, readable code. It does have a cost, though, as it requires more typing. As long as keyboards remain cheaper than brains, the benefits should outweigh the costs.

Concurrency on a single thread

2009-07-08T07:21:00.000-07:00

When I wrote my article about concurrency, I did a bit of searching to find out how to use multi-threading in F#. One of the hits was a blog entry on HubFS by gneverov titled "Hell Is Other Languages : Concurrency on a single thread". At that time, I was a bit confused by the article. Why would one want single-threaded concurrency when we already had multi-threaded concurrency? Part of the answer lies in reactive programming.

Recently, I read an article by Shawn Hargreaves, "Pumping the Guide", where he describes some design issues with using the Guide on the Xbox. The Guide is the part of the Xbox GUI which is used for performing common operations, such as entering text, selecting a device where game data is saved, seeing which of your friends are online and what they are doing... The problem is to have the game still running in the background while the Guide is opened.

The solution chosen by the XNA team was to make calls to the Guide non-blocking. This however makes it harder for game developers to use it, as it forces them to keep track of the application state explicitly, including both the state of the game and the state of the Guide.

Kevin Gadd's shows a elegant solution to this problem in C# using custom enumerators in an article aptly named "Asynchronous programming for xna games with Squared.Task".

Kevin's implementation in C# is as pretty as it can get, but it would probably look even better in F# using asynchronous computations. Although the async { ... } notations is exactly what we want, the Async functions do not seem to support the kind of single-threaded concurrency that Kevin's Square.Task does.

The code by gneverov however should be easy to modify to execute one single step in one of the active tasks, if it does not already support that.

WiX again.

2009-07-02T10:24:00.000-07:00

In my previous post I expressed my disappointment with WiX. However, after an additional day of struggling with it, I may change my mind. I managed to find a pretty straightforward solution to (almost) all my problems. Getting there wasn't straightforward at all, though.

Here are the lessons I learned in the process:

Do not overwrite existing files using <File> elements.
When your software gets uninstalled, it will remove your file, but the old file won't be restored. The solution that first popped up in my mind, namely to backup old files, isn't as easy as it seems. The problem is that the backup copy will be left behind after the software gets uninstalled.

<CopyFile> is not your friend.
...at least as far as backing up existing files goes. I tried to back up the old file by copying it into my application's folder using CopyFile, and failed miserably. Maybe I missed something, but it seems CopyFile is designed to make copies of the files you install, not of existing files.

<CustomAction> is way too complex for its own good (and yours).
CustomAction can be used in many different ways, using slightly different syntaxes. I attempted to use it to backup files, and finally succeeded. It wasn't easy. I tried to use it to run a command (COPY), but it failed. Same problem with other commands such as REN and DEL. No success running batch files either. I tried running a jscript, and that failed too. Since the creator pf WiX advises against using scripts in custom actions, I did not insist. I ended up using "xcopy.exe", which worked (with a catch: the target must be an existing directory, otherwise xcopy demands to interact with the user, and we don't want that).

I found ONE use of CustomAction, and I am not planning on trying out other uses. At least not for a while.

<RemoveFile> is your friend.
Unlike CopyFile, it's easy to use to clear up stuff in your application's folder. I used it to remove the backup after restoring it during uninstallation.

In case you wonder how to handle back-ups in WiX, that's the way I did it:

<Property Id='XCOPY'>xcopy.exe</Property>
...
<CustomAction Id='Backup'
Property='XCOPY'
ExeCommand='"[ExistingFolder]PlugIn.dll" "[OldFiles]" /Y'
Result='check'
Execute='deferred' />

<CustomAction Id='Install'
Property='XCOPY'
ExeCommand='"[NewFiles]PlugIn.dll" "[ExistingFolder]" /Y'
Result='check'
Execute='deferred' />

<CustomAction Id='Restore'
Property='XCOPY'
ExeCommand='"[OldFiles]PlugIn.dll" "[ExistingFolder]" /Y'
Result='ignore'
Execute='deferred' />

<InstallExecuteSequence>
<Custom Action='BackupPlugIn' Before='InstallPlugIn'>Not Installed</Custom>
<Custom Action='InstallPlugIn' After='InstallFiles'>Not Installed</Custom>
<Custom Action='RestorePlugIn' Before='RemoveFiles'>Installed</Custom>
</InstallExecuteSequence>

...
<Directory Id='NewFiles' Name='New Files'>
<Component Id='NewFiles' Guid='...'>
<File Id='NewFile' Name='Plugin.dll' Source='build/PlugIn.dll' />
</Component>
</Directory>

<Directory Id='OldFiles' Name='Old Files'>
<Component Id='OldFiles' Guid='...'>
<CreateFolder />
<RemoveFile Id='CleanUpBackup' Name='PlugIn.dll' On='uninstall' />
</Component>
</Directory>

Note how I avoided overwriting files in the "Component" elements. I do that using CustomAction instead, both when installing my plug-in and when restoring the old one.

Something that's missing are rollback actions. There should be one for each deferred action, namely an action removing the xcopy-ed file. I don't know of any standard program to remove files on Windows, and I'd rather not write one myself. Where is "rm"?

UPDATE:

WiX experts are probably shaking their heads when they read this code:

<Custom Action='RestorePlugIn' Before='RemoveFiles'>Installed</Custom>
</InstallExecuteSequence>

While it does do what I intended when the user removes the software, it is also executed when users perform other actions than install or uninstall, such as repair an installation. As a result, an attempt to repair an installation will restore the old plug-in, which of course is more likely to destroy the installed software...

WiX, because we can.

2009-07-01T10:50:00.000-07:00

For today's post, I thought I might write on something that's not directly related to F#. Instead, this article deals with WiX, a piece software intended to help creating installers. WiX and F# do share their approach to writing programs, though, namely the declarative way.

First, I must say I am no expert in installers. I have built a couple rpm packages on Linux, and found the experience OK, but not particularly enjoyable. I have also used NullSoft Scriptable Install System (NSIS for short) for top10, and gave up with it. My main gripe is that NSIS is really more a scripting language, and not a particularly good one at that. I don't think it's worse than the other install systems out there, though I haven't tried them all. I did try WISE, for instance, but failed to install it. Now, that's irony...

The problem is that these tools try to solve the problem using a procedural approach. The programmer has to specify what to do during an installation, which typically includes copying files on the hard disk, setting up a few shortcuts, messing up with the registry. Specifying all this is a tedious task, but it's not even half the job. One must also specify what to do when the user decides to uninstall the software. Typically, this means clearing up the mess in the registry, removing the shortcuts, deleting files.

Obviously, it should be possible to deduce the uninstallation process from the installation process. It's not just a matter of convenience, but of correctness.

WiX attracted a bit of attention when it came out, being Open Source software produced by Microsoft. Another side of it worth of interest is that it uses a declarative approach to specifying installation procedures. Instead of writing the sequence of operations needed to (un)install software, one specifies what to install, and where. Which is the way it should be.

As attractive as it seems to be, I must say I am disappointed. The three full days of experimenting I have spent on WiX have been rather painful.

The first issue is that WiX is based on Windows Installer, a.k.a MSI, whose documentation is pretty hard to grasp for a newcomer. Part of the problem resides in the core design choices, which seem genuinely weird to me. An MSI installer is not a program, it's a database, which contains a description of a workflow, where the actions make up the installation procedure. Now, installations a probably some of the most linear processes one can think of, meaning workflows are complete overkill. Why one would use a database to store a workflow is another mystery.

WiX attempts to hide these layers of insanity. All you need to do to copy a file on the system is specify which file you want to copy, and where. WiX takes care of generating the code to undo the copy if it fails, as well as the code to remove the file when uninstalling.

Sadly, WiX only goes halfway. If your installation process happens to write over an existing file, the uninstallation process won't restore the original file. This must be handled manually, and requires a decent understanding of MSI, its workflows, custom actions and databases.

What's worse, WiX adds another layer of wickedness of its own, namely XML. That was probably the only technology missing in the stack...

In case you urgently need a headache, I suggest you go have a look at Suggested InstallExecuteSequence, which is the sequence of actions one should take to install software. That's 60 of them, no less. If that sounds like a lot, well it is. The catch is that the same sequence is used for uninstallation. Approximately half of these actions are active when installing, the other half being active while uninstalling. The question that immediately pops up is "why not use two separate sequences"? But then, one would not need conditions, such a shame...

XNA asteroid clone aborted

2009-05-20T02:24:00.000-07:00

I have decided to abort my attempt to write a 3d asteroids clone for the XBox 360. As, there already are quite a few 2d clones of the original Asteroids, I had decided to make a 3d version. The problem, as I pointed in an earlier post, is that one needs a considerably larger number of asteroids to make the game interesting. The magic number here seems to be 1000 asteroids.

I wanted collision response between asteroids. Doing collision detection is quadratic in the number of objects, unless one uses space partitioning. My experiments showed that the naive way (without space partitioning) works fine for 100 asteroids, but does not scale up.

I implemented an octree data structure to speed things up. The idea here is to partition space in boxes of varying size, where each box contains at most about 10 asteroids. Collision detection can then be done on groups of 10 asteroids.

The optimization worked fine when the game was run on the PC, but not on the XBox. The game run at 60 fps on the PC, with noticeable "hickups" every few seconds though. The game run at less than 10 fps on the XBox.

The culprit is the gargabe collector on the XBox. When looking on the net, one finds that the suggested solution is to minimize the number of live objects, which involves using structs. Unfortunately, most of the nice constructs of F#, such as discriminated unions and records, are translated to classes. Replacing these by structs is feasible, but it's not a very pleasant experience.

I also feel that I do not want to invest time developing skills to avoid garbage collection when the correct solution is to fix the garbage collector on XBox.

That does not mean I am giving up on XNA and the XBox, but I will have to find other computationally easier projects.

Race condition in "First obstacles and solutions"

2009-04-12T01:16:00.000-07:00

I fixed a bug in my asteroids clone yesterday which turned out to be a race condition. The problem was in map_parallel:

let map_parallel (func : 'a -> 'b) (items : 'a[]) =
let results = Array.zero_create (items.Length)
let count = ref items.Length
use notify = new System.Threading.AutoResetEvent(false)

items
|> Array.iteri (
fun i item ->
System.Threading.ThreadPool.QueueUserWorkItem (
fun _ ->
let res = func item
results.[i] <- res
!: System.Threading.Interlocked.Decrement count |> ignore
!: if !count = 0 then notify.Set() |> ignore
) |> ignore
)
notify.WaitOne() |> ignore
results

I have marked the two faulty lines in the code above with "!:". The (hopefully) correct version is:

let c = System.Threading.Interlocked.Decrement count
if c = 0 then notify.Set() |> ignore

In the faulty version, it is possible for two threads to execute "then notify.Set()". The second thread may then raise an exception as "notify" may already have been disposed of.

The code in the original post was corrected.

Structs that look like records

2009-03-29T14:16:00.000-07:00

I've spent some time trying to improve my asteroids clone in F# for the XBox360. I present the first results in this post.

But first, some non-technical considerations. Microsoft has now made available to XNA creators (i.e. game programmers) the download statistics of their games. A vast majority of creators seem disappointed, but I think that's more a sign of too high expectations than a failure of the platform itself.
One of the creators reported that full game downloads went down when Microsoft raised the time limit in trial versions from 4 minutes to 8 minutes. Players have the ability to download a trial version of an XBox Live Community Game before buying the full version. Trial versions typically have some features disabled (this is up to the game creator) and a mandatory time limit (which cannot be controlled by game creators).
What happened there, apparently, is that the game is played in short sessions shorter than 8 minutes at a time, making the free trial version sufficiently appealing that gamers did not feel a need to buy the full version.

Asteroids is not typically a game you play for long periods at a time, so I expect my game may suffer the same problem.

Back to the technical side of things. I found a way to make structs look like records. Here is the declaration:


type State =
    struct
        val props : Properties
        val pos : Vector3
        val speed : Vector3
        val impulses : Vector3
        val force : Vector3
        
        new (props, pos, speed, impulses, force) = 
            { props = props ;
              pos      = pos ;
              speed    = speed ;
              impulses = impulses ;
              force    = force }
        
        static member inline Default (props, ?pos, ?speed, ?impulses, ?force) =
            State(
                props,
                pos = defaultArg pos Vector3.Zero,
                speed = defaultArg speed Vector3.Zero,
                impulses = defaultArg impulses Vector3.Zero,
                force = defaultArg force Vector3.Zero)
                
        member inline x.Clone (?pos, ?speed, ?impulses, ?force) =
            new State (
              x.props,
              pos      = defaultArg pos      x.pos,
              speed    = defaultArg speed    x.speed,
              impulses = defaultArg impulses x.impulses,
              force    = defaultArg force    x.force )

... and here is how it's used:


        member x.ApplyCenterForce (v : Vector3) =
            let force = x.force + v 
            x.Clone (force = force)

This is very similar to the old code:


let applyCenterForce (v : Vector3) (x : State) =
    let force = x.force + v
    { x with force = force }

Looking back at the first snipplet, notice how I declared "x.Clone":


        static member inline Default (props, ?pos, ?speed, ?impulses, ?force) =

The question marks before the arguments mean that these arguments are optional. If the caller does not provide them, they automatically get the "None" value.


            new State (
              x.props,
              pos      = defaultArg pos      x.pos,
              speed    = defaultArg speed    x.speed,
              impulses = defaultArg impulses x.impulses,
              force    = defaultArg force    x.force )

"defaultArg" is a convenience F# standard function which returns the first value unless it's "None", in which case the second value is returned.

The function was declared "inline" to avoid creating lots of "Option" objects at call sites. For instance, the disassembled version of "ApplyCenterForce" looks like this:


public HeavyObject.State ApplyCenterForce(Vector3 v)
{
    return new HeavyObject.State(this._props, this._pos, this._speed, this._impulses, this._force + v);
}

Compare with the version without "inline":


public HeavyObject.State ApplyCenterForce(Vector3 v)
{
    Vector3 vector = this._force + v;
    return this.Clone(null, null, null, new Option(vector));
}

As the entire point with structs is to avoid allocating objects on the heap, having an "Option" created for each call to ApplyCenterForce is not quite acceptable.

It's not clear that using structs is a clear win in all situations. Performance on the PC is negatively affected, as garbage collection is almost free there, whereas copying structs when passing them as parameters to functions isn't. Performance on the XBox360, however, is improved, as garbage collection is kept under control.

First obstacles and solutions

2009-03-25T15:02:00.000-07:00

I've got forward with my asteroids clone on the XBox 360 using XNA, and I started noticing a few issues, not all technical.

First, a 3d space is mostly empty. I did not realize the probability of being hit by an asteroid is pretty low. In order to make the game somewhat interesting, I need a good 1k asteroids in a 100m x 100m x 100m cube. I doubt any player will have the patience and perseverance to shoot each of these 1000 asteroids. I have ideas about solving that problem, but I'm not sure which one to pick yet.

Regarding performance, the game initially ran fine with 100 asteroids, but as I say above, I will need 10 times that amount. The initial bottleneck was collision detection, which was quadratic. I solved this on the PC using space partitioning with an octree.


#light

open Microsoft.Xna.Framework
open System.Collections.Generic

type NodeData<'a> =
    { bbox : BoundingBox ;
      sub_nodes : Node<'a> [] }
      
and Node<'a> =
    | Leaf of BoundingBox * 'a []
    | Node of NodeData<'a>


let mkBBox (p1 : Vector3) (p2 : Vector3) =
    let x1, x2 =
        if p1.X < p2.X then (p1.X, p2.X) else (p2.X, p1.X)
    let y1, y2 =
        if p1.Y < p2.Y then (p1.Y, p2.Y) else (p2.Y, p1.Y)
    let z1, z2 =
        if p1.Z < p2.Z then (p1.Z, p2.Z) else (p2.Z, p1.Z)
    
    BoundingBox (Vector3 (x1, y1, z1), Vector3 (x2, y2, z2))


let map_parallel (func : 'a -> 'b) (items : 'a[]) =
    let results = Array.zero_create (items.Length)
    let count = ref items.Length
    use notify = new System.Threading.AutoResetEvent(false)
    
    items
    |> Array.iteri (
        fun i item ->
            System.Threading.ThreadPool.QueueUserWorkItem (
                fun _ ->
                    let res = func item
                    results.[i] <- res
                    let c = System.Threading.Interlocked.Decrement count
                    if c = 0 then notify.Set() |> ignore
            ) |> ignore
        )
    notify.WaitOne() |> ignore
    results

    
let rec partition (count_limit) (intersect) (items : 'a []) (bbox : BoundingBox) multi_threaded =
    if items.Length < count_limit
    then
        (bbox, items) |> Leaf
    else
        let in_bbox =
            items
            |> Array.filter (fun item -> intersect item bbox)

        let center = 0.5f * (bbox.Min + bbox.Max)
        let pts = bbox.GetCorners ()

        let sub_nodes =
            pts
            |> (if multi_threaded then map_parallel else Array.map) (
                fun pt ->
                    let sub_box = mkBBox center pt
                    partition count_limit intersect in_bbox sub_box false
                )

        { bbox = bbox ;
          sub_nodes = sub_nodes }
        |> Node


let rec getVisible (view : BoundingFrustum) addVisible (partition : Node<'a>) =
    match partition with
    | Leaf (bbox, items) ->
        if bbox.Intersects (view)
        then
            items |> Array.iter addVisible
    | Node data ->
        if data.bbox.Intersects (view)
        then
            data.sub_nodes
            |> Array.iter (getVisible view addVisible)

It's pretty rough code, but there are some interesting bits anyway. In "partition", the function creating the octree, I use multithreading in the top call in an attempt to take advantage of the multiple cores. My timings on the PC show however little global benefit in using multithreading, but I don't know how much "partition" contributes to the overall execution time. It's too early to draw any conclusion, but at least performance is not negatively affected.

Note that I reimplemented map_parallel (which I had introduced in an earlier Tutorial about concurrency) without using asynchronous computations. It's obviously inferior to the older version as it does not handle exceptions, but it has the advantage of actually working on both the PC and the XBox360. The older version causes an "error code 4" on the XBox. I don't know why, I'll try to report that on hubfs with a smaller test case as soon as I get time.

The octree made the PC version run nicely with 1000 asteroids and more, but the XBox360 is still running very slowly, which makes me think that I have finally hit the limitations of its garbage collector. Note that I have not verified that, not being very comfortable with the development kit yet.

Currently, each asteroid is represented using a record, and records get translated to classes by the F# compiler. The records are stored in an array. I wonder if it would work better with structs instead, the idea being that an array of structs should be seen as one object, whereas an array of classes is composed of 1001 objects in this case. As the performance of garbage collection is dependent on the number of objects, but not so much on their size, an array of struct should offer better performance.

The sad thing is that I really liked records, I wish F# allowed the [<Struct>] attribute on records.

F# game running on the console

2009-03-14T10:47:00.000-07:00

I have just succeeded to write and run my first game on my XBox360. Here is proof of it:

The game is composed of an F# library and a top-level C# application. The game, a 3d clone of Asteroids, is still very far from being complete. For instance controls require a keyboard, and the code is still riddled with bugs. Never the less, the first attempt to deploy on the XBox was successful, which is quite encouraging. See Grammerjack's old blog for details on each step of the deployment process.

The F# code is written in a pure functional way, which I fear is not going to work out in the end. Such code relies heavily on the garbage collector, and the current version of the XBox360 .NET environment is known to be weak on this point.

I wonder if it's possible to modify the .NET code emitted by the F# compiler to replace instantiations of new objects by references to items in pre-allocated arrays. This would make it possible to keep purity in the F# source code while maintaining decent performance.
Right now, I feel that if I was to write code relying heavily on in-place modifications, I would rather do that in C# than in F#.

Parsing DirectX .X files

2008-12-26T06:36:00.000-08:00

This has been by far the most demanding episode to write in these series of tutorials, but finally it's there. See http://code.google.com/p/fs-gamedev/wiki/Tutorial10 for the text and source code.

This tutorial shows how to parse .X files, which are used for 3d models and scenes. Note that DirectX offers convenient functions to manipulate these files, meaning that the practical usefulness of the code in this tutorial is limited, unless you don't have access to DirectX.

This tutorial demonstrates the following concepts:

* Discriminated unions and simple pattern matching
* Stateless lexing
* Hiding side effects in IO operations
* Error handling using the option type
* Defining mutually and self dependent types
* Building functions at run-time by combining basic functions

The content of this tutorial is significantly denser than usual. The really interesting part in my opinion resides however in the design decision to separate parsing in two stages. During the first stage, second-stage parsers are dynamically created by combining simple parsers (such as a semi-colon parser, an int parser, even a "zero" parser parsing nothing). Second-stage parsing simply consists of calling the result of first-stage parsing, which results in hierarchical data representing faces, lights and materials composing a 3d scene.

Situation update

2008-11-09T08:07:00.000-08:00

Tutorials
There has been little visible activity on the tutorials recently. That's because I have been busy implementing a small 3d object viewer. I have the somewhat unfortunate tendency to choose complexity over simplicity, which means that this viewer should be cross-platform. It is based on a generic scene-graph library and will support both DirectX (using SlimDX) and OpenGL (using the TAO framework).
It can display 3d objects stored in .X files, currently using the DirectX API. I have started a mini-project to write my own parser for it, as DirectX is limited to windows platforms.
I am starting to see the end of the tunnel, and the following tutorials should come soon:

- A generic scene graph library. It will demonstrate the use of some of F# objected-oriented constructs. It will also show how to use SlimDX with F#, which you can already see in snk_kid's examples.

- A parser for .X files. Writing this code proved more challenging than expected: .X files start by defining the data structures that are used later in the file to describe the data. See e.g. Direct-X File Format. This is a flexible but unusual approach: Data structures are normally fixed from file to file, and parsers can be written with this knowledge at hand. I found an elegant solution using a functional approach: The data structure declarations are parsed, generating new data parsers, which are used later when parsing the data itself.

XNA
I am staying clear of XNA for the time being. It would seem that my dream of getting my racing game to run on the XBox360 is not realizable, as the CLR on the XBox360 is notably slow when it comes to computations on floats, which are hardly avoidable in physics simulations.

Mono and games
Regarding performance and games, it seems Mono is overtaking Microsoft's CLR. Miguel de Icaza has announced that Mono now has experimental support for SIMD instructions. My racing game is currently implemented in C++, but does not take advantage of SIMD instructions. I am hopeful that a new clean implementation of my physics engine in F# may actually be faster than the current C++ one.

Tutorials moving to Google code

2008-10-24T12:11:00.000-07:00

From now on, I will use the wiki on the Google code project for the tutorials. This has the advantage that readers will be able to see the history of corrections. Another good thing is that the wiki supports syntax highlighting. Blogger's software does not seem especially fit for posting code.

I think I will continue to use this blog for my thoughts and opinions about game programming and F#.

Tutorial 11b: Efficient generic programming

2008-10-19T12:48:00.000-07:00

Specialization is a programming technique used to improve the performance of generic code. It consists of specifying specific implementations for one or several specific instantiations of generic code.

Specialization using pattern matching

The "runge_kutta_4" function shown in these tutorials contains the following lines:

old + (1.0/6.0) * (v1 + 2.0 * (v2 + v3) + v4)

This is fine when dealing with floats, but with 3-dimensional vectors and larger types, it may be excessively slow due to the large amounts of intermediate values produced. Indeed, this code is the same as:

tmp1 = v2 + v3
tmp2 = 2.0 * tmp1
tmp3 = tmp2 + v4
tmp5 = v1 + tmp3
tmp6 = 1.0 / 6.0
tmp7 = tmp6 * tmp5
old + tmp7

Of these 7 intermediate values, 6 could be replaced by one.

What if we had a function to add 6 vectors creating only one value, the final result?

let add6 ((v0: Vec3d), (v1: Vec3d), (v2: Vec3d), (v3: Vec3d), (v4: Vec3d), (v5: Vec3d)) =
let x = v0.x + v1.x + v2.x + v3.x + v4.x + v5.x
let y = v0.y + v1.y + v2.y + v3.y + v4.y + v5.y
let z = v0.z + v1.z + v2.z + v3.z + v4.z + v5.z

Vec3d(x, y ,z)

Admittedly, it's not very pretty, and it would be nice if the user of "runge_kutta_4" was not forced to provide such a function.

F# has a parametric type called "option" useful to represent this kind of optional values. The C++ counter-part is to use a pointer, and let the null value denote the case when no value is provided.

The dictionary of operations is modified as follows:

type VecOps<'vector, 'scalar> = {
up: 'vector
add: 'vector * 'vector -> 'vector
add6: Add6<'vector> option
scale: 'scalar * 'vector -> 'vector
}

(By the way, another equivalent way of writing the declaration of add6 would be

add6: 'vector Add6 option

)

An instance of the dictionary using add6 is created as follows:

let Vec3d_ops = {
add = plus_Vec3d;
scale = scale_Vec3d;
add6 = Some add6;
up = Vec3d(1.0)
}

Or, to leave out add6:

let Vec3d_ops = {
add = plus_Vec3d;
scale = scale_Vec3d;
add6 = None;
up = Vec3d(1.0)
}

The last part of the "runge_kutta_4" function is modified to check if the dictionary of operations contains an "add6":

match vec_ops.add6 with
// No addMany available, use pair-wise additions (will create many intermediate vectors).
| None ->
old + (1.0/6.0) * (v1 + 2.0 * (v2 + v3) + v4)
// addMany available, use it.
| Some add ->
let tmp = add (v1, v2, v2, v3, v3, v4)
old + (1.0/6.0) * tmp

This is a new F# construct, called "pattern-matching". Basically, it means:

"Check the value of vec_ops.add6. If it is equal to None, then do the sum the usual way. otherwise, if the value of vec_ops.add6 is of the form Some add, then do the some by using 'add'".

I think pattern matching is a very nice construct. It allows you to match a value with fairly complex expressions called patterns. I won't dig deeper into patterns yet, let me just say that even though they look complex, the code generated by the compiler is as optimized as possible.

Optimization troubles

Unfortunately, not everything runs as fine as I had hoped. If I look at the generated code, I see that the optimizations that the F# compiler performed in the first part of Tutorial 11 have now disappeared. The problem seems to be that the compiler no longer sees through the record used for the dictionary of operations, and is therefore unable to inline the addition and scale operations. It is also unable to see if vec_ops.add6 is constantly "None" or if it has a constant function value.

As it turns out, the problem has nothing to do with pattern matching. Indeed, if I removed the "up" field from the record, or if use multiple parameters instead of a record, the generated code looks very nice, as shown below.

When an "add6" function is provided:

When no "add6" function is provided:

Was it worth it?
I get a 25% performance boost thanks to "add6" when using 3d vectors. On the other hand, I get a 65% performance drop when summing floats. This seems to be a clear case where tailoring generic code to specific types really helps to achieve the best performance.
There is a link to the full code available at the bottom of this page, if you want to try it out for yourself. I have made an habit of messing up my benchmark measurements, so don't take my word!

Conclusion

Time to conclude the part of these Tutorials dedicated to generic programming and low-level optimization.

To summarize:
1) Make sure your computations on floats are correct. NaN values kill performance.
2) Avoid curried functions when performance is critical, especially for methods.
3) Inline generic functions to avoid indirect calls to operations. However, do not take the habit of inlining all small functions. The compiler or the CLR do that for you.
4) Keep dictionaries of operations small, or avoid them altogether. Alternatives include static type constraints, shown in Tutorial 9, or function parameters.

Regarding item 4), I hope this is a problem that will be fixed in later releases of the F# compiler.

Source code
The complete source code used in this tutorial is available on google code (with comments, for a change).

Tutorial 11: Efficient generic programming

2008-10-15T13:05:00.000-07:00

In Tutorial 8 I introduced a method for generic programmings which uses so-called dictionaries of operations (see also pp 110-111 in Expert F#). I concluded the article with the following judgment:

I'll close this up with a comment on performance. To put things bluntly, it's terrible. I am not quite sure if I have done something wrong, so I won't post scary numbers (yet), but I would say this method is not usable for real time physics simulations.

Bug fix

Well, it turned out that (1) I did do something wrong, and (2) there was a lot of untapped optimization potential in this code.

Before I go deeper into optimization techniques, let me correct a bug in the code:

let spring (vec_ops: VecOps<'a, 'b>) stiff pos =
vec_ops.scale stiff pos

should have been

let spring (vec_ops: VecOps<'a, 'b>) stiff pos =
vec_ops.scale -stiff pos

Without the minus sign, the simulated system quickly gains so much energy that the positions fall out of range. Apparently, floating point computations involving NaNs are very slow.

Faster, but still slow

With that problem fixed, the program now runs with the following execution times:

1D (struct)
Single (min, max, avg): 17.296000 17.382000 17.330000
Multi (min, max, avg): 8.244000 8.591000 8.412000
Single (min, max, avg): 78.617000 80.769000 79.340333
Multi (min, max, avg): 41.145000 41.741000 41.362333
2D (struct)
Single (min, max, avg): 18.918000 19.332000 19.158667
Multi (min, max, avg): 10.107000 10.411000 10.300667
Single (min, max, avg): 108.103000 110.466000 109.122333
Multi (min, max, avg): 56.108000 58.272000 57.140667
3D (struct)
Single (min, max, avg): 23.440000 23.683000 23.553667
Multi (min, max, avg): 12.671000 15.129000 13.726667
Single (min, max, avg): 112.160000 114.022000 113.266333
Multi (min, max, avg): 60.331000 65.190000 63.192667

Note that integration using 3-dimensional vectors is only ~1.5 times slower than when using 1-dimensional vectors, which is unexpected. The computations alone should really be 3 times slower. Where does the difference come from?

The time for the 1-dimensional computation is roughly fp + ovh, where fp is the time spend doing additions and multiplications on floats, and ovh is the overhead, i.e. time spent in calling functions and allocating objects.
Then the time for the 3-dimensional computation should be 3fp + ovh. For the sake of simplicity I'm assuming the overhead does not depend on the type of vector involved.
I've done the math for single-threaded RK4, and it turns out that the overhead time is about 78% of the total execution time.

It should be possible to do better, especially if we look at the performance of the code in Tutorial 9. Personally, I prefer the code in Tutorial 8, and would be glad if I could bring down the execution time to comparable levels.

Optimizations

A common (and valuable) advice on optimization techniques is to profile the code, using e.g. NProf. In the present case, however, NProf did not tell me anything I did not know.
At this point, .NET reflector comes in handy as it allows one to look at the generated IL code.

Let us look at the code for "ef_Vec1d", the Euler integration function using 1-dimensional vectors. It's not trivial to find, there is a bit of detective work to do. In the code for "_main", we find:

ef_Vec1d is a partially evaluated function, which is compiled into an object mimicking a function. This kind of object holds the evaluated parameters as data members and has an "Invoke" method which is the function itself.
There is a bit of overhead associated to partially evaluated functions, which means one should avoid them in performance critical sections of the code.
If we look at "clo@64_1", we will see that it lacks any data member. Moreover, the "Invoke" method contains:

Notice how the compiler is accessing Vec1D_ops directly, instead of using a data member or a function parameter. Would it be possible to get the compiler to do the same kind of optimization inside "euler_implicit"? In order for this to be possible, "euler_implicit" must be declared "inline". The new "clo@64" becomes:

The generated code is starting to be hard to read, but we can see that the body of "euler_implicit" was indeed inlined, and is now using Vec1D_ops directly. That is a nice optimization, but it would be better if the compiler had gone further and called "Vec1d.scale" directly. It might have even inlined "Vec1d.scale", as this method is very short.
What can we do to help the compiler do that? I had to take a guess here, but I suspected using a record for VecOps instead of a class could be a good idea.

That was a pretty good intuition. For some reason, classes prevent the F# compiler to "see through" them and remove them during optimization. Records, on the other hand, can be removed.

This piece of code, which is much more easily readable than the previous one, exposes a new problem:

Note that "plus" is not a function of two Vec1d returning a Vec1d. What it really is is a function of a single Vec1d, returning a FastFunc, which is itself an object mimicking a function. Every time "plus" is called, a new function object is created, which is a bad thing, performance wise. Happily, the solution is easy: Change the signature of plus to take two Vec1d and return a Vec1d. Instead of Vec1d -> Vec1d -> Vec1d

we want (Vec1d * Vec1d) -> Vec1d:

After applying the same change to "scale", we get the following performance:

1D (struct)
Single (min, max, avg): 1.959000 1.971000 1.964667
Multi (min, max, avg): 0.990000 1.004000 0.995000
Single (min, max, avg): 9.463000 9.509000 9.479667
Multi (min, max, avg): 4.939000 5.023000 4.975667
2D (struct)
Single (min, max, avg): 3.485000 3.522000 3.507333
Multi (min, max, avg): 1.783000 1.814000 1.794667
Single (min, max, avg): 20.306000 20.692000 20.468333
Multi (min, max, avg): 10.557000 10.657000 10.593000
3D (struct)
Single (min, max, avg): 6.089000 6.127000 6.104667
Multi (min, max, avg): 3.073000 3.201000 3.152333
Single (min, max, avg): 32.570000 32.616000 32.597333
Multi (min, max, avg): 16.424000 16.784000 16.657667
3D (record)
Single (min, max, avg): 6.910000 6.958000 6.940667
Multi (min, max, avg): 3.530000 3.575000 3.554667
Single (min, max, avg): 33.879000 34.373000 34.065000
Multi (min, max, avg): 17.662000 17.843000 17.758667

That was quite a performance improvement, wasn't it?
I have also implemented a 3d vector type using a record instead of a struct, in case it might magically improve performance. As you can see, it did not, there is no real difference with the struct.

These numbers could certainly be improved further by using the techniques described in Tutorial 7, but I'll stop here for now.

Complete source code

For the complete source code of the optimized version, see revision 8

To compare the changes with the code from Tutorial 8, see the diff.

Source code on Google code

2008-10-10T11:42:00.000-07:00

Just a quick note to announce that I have created a google code project to host the source code used in this blog.
I have not yet added all tutorials, but the seven first are already there.

Tutorial 10: Generic programming using quotations

2008-09-27T02:17:00.000-07:00

The code for this tutorial comes in several files.
First: GenericPhysics.fs

#light

open System
open Microsoft.FSharp.Linq.QuotationEvaluation

#nowarn "57"

type ps<'Vec> = class
val pos:'Vec
val speed:'Vec
new(pos, speed) = { pos = pos; speed = speed }
end

type sa<'Vec> = class
val speed:'Vec
val accel:'Vec
new(speed, accel) = { speed = speed; accel = accel }
end

let mk_gravity scale_func (up: 'Vec): 'Vec =
let q =
<@
let (*) = %scale_func in -9.81 * up
@>
q.Eval()

let mk_spring scale_func: float -> 'Vec -> 'Vec =
let q =
<@
let (*) = %scale_func in fun k v -> -k * v
@>
q.Eval()

let mk_drag scale_func: float -> 'Vec -> 'Vec =
let q =
<@
let (*) = %scale_func in fun k v -> -k * v
@>
q.Eval()

let mk_euler_implicit plus_func scale_func =
let q =
<@
let (+) = %plus_func in
let (*) = %scale_func in
fun accel_func pos speed delta ->
let speed2 = speed + delta * (accel_func pos speed)
let pos2 = pos + delta * speed2
ps<_>(pos2, speed2)
@>
q.Eval()

let inline adapt (f: 'Vec -> 'Vec -> 'Vec) =
fun pos speed ->
let accel = f pos speed in
sa<_>(speed, accel)

let mk_rk4_q plus_func scale_func =
<@
fun deriv_func pos speed delta ->
let pf = %plus_func
let sf = %scale_func

let extrapolate x delta dx =
pf x (sf delta dx)

let half_delta = 0.5 * delta

let sa1: sa<_> = deriv_func pos speed
let sa2 = deriv_func (extrapolate pos half_delta sa1.speed) (extrapolate speed half_delta sa1.accel)
let sa3 = deriv_func (extrapolate pos half_delta sa2.speed) (extrapolate speed half_delta sa2.accel)
let sa4 = deriv_func (extrapolate pos delta sa3.speed) (extrapolate speed delta sa3.accel)

let sixth_delta = delta / 6.0

let update old v1 v2 v3 v4 =
pf old (sf sixth_delta
(pf v1
(pf v2
(pf v2
(pf v3
(pf v3
v4))))))

let pos1 = update pos sa1.speed sa2.speed sa3.speed sa4.speed
let speed1 = update speed sa1.accel sa2.accel sa3.accel sa4.accel

ps<'Vec>(pos1, speed1)
@>

let mk_rk4 plus_func scale_func =
let q = mk_rk4_q plus_func scale_func
q.Eval()

let simulate intg_func (t0: float) t_fin delta pos0 speed0 =
let rec repeat t0 pos0 speed0 =
if t0 > t_fin then (pos0, speed0)
else
let t1 = t0 + delta
let ps: ps<_> = intg_func pos0 speed0 delta
repeat t1 ps.pos ps.speed
repeat t0 pos0 speed0

Second file: FloatPhysics.fs

#light

let gravity = GenericPhysics.mk_gravity <@ fun x y -> x * y @> 1.0
let drag = GenericPhysics.mk_drag <@ fun x y -> x * y @>
let spring = GenericPhysics.mk_spring <@ fun x y -> x * y @>
let rk4 = GenericPhysics.mk_rk4 <@ fun x y -> x + y @> <@ fun x y -> x * y @>
let euler = GenericPhysics.mk_euler_implicit <@ fun x (y:float) -> x + y @> <@ fun x y -> x * y @>

Third file: Util.fs

Last file: Main.fs

#light

open System
open FloatPhysics
open Util

let inline accel pos speed =
drag 1.0 speed + spring 100.0 pos + gravity

let ef = (FloatPhysics.euler accel)
let rk4f = (rk4 (GenericPhysics.adapt accel))

let run euler_func s0 =
let t0 = 0.0
let t_fin = 1000.0
let delta = 0.005

let run_timed map_func =
let n_runs = 2
let times =
[
for i in 1..n_runs ->
let (run_time, res) =
run_time_func (fun () ->
s0 |> map_func(fun (x, y) ->
GenericPhysics.simulate euler_func t0 t_fin delta x y))
run_time
]

let max = Seq.max times
let min = Seq.min times
let avg = (Seq.fold (fun x y -> x+y) 0.0 times) / float n_runs
(min, max, avg)

let single_min, single_max, single_avg = run_timed List.map
let multi_min, multi_max, multi_avg = run_timed map_parallel

printfn "Single (min, max, avg): %f %f %f" single_min single_max single_avg
printfn "Multi (min, max, avg): %f %f %f" multi_min multi_max multi_avg

let n_bodies = 2

let s0_float = [ for s in 1..n_bodies -> (float s, 0.0) ]
run ef s0_float
run rk4f s0_float

ignore(Console.ReadKey(true))

If you want to compile these sources using Visual Studio, you need to know that the order in which the files appear in the project is important. If a file B uses types or values from a file A, then A must be placed higher in the list of files of the project.

You will also need to add references to the following DLLs: FSharp.PowerPack and FSharp.PowerPack.Linq.

Let us now take a deeper look at the new features of F# used in the code.

open Microsoft.FSharp.Linq.QuotationEvaluation

#nowarn "57"

The main item of this Tutorial is quotations. These represent pieces of code which can be constructed at compile time, changed dynamically at run time, and recompiled and executed dynamically. This last part is still experimental, and requires the use of a specific module.
The "#nowarn" directives tells the compiler not to warn us about this feature being experimental.

let mk_gravity scale_func (up: 'Vec): 'Vec =
let q =
<@
let (*) = %scale_func in -9.81 * up
@>
q.Eval()

The interesting piece here is the part between <@ and @>. The entire thing is called a quotation. It must contain a valid segment of F# code. The F# compiler will parse the code in this quotation, and build an object representing this code. More precisely, the compiler will generate an abstract syntax tree (AST). Note that this object does not in itself constitute executable code.
You may be wondering what "%scale_func" means in this context. The "%" operator specifies that another AST should be inserted there. "scale_func" is the variable which should contain the AST to insert.
To clarify this, look at the call to mk_gravity in FloatPhysics.fs:

let gravity = GenericPhysics.mk_gravity <@ fun x y -> x * y @> 1.0

The resulting quotation would therefore look as follows:

<@
let (*) = fun x y -> x * y in -9.81 * up
@>

which is has the same effect as:

<@
-9.81 * up
@>

An AST generated from a quotation can be compiled using method "Compile", or compiled and executed using method "Eval".
Had I written "q.Eval()" instead, "mk_gravity" would have returned a value of type "unit -> 'Vec", i.e. a function taking no argument and returning a vector when called. We may just as well returned the vector directly, which we can do by using method "Eval" instead.

If we take a step back and look at what we have just achieved, we will see that we have constructed a rather complicated way of perform the product of a vector by a scalar.

Let us look at the next function for a more interesting example.

let mk_spring scale_func: float -> 'Vec -> 'Vec =
let q =
<@
let (*) = %scale_func in fun k v -> -k * v
@>
q.Eval()

While I wrote this code I repeatedly found myself wondering "What did I just write?". Happily, the compiler can answer that question.This function takes an AST which should represent a function taking a float and a vector (in curried form) and returning a vector. The "mk_spring" function will then return a function taking a float and a vector and returning a vector. In other words, it will "unquote" the quotation, which is simply done by evaluating the AST. Before doing so, it inserts the quoted form of the function performing the product of a vector by a scalar into q, which in the present case has the same effect as:

<@
let (*) = fun x y -> x * y in fun k v -> -k * v
@>

Or in simpler terms:

<@
-k * v
@>

We have found yet another way to perform the product of a vector (which is actually a float in this simple example) by a scalar (another float, but not to be mistaken with the vector). The "mk_spring" function differs from "mk_gravity" in the way that its parameters are expected to vary. Gravity is assumed to be constant, and so is the upward direction, denoted by the "up" parameter of "mk_gravity". The stiffness coefficient and the position of the body, on the other hand, change across calls.

Using quotations to achieve genericity can be seen as some kind of hybrid between the functional approach described in Tutorial 8 and the approach based on static constraints of Tutorial 9. It shares with Tutorial 8 its use of function parameters to specify the implementation of operations on vectors. It share with Tutorial 9 its way of emitting specific code for each concrete type of vector.

I had hoped this would result in more efficient code, but that is unfortunately not currently the case. The quotation evaluation functionality is still experimental, and it may be possible that future versions of F# might produce faster code.

Update
I've come across an entry in Jomo Fisher's blog about Linq which makes me wonder if my code is really right. Jomo has used Linq in a setting where performance is truly impressive. Why I am getting such bad results here? Further investigation needed...
End of Update

The point of the approach described here is not so much what it achieves, but what possibilities it opens. For instance, it is possible to implement aggressive optimization techniques that the F# compiler will probably never support, such as rearranging code to avoid creating objects for intermediate values, or turning pure computations into computations with local side effects. Obviously, it would not be realistic to support all features of F#, but a subset dedicated to computations would probably suffice. Using Quotations.Expr from F# and Reflection.Emit from .NET, it seems very feasible to write a specialized optimizing compiler for a subset of F#.
Other interesting potential uses of quotations for games include programs to run on the GPU (shaders), or on any other kind of peripheral, for that matter (game controllers, head-on displays...).

Updated C++ version

2008-09-24T13:18:00.000-07:00

This is the C++ version of the integrator, updated to use vectors.

UPDATE: Bug fixes. Funny how non-explicit single-argument constructors can hide errors in your code...

// RK++NET.cpp : main project file.

#include "stdafx.h"
#include <windows.h>

#include <map>
#include <vector>
#include <iostream>

const double gravity = -9.81;

template<typename T>
inline
T spring(const T& pos)
{
return -100.0 * pos;
}

template<typename T>
inline
T drag(double k, const T& pos)
{
return -k * pos;
}

template<typename A>
class EulerImplicit
{
public:
EulerImplicit(const A& accel):
accel(accel)
{
}

template<typename T>
inline
void operator()(T& pos, T& speed, const double delta) const
{
speed += delta * accel(pos, speed);
pos += delta * speed;
}

private:
const A& accel;
};

template<typename A>
class RK4
{
public:
RK4(const A& accel):
accel(accel)
{
}

template<typename T>
inline
void operator()(T& pos, T& speed, const double delta) const
{
const double half_delta = 0.5 * delta;

std::pair<T, T> k1 = accel(pos, speed);
std::pair<T, T> k2 = accel(pos + half_delta * k1.first, speed + half_delta * k1.second);
std::pair<T, T> k3 = accel(pos + half_delta * k2.first, speed + half_delta * k2.second);
std::pair<T, T> k4 = accel(pos + delta * k3.first, speed + delta * k3.second);

pos += delta / 6.0 * (k1.first + 2.0 * (k2.first + k3.first) + k4.first);
speed += delta / 6.0 * (k1.second + 2.0 * (k2.second + k3.second) + k4.second);
}

private:
const A& accel;
};

template<typename T>
class Force
{
public:
explicit Force(const T& up) : m_drag(1.0), m_gravity(gravity*up)
{
}

T operator()(const T& pos, const T& speed) const
{
return drag(m_drag, speed) + spring(pos) + m_gravity;
}

private:

const double m_drag;
T m_gravity;
};

template<typename A>
class Adapt
{
public:
Adapt(const A& accel):
accel(accel)
{
}

template<typename T>
inline std::pair<T, T> operator()(const T& pos, const T& speed) const
{
std::pair<T, T> ret;
ret.first = speed;
ret.second = accel(pos, speed);
return ret;
}

private:
const A& accel;
};

template<typename T, typename I>
inline
void simulate(const I& intg_func, T& pos, T& speed, double t0, const double t_fin, const double delta)
{
while(t0 < t_fin)
{
t0 += delta;
intg_func(pos, speed, delta);
}
}

template<int DIM>
class VecD
{
public:
VecD() {
for (int i=0; i<DIM; ++i)
vals[i] = 0.0;
}

explicit VecD(double v0, double v1=0.0, double v2=0.0)
{
if (DIM >= 1)
vals[0] = v0;

if (DIM >= 2)
vals[1] = v1;

if (DIM >= 3)
vals[2] = v2;

for (int i=3; i<DIM; ++i)
vals[i] = 0.0;
}

inline VecD<DIM> operator+=(const VecD<DIM>& other)
{
for (int i=0; i<DIM; ++i)
vals[i] += other.vals[i];
return *this;
}

inline VecD<DIM> operator+(const VecD<DIM>& other) const
{
VecD<DIM> tmp(*this);
return tmp += other;
}

public:
double vals[DIM];
};

template<int DIM>
inline
VecD<DIM>
operator*(double k, const VecD<DIM>& other)
{
VecD<DIM> ret(other);
for (int i=0; i<DIM; ++i)
ret.vals[i] *= k;
return ret;
}

typedef VecD<1> Vec1D;
typedef VecD<2> Vec2D;
typedef VecD<3> Vec3D;

void make_pos(int i, double& out) { out = (double)i; }
void make_pos(int i, Vec1D& out) { out = Vec1D((double) i); }
void make_pos(int i, Vec2D& out) { out = Vec2D(1.0, (double) i); }
void make_pos(int i, Vec3D& out) { out = Vec3D(1.0, (double) i, -1.0); }

void make_up(double &out) { out = 1.0; }
void make_up(Vec1D &out) { out = Vec1D(1.0); }
void make_up(Vec2D &out) { out = Vec2D(0.0, 1.0); }
void make_up(Vec3D &out) { out = Vec3D(0.0, 1.0, 0.0); }

template<typename Vec>
void run_sim(const char *descr)
{
typedef std::vector< std::pair<Vec, Vec> > Tuples;

std::cout << descr << std::endl;

const double t0 = 0.0;
const double t_fin = 1000.0;
const double delta = 0.005;
const int N_BODIES = 100;

Tuples initial_states;
initial_states.reserve(N_BODIES);
for (int i=0; i<N_BODIES; ++i)
{
Vec pos;
make_pos(i, pos);
initial_states.push_back( std::make_pair(pos, Vec(0.0)) );
}

double el = 0.0;
const int NRUNS=3;
for (int i=0; i<NRUNS; ++i)
{
Tuples states(initial_states);

Vec up;
make_up(up);
Force<Vec> accel(up);
EulerImplicit< Force<Vec> > euler(accel);
long int start0 = GetTickCount();
for (Tuples::iterator it = states.begin();
it != states.end();
++it)
{
simulate(euler, it->first, it->second, t0, t_fin, delta);
}
el += (GetTickCount() - start0) / 1000.0;
}
std::cout << "Time: " << el / NRUNS << "\n";
}

int main(int argc, char **argv)
{
run_sim<double>("double");
run_sim<Vec1D>("class 1D");
run_sim<Vec2D>("class 2D");
run_sim<Vec3D>("class 3D");

char c;
std::cin >> c;
return 0;
}

Tutorial 9: Generic programming using type constraints

2008-09-24T11:15:00.000-07:00

This Tutorial 9 shows a generic implementation of the integrator, based on type parameters.

#light

open System

let run_time_func (func: unit -> 'a) =
let watch = new System.Diagnostics.Stopwatch()
watch.Start()
let res = func ()
watch.Stop()
let diff0 = float watch.ElapsedMilliseconds / 1000.0
(diff0, res)

let map_parallel func items =
let tasks =
seq {
for i in items -> async {
return (func i)
}
}
Async.Run (Async.Parallel tasks)

type ps<'num> = struct
val pos:'num
val speed:'num
new(pos, speed) = { pos = pos; speed = speed }
end

type VecN =
One of float
| Two of float*float
| Three of float*float*float
with
static member inline plus (a: VecN) (b: VecN) =
match (a, b) with
| (One(v), One(w)) -> One(v+w)
| (Two(v0, v1), Two(w0, w1)) -> Two(v0 + w0, v1 + w1)
| (Three(v0, v1, v2), Three(w0, w1, w2)) -> Three(v0 + w0, v1 + w1, v2 + w2)
| _ -> failwith "Size mismatch"

static member inline scale (k: float) (a: VecN) =
match a with
| One(v) -> One(k * v)
| Two(v0, v1) -> Two(k * v0, k * v1)
| Three(v0, v1, v2) -> Three(k * v0, k * v1, k * v2)

type Vec1d = struct
val x: float

new (x) = { x = x }

static member inline plus (a: Vec1d) (b: Vec1d) = Vec1d(a.x + b.x)
static member inline scale (k: float) (a: Vec1d) = Vec1d(k * a.x)
end

type Vec2d = struct
val x: float
val y: float

new (x, y) = { x = x; y = y }

static member inline plus (a: Vec2d) (b: Vec2d) = Vec2d(a.x + b.x, a.y + b.y)
static member inline scale (k: float) (a: Vec2d) = Vec2d(k * a.x, k * a.y)
end

type Vec3d = struct
val x: float
val y: float
val z: float

new (x, y, z) = { x = x; y = y; z = z }

static member inline plus (a: Vec3d) (b: Vec3d) = Vec3d(a.x + b.x, a.y + b.y, a.z + b.z)
static member inline scale (k: float) (a: Vec3d) = Vec3d(k * a.x, k * a.y, k * a.z)
end

type CVec1d (x: float) = class
member v.X = x

static member inline plus (a: CVec1d) (b: CVec1d) = CVec1d(a.X + b.X)
static member inline scale (k: float) (a: CVec1d) = CVec1d(k * a.X)
end

type CVec2d (x: float, y:float) = class
member v.X = x
member v.Y = y

static member inline plus (a: CVec2d) (b: CVec2d) = CVec2d(a.X + b.X, a.Y + b.Y)
static member inline scale (k: float) (a: CVec2d) = CVec2d(k * a.X, k * a.Y)
end

type CVec3d (x: float, y: float, z: float) = class
member v.X = x
member v.Y = y
member v.Z = z

static member inline plus (a: CVec3d) (b: CVec3d) = CVec3d(a.X + b.X, a.Y + b.Y, a.Z + b.Z)
static member inline scale (k: float) (a: CVec3d) = CVec3d(k * a.X, k * a.Y, k * a.Z)
end

let gravity =
-9.81

let inline spring (pos: ^vec) =
let (*) k x = (^vec: (static member inline scale: float -> ^vec -> ^vec) k) x
let k = 100.0
-k * pos

let inline drag k (pos: ^speed) (speed: ^speed) =
let (*) k x = (^vec: (static member inline scale: float -> ^vec -> ^vec) k) x
-k * speed

let inline euler_implicit accel_func (pos: ^vec) (speed: ^vec) delta =
let (+) x y = (^vec: (static member inline plus: ^vec -> ^vec -> ^vec) x) y
let (*) k x = (^vec: (static member inline scale: float -> ^vec -> ^vec) k) x

let speed2 = speed + (delta * (accel_func pos speed))
let pos2 = pos + (delta * speed2)
ps<_>(pos2, speed2)

let inline simulate intg_func t0 t_fin delta pos0 speed0 =
let oc = OptimizedClosures.FastFunc3<_,_,_,_>.Adapt(intg_func)
let rec repeat t0 pos0 speed0 =
if t0 > t_fin then (pos0, speed0)
else
let t1 = t0 + delta
let ps: ps<_> = oc.Invoke(pos0, speed0, delta)
repeat t1 ps.pos ps.speed
repeat t0 pos0 speed0

let inline accel (up: ^vec) (pos: ^vec) (speed: ^vec) =
let (+) x y = (^vec: (static member inline plus: ^vec -> ^vec -> ^vec) x) y
let (*) k x = (^vec: (static member inline scale: float -> ^vec -> ^vec) k) x
(drag 1.0 pos speed) + (spring pos) + (gravity * up)

let run euler_func s0 =
let t0 = 0.0
let t_fin = 1000.0
let delta = 0.005

let run_timed map_func =
let n_runs = 3
let times =
[
for i in 1..n_runs ->
let (run_time, res) = run_time_func (fun () -> s0 |> map_func(fun (x, y) -> simulate euler_func t0 t_fin delta x y))
run_time
]

let max = Seq.max times
let min = Seq.min times
let avg = (Seq.fold (fun x y -> x+y) 0.0 times) / float n_runs
(min, max, avg)

let single_min, single_max, single_avg = run_timed List.map
let multi_min, multi_max, multi_avg = run_timed map_parallel

printfn "Single (min, max, avg): %f %f %f" single_min single_max single_avg
printfn "Multi (min, max, avg): %f %f %f" multi_min multi_max multi_avg

let n_bodies = 10

let s0_Vec1d = [ for s in 1..n_bodies -> (Vec1d(float s), Vec1d(0.0)) ]
let ef_Vec1d = euler_implicit (accel (Vec1d(1.0)))

let s0_Vec2d = [ for s in 1..n_bodies -> (Vec2d(float s, 1.0), Vec2d(0.0, 0.0)) ]
let ef_Vec2d = euler_implicit (accel (Vec2d(0.0, 1.0)))

let s0_Vec3d = [ for s in 1..n_bodies -> (Vec3d(float s, 1.0, -1.0), Vec3d(0.0, 0.0, 0.0)) ]
let ef_Vec3d = euler_implicit (accel (Vec3d(0.0, 1.0, 0.0)))

let s0_CVec1d = [ for s in 1..n_bodies -> (CVec1d(float s), CVec1d(0.0)) ]
let ef_CVec1d = euler_implicit (accel (CVec1d(1.0)))

let s0_CVec2d = [ for s in 1..n_bodies -> (CVec2d(float s, 1.0), CVec2d(0.0, 0.0)) ]
let ef_CVec2d = euler_implicit (accel (CVec2d(0.0, 1.0)))

let s0_CVec3d = [ for s in 1..n_bodies -> (CVec3d(float s, 1.0, -1.0), CVec3d(0.0, 0.0, 0.0)) ]
let ef_CVec3d = euler_implicit (accel (CVec3d(0.0, 1.0, 0.0)))

let s0_One = [ for s in 1..n_bodies -> (One(float s), One(0.0)) ]
let ef_One = euler_implicit (accel (One(1.0)))

let s0_Two = [ for s in 1..n_bodies -> (Two(float s, 1.0), Two(0.0, 0.0)) ]
let ef_Two = euler_implicit (accel (Two(0.0, 1.0)))

let s0_Three = [ for s in 1..n_bodies -> (Three(float s, 1.0, -1.0), Three(0.0, 0.0, 0.0)) ]
let ef_Three = euler_implicit (accel (Three(0.0, 1.0, 0.0)))

printfn "1D (struct)"
run ef_Vec1d s0_Vec1d

printfn "2D (struct)"
run ef_Vec2d s0_Vec2d

printfn "3D (struct)"
run ef_Vec3d s0_Vec3d

printfn "1D (class)"
run ef_CVec1d s0_CVec1d

printfn "2D (class)"
run ef_CVec2d s0_CVec2d

printfn "3D (class)"
run ef_CVec3d s0_CVec3d

printfn "1D (union)"
run ef_One s0_One

printfn "2D (union)"
run ef_Two s0_Two

printfn "3D (union)"
run ef_Three s0_Three

ignore (Console.ReadKey(true))

Here come the detailed explanations:

type VecN =
One of float
[...]
type CVec3d (x: float, y: float, z: float) = class
member v.X = x
member v.Y = y
member v.Z = z

static member inline plus (a: CVec3d) (b: CVec3d) = CVec3d(a.X + b.X, a.Y + b.Y, a.Z + b.Z)
static member inline scale (k: float) (a: CVec3d) = CVec3d(k * a.X, k * a.Y, k * a.Z)
end

These definitions show different ways to implement vector types. The first method, which uses a union, is a bit uncommon. It is inelegant because it does not take advantage of the type system to capture the fact that adding vectors of different dimensions is not allowed. It is also the slowest implementation of vectors of all.
Follow definitions of one, two and three dimensional vectors using structs, which we already saw in the previous tutorial. The last group is almost identical, except for the fact that classes are used. I won't go into the differences between structs and classes in this post, but it's interesting to see that structs are faster in this program. This is however not generally true, even when considering only the special case of 3d vectors.

The interesting part starts below.

let inline spring (pos: ^vec) =

This defines a generic function "spring" taking a parameter of type "^vec". Note that "vec" here is not an actual type, but a type variable. We have already used the notation " 'vec", which plays a similar role. The difference resides in who creates the concrete function. In the case of " 'vec", this is handled by the generics mechanics in the .NET runtime. In the present case, using "^vec", it is handled by the F# compiler.
(QUESTION: is that correct? I tried replacing "^vec" with "'vec" in this line, and that worked too.)
This requires the function to be declared as inline. The compiler will generate a new copy of the code for each concrete type with which it is used.
For further details about type constraints, see Statically typed duck typing in F#.

let (*) k x = (^vec: (static member scale: float -> ^vec -> ^vec) k) x

I will start with the part of the line after the "=" symbol. It constitutes a type constraint, and means that "^vec" must have a static member named "scale", accepting a float and returning a function from "^vec" to "^vec" (in other words: a function taking a float and a "^vec" and returning a "^vec").
The rest of the line defines a function "*", thus overloading the multiplication operator, which allows us to write expressions in a natural way. Note that this method could also have been used in Tutorial 8, its availability is not subject to the use of type constraints.

let k = 100.0
-k * pos

Finally something we recognize...

You may have noticed that unlike Tutorial 8, this tutorial includes the optimizations from Tutorial 7 and 7b (aggressive inlining and OptimizedClosures). They do seem to make a difference here.

Update:
This Tutorial used to include a section comparing the performance of the F# and the C++ versions of Euler using doubles and structs (for 1-, 2- and 3-dimensional vectors). I noticed the timing results depended very much on whether the programs were started from Visual Studio or directly from Windows. C++ programs using .NET are faster when started from Visual studio, whereas F# programs run faster when started outside of Visual Studio. The differences were large enough to render comparisons meaningless, and I have therefore decided to remove the benchmark results until I have cleared that up.

I have kept the most original method to write generic code for the next Tutorial. Stay tuned!