Parallel draw-update XNA game component

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

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

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

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

namespace CleverRake.XnaUtils

open Microsoft.Xna.Framework
open System.Threading

type IFramePerSecondCounter =
    abstract FramesPerSecond : float

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

    inherit DrawableGameComponent(game)

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

    let mutable enabled = true
    let mutable update_order = 0

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

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

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

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

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

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

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

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

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

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

    interface IFramePerSecondCounter with
        member this.FramesPerSecond = fps

    member this.FramesPerSecond = fps

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

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

    member this.IsDead = not(compute_thread.IsAlive)

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

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

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

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

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

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

Converting FS project files to target Xbox 360

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

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

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

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

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

Asteroid Sharp Shooter: Post-mortem

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.

Why we need better garbage collection on the Xbox

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.

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

Yes, it is.

Safe IO on the Xbox 360 in F#

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

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

All seasoned XBLIG developers know that this API has a number of pitfalls that are not always easy to avoid. Here are those that come to my mind:

1. Files can only be accessed after getting access to a storage device, which requires interaction with the user as soon as more than one storage device (hard-disk, memory unit, usb stick...) is available. As all of the steps cannot be performed within a single iteration of the update-loop, this forces the programmer to spread the steps over multiple iterations.
2. Attempting to get a storage device while the guide is open results in an exception. The guide is a graphical interface to the console's "operating system" which is available at any time.
3. At most one storage container may be in use at any time (a storage container is a collection of files, it can be seen as a directory).
4. The user may at any time remove a storage device, which results in exceptions being thrown while accessing the device.
5. File access is quite slow. In order to keep the GUI responsive, games must perform IO asynchronously.

Attempting to use the XNA API as it is almost invariably leads to bugs. I would say storage-related crashes are among the top 3 reasons games fail peer review. EasyStorage is a popular C# component that simplifies safe IO in games. In this article, I describe an alternative component written in F#.

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

Problem 1: Getting a storage device asynchronously

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

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

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

Problem 2: Avoiding GuideAlreadyVisible exceptions

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

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

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

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

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

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

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

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

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

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

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

Problem 4: Uncaring users yanking storage devices at inappropriate times

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

Problem 5: Asynchronous file operations

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

Wrap-up

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

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

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.

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.