Sunday, August 21, 2011

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

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

The main subject of the book is the F# language and its various
constructs, but every single chapter is centered around a game-related
problem. Each one of the first 5 chapters describes a problem, shows
and discusses its solution and then discusses in depth the F#
constructs used. The book has a (relatively rare) "problem-solution"
approach where everything is explained because of how well it works in
solving the problem, and not just "because". The 5 problems we present
are:
- a bouncing ball
- the Saturn V rocket
- an asteroid field
- a large asteroid field optimized with quad trees
- a police starship that must fight off a pirate ship attacking a
cargo freighter
In the last two chapters we use XNA to build a 2D and 3D renderer for
two of the samples we have seen. We show the basics of the SpriteBatch
class, the Model class, input management and audio with this powerful
framework. Basically, we cover the most important aspects of XNA in a
simple and succint way.
I had a quick look at the book and I think Giuseppe's description is a fair one. In other words, this is not a book primarily about game programming, but an introduction to F#. Although it touches some advanced topics such as custom workflows, it is not a comprehensive coverage of the language.
All in all, if you are looking for a gentle and quick introduction to the language, and you are interested in game programming, you should definitely check this book.

The book is available on Amazon and Smashwords.

Wednesday, August 3, 2011

The forgotten control flow construct

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

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

int parse()
{
    Token   tok;

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

Let's see how using a while turns out:

type Token = END

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

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

                if tok = END then
                    Accepted
                else
                    Shifting

            | Shifting ->
                if shift tok then
                    Reading
                else
                    Reducing

            | Reducing ->
                if reduce tok then
                    Shifting
                else
                    Errored

            | Errored | Accepted -> failwith "Invalid state"

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

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

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

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

type Token = END | SOMETHINGELSE

type Status = ACCEPT | ERROR

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

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

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

    do_read()

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

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

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

Tuesday, August 2, 2011

Is it worth it?

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

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

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

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

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

Differences in ScreenBase

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

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

Differences in inheritors

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

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

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

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

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

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

Advantages of composition and delegation over inheritance

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

Advantages of inheritance over composition and delegation:

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

Conclusion

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

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