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

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

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

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

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

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 !

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

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

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

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

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

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:

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

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:

<!--
The SearchPaths property is set to find assemblies in the following order:

(1) Files from current project - indicated by {CandidateAssemblyFiles}
(2) $(ReferencePath) - the reference path property, which comes from the .USER file.
(3) The hintpath from the referenced item itself, indicated by {HintPathFromItem}.
(4) The directory of MSBuild's "target" runtime from GetFrameworkPath.
The "target" runtime folder is the folder of the runtime that MSBuild is a part of.
(5) Registered assembly folders, indicated by {Registry:*,*,*}
(6) Legacy registered assembly folders, indicated by {AssemblyFolders}
(7) Look in the application's output folder (like bin\debug)
(8) Resolve to the GAC.
(9) Treat the reference's Include as if it were a real file name.
-->
<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:

<TargetFrameworkVersion>v3.5</TargetFrameworkVersion>
+ <XnaFrameworkVersion>v3.1</XnaFrameworkVersion>
+ <XnaPlatform>Xbox 360</XnaPlatform>

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

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

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

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

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

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.