Jump to content

  • Log In with Google      Sign In   
  • Create Account

Like
13Likes
Dislike

Haskell Game Object Design - Or How Functions Can Get You Apples

By Marc Sunet | Published Jul 02 2014 05:52 AM in Game Programming
Peer Reviewed by (Alpha_ProgDes, Dave Hunt, jbadams)

haskell game object design subtyping

In this tutorial, we will see one possible way to model game objects in Haskell. To do so, the tutorial proposes several design problems with increasing levels of difficulty. For each of these problems, a solution in C++ is presented first and then potential Haskell alternatives are discussed. By the end, we will have seen how to dodge subtyping and dynamic dispatch in the design of game objects by making use of the close relationship between objects and closures. The information presented in the following sections is not new, but if you are new to functional programming you might nevertheless find it worthwhile. Finally, it is worth noting that some experience with C++ and some background in object-oriented programming are assumed.

Problem 1: An Initial Game Object


Suppose we are building a game. It is quite natural to think of the objects in a game as just that, game objects. As a starting point, let's say that in our game there are two types of objects: apples and bananas. Nevertheless, we do not want to limit ourselves to just these two types of objects, since we might decide to add new ones later on. In the object-oriented paradigm, we would throw in a base class, say, GameObject, from which particular types of objects such as Apple and Banana would derive. This would allow us to decouple the rest of the game code from these specific types, giving us the ability to add new types of objects at a later stage without modifying existing code and therefore satisfying the open/closed principle. The following code snippet illustrates this concept:

class GameObject {
public:
    virtual void render () const = 0;
};


class Apple : public GameObject {
public:
    void render () const { cout << "apple" << endl; }
};


class Banana : public GameObject {
public:
    void render () const { cout << "banana" << endl; }
};

When translating the above code into Haskell, we might be tempted to use algebraic data types as follows:

data GameObject = Apple | Banana

render Apple  = putStrLn "apple"
render Banana = putStrLn "banana"

The problem with this approach is that the open/closed principle is not preserved; we cannot add new value constructors without modifying the definition of the GameObject data type and the functions that pattern match on it. For this reason, we seek a better alternative where the principle still holds.

Functions in Disguise


Notice that in the C++ version of the code, the GameObject, Apple and Banana classes have no data, only behaviour. What we have actually defined is a set of function objects, which are simply functions disguised as objects. Since the C++ version of the code is inherently functional, we ought to be able to arrive at a Haskell translation. To do so, we just have to think about the behaviour exposed by the GameObject class. In this context, a game object is essentially a function that renders an object, and by capturing this very notion, we arrive at the following Haskell alternative:

data GameObject = GameObject { render :: IO () }

apple  = GameObject $ putStrLn "apple"
banana = GameObject $ putStrLn "banana"

In this solution, apples and bananas are not proper types, but functions that construct GameObject values. This is a key point that will accompany us throughout the rest of this tutorial.

To fully grasp the idea behind this solution, it is worth pointing out that the render field is really a function of type GameObject -> IO (). In other words, the render field is a function that when applied to a given GameObject, yields an IO action that gets that object rendered:

> let a = apple
> render apple
apple
> :t render
render :: GameObject -> IO ()
> render banana
banana

This might seem rather obvious at this point. However, further problems will become more complicated and will require that we keep in mind this idea that record fields are really functions that take records as arguments, so this is a good place to bring it up.

Finally, the above solution better mimics the C++ version of the code by allowing us to add new game objects without modifying the GameObject data type and therefore satisfying the open/closed principle. For instance, we can now add oranges by simply writing:

orange = GameObject $ putStrLn "orange"

Problem 2: Identifying Game Objects with Unique IDs


Suppose that we now wish to go further by identifying game objects with a unique ID and outputting this ID when rendering an object. In C++, this could be modelled as follows:

typedef int GoID;

class GameObject {
    GoID _id;

public:
    GameObject (GoID id) : _id(id) {}

    GoID id () const { return _id; }

    virtual void render () const = 0;
};


class Apple : public GameObject {
public:
    Apple (GoID id) : GameObject(id) {}

    void render () const { cout << "apple: id " << id() << endl; }
};


class Banana : public GameObject {
public:
    Banana (GoID id) : GameObject(id) {}

    void render () const { cout << "banana: id " << id() << endl; }
};

Same Data, Different Behaviour


Since the ID attribute is common to all game objects, our old design adapts to the new situation without any major changes. All we need to do is incorporate the new ID attribute into the GameObject data type:

type GoID = Int

data GameObject = GameObject
    { goID   :: GoID
    , render :: IO () }

apple  goid = GameObject goid $ putStrLn ("apple: id " ++ show goid)
banana goid = GameObject goid $ putStrLn ("banana: id " ++ show goid)

Adding data common to all game objects is not a problem; we just need to slightly complicate the GameObject data type to reflect the changes. Notice that since apple and banana are functions that build GameObject values, we must supply them with the game object ID that identifies the game object being built.

Problem 3: Updating Game Objects


A static game is not all that fun, so eventually we will want game objects to be updated over the course of time. For this reason, suppose that apples now have a level attribute that is included in their render, and that apples level up on every game tick. This is certainly not very realistic, but is enough to illustrate the next problem. Finally, let bananas have no levels whatsoever. The C++ version of the game could resemble the following:

typedef int GoID;

class GameObject {
    GoID _id;

public:
    GameObject (GoID id) : _id(id) {}

    GoID id () const { return _id; }

    virtual void render () const = 0;

    virtual void update () {}
};

class Apple : public GameObject {
    int level;

public:
    Apple (GoID id) : GameObject(id), level(0) {}

    void render () const { cout << "apple: id " << id()
                                << ", level "   << level
                                << endl; }

    void update () { level++; }
};

class Banana : public GameObject {
public:
    Banana (GoID id) : GameObject(id) {}

    void render () const { cout << "banana: id " << id() << endl; }
};

To reflect the changes in Haskell, we might be tempted to write:

data GameObject = GameObject
    { level  :: Int
    , goID   :: GoID
    , render :: IO () }

This representation is not entirely accurate, however, because bananas have no levels. Pushing the level attribute all the way up to the GameObject data type would imply that all game objects have a level, which is not the case. How about the following, then:

data GameObject = Apple { level :: Int, ... } | Banana { ... }

This would once again remove the possibility of adding new kinds of game objects.

The problem is that while a GameObject is still just something that can render, update, and uniquely identify itself, an apple needs to carry that additional level attribute with it.

Closures to the Rescue


To solve this new problem, we just have to use the same trick we have been applying so far: representing apples as functions. With an object-oriented mind, we could define an apple as follows:

An Apple is a type of GameObject that has a level, levels up every certain amount of time, and that as with all game objects, can render and uniquely identify itself.


This definition, however, does not properly translate into Haskell because it is trying to define apples as a subtype of a more general GameObject type, which implies the use of subtyping. Instead, we have to rethink what it is that we wish to think of as an apple. With a functional perspective, we could say:

An apple is a function that takes a game object ID and a level and returns a GameObject that is identified by the given ID, shows the given level in its render, and the update function of which returns a new GameObject that is exactly the same but with its level increased by 1.


In other words, an apple is, once again, a function that yields a GameObject value, except that this time it also takes the set of attributes needed to represent an apple:

import Text.Printf

type GoID  = Int
type Level = Int

data GameObject = GameObject
    { goID   :: GoID
    , render :: IO ()
    , update :: GameObject }

banana :: GoID -> GameObject
banana goid =
    GameObject
    { goID   = goid
    , render = printf "banana: id %d\n" goid
    , update = banana goid }

apple :: Level -> GoID -> GameObject
apple level goid =
    GameObject
    { goID   = goid
    , render = printf "apple: id %d, level %d\n" goid level
    , update = apple (level+1) goid }

Perhaps this is starting to get somewhat confusing. Recall, however, that record fields are really record-eating functions:

> :t render
render :: GameObject -> IO ()
> :t update
update :: GameObject -> GameObject
> mapM_ render . take 5 $ iterate update (apple 1 17)
apple: id 17, level 1
apple: id 17, level 2
apple: id 17, level 3
apple: id 17, level 4
apple: id 17, level 5
> mapM_ render . take 5 $ iterate update (banana 17)
banana: id 17
banana: id 17
banana: id 17
banana: id 17
banana: id 17

The render field takes a GameObject and renders it. The update field, on the other hand, takes a GameObject and updates it. In the case of apples, the update function increases the apple's level by one, whereas in the case of bananas, an identical banana is yielded.

The essence of the above solution is that in Haskell, functions are not just pieces of code that take some parameters and return a value. Functions are first class citizens: you can feed them into and return them from other functions as well as store them as data. Functions allow us to represent regular computations that take some arguments and yield a value, data structures, infinite lists, and more. Here, we use functions to represent particular "types" of game objects. The only data type that we actually have is GameObject, however; particular game objects, such as apples and bananas, are not subtypes of a more general GameObject type, but values of that type. Since the terminology can get a bit confusing, we note that when we say "an apple is a function that assembles a GameObject" and "an apple is a GameObject value", we really mean the same thing. That being said, it is worth noting that as far as apple philosophy goes, we would say that an apple is technically a closure, not the apple-building function per se, since what really defines an apple is the application of the apple function to a given set of apple attributes. Nevertheless, we can still think of an apple as a way to assemble game objects.

Before we move on, let us take a closer look at the above solution. A priori, we might believe that something does not seem quite right:

apple :: Level -> GoID -> GameObject
apple level goid =
    GameObject
    { ...
    , update = apple (level+1) goid }

Notice that the apple function is being defined in terms of itself, since the update function recursively calls the apple function in its definition. This will not lead into infinite recursion, however, because Haskell is a lazy language. The new apple is only evaluated on demand, such as when it is rendered, and it is for this reason that the apple function is essentially building a lazy sequence of apples. Compare it to the following function:

count x = x : count (x+1)

The count function defined above creates an infinite list of increasing numbers. Laziness gives us the power to deal with infinity, which is why the following example will not induce the interpreter into a state of infinite recursion:

> let count x = x : count (x+1)
> take 5 $ count 1
[1,2,3,4,5]

In the above example, we take five numbers from the list and get them printed on screen. The remaining part of the list, containing numbers 6, 7, 8..., is not evaluated because it is not needed, since we are only printing the first five numbers. Similarly, the update function defined previously will not do more work than necessary, which is why its infinitely recursive definition does actually work.

Problem 4: Towards More Realistic Updates


Levelling apples up on every game tick is unrealistic and undesirable, since the rate at which they do so varies depending on available resources. What we would like now is the ability to generate a dynamic sequence of apples based on some external time measurement. To do so, we let the update method take a time delta and let apples level up every 5 seconds. In C++, this could be done as follows:

typedef int GoID;

class GameObject {
    GoID _id;

public:
    GameObject (GoID id) : _id(id) {}

    GoID id () const { return _id; }

    virtual void render () const = 0;

    virtual void update (float dt) {}
};

class Apple : public GameObject {
    int   level;
    float elapsed;

public:
    Apple (GoID id) : GameObject(id), level(0), elapsed(0) {}
    
    void render () const { cout << "apple: id " << id()
                                << ", level "   << level << endl; }
	
    void update (float dt) {
        elapsed += dt;
        if (elapsed >= 5.0f) {
            elapsed = elapsed - 5.0f;
            level++;
        }
    }
};

class Banana : public GameObject {
public:
    Banana (GoID id) : GameObject(id) {}
    
    void render () const { cout << "banana: id " << id() << endl; }
};

To translate this new behaviour into Haskell, we once again make use of the idea that apples and bananas are simply functions that assemble GameObject values. A game object is still something that can be rendered, updated, and uniquely identified. We just need to expand on our existing solution by modifying the update function to take a time delta, just as in the C++ version of the code:

type Dt = Float

data GameObject = GameObject
    { goID   :: GoID
    , render :: IO ()
    , update :: Dt -> GameObject }

The definition of banana only varies slightly. Its update function ignores the given time delta and returns the original banana:

banana :: GoID -> GameObject
banana goid =
    GameObject
    { goID   = goid
    , render = printf "banana: id %d\n" goid
    , update = const $ banana goid }

Next, we turn to apples. In the previous section we saw that the level attribute can simply be trapped in a closure. We now do the same with the elapsed attribute and add that extra bit of logic to get the apples levelled up every 5 seconds:

type Elapsed = Float

apple :: Level -> Elapsed -> GoID -> GameObject
apple level elapsed goid =
    GameObject
    { goID   = goid
    , render = printf "apple: id %d, level %d\n" goid level
    , update = \dt ->
        let elapsed' = elapsed + dt
        in if elapsed' >= 5.0
            then apple (level+1) (elapsed' - 5.0) goid
            else apple  level     elapsed'        goid }

Now, an apple's update function creates a dynamic sequence of apples by reacting to time. In fact, it could react to any external event, such as user input or network messages. The Haskell solution is now just as extensible as the C++ version, but without the need of subtyping and dynamic dispatch.

Full source code follows:

import Text.Printf

type GoID = Int
type Dt   = Float

data GameObject = GameObject
    { goID   :: GoID
    , render :: IO ()
    , update :: Float -> GameObject }

banana :: GoID -> GameObject
banana goid =
    GameObject
    { goID   = goid
    , render = printf "banana: id %d\n" goid
    , update = const $ banana goid }

type Level   = Int
type Elapsed = Float

apple :: Level -> Elapsed -> GoID -> GameObject
apple level elapsed goid =
    GameObject
    { goID   = goid
    , render = printf "apple: id %d, level %d\n" goid level
    , update = \dt ->
        let elapsed' = elapsed + dt
        in if elapsed' >= 5.0
            then apple (level+1) (elapsed' - 5.0) goid
            else apple  level     elapsed'        goid }

The following example illustrates the above solution. Notice that apples are only updated when more than 5 seconds have elapsed, whereas bananas remain static:

> :t render
render :: GameObject -> IO ()
> :t update
update :: GameObject -> Float -> GameObject
> mapM_ render . take 5 $ iterate (flip update 3) (apple 1 0 17)
apple: id 17, level 1
apple: id 17, level 1
apple: id 17, level 2
apple: id 17, level 2
apple: id 17, level 3
> mapM_ render . take 5 $ iterate (flip update 3) (banana 17)
banana: id 17
banana: id 17
banana: id 17
banana: id 17
banana: id 17

Apple Reification Unleashed


Having an actual Apple data type will make the current solution more readable and will allow us to define functions that operate on a proper Apple type rather than a losely defined set of parameters. The Apple data type could be defined as:

data Apple = Apple
    { level   :: Level
    , elapsed :: Float }

At this point, one might argue that defining an apple as a type contradicts our argument that apples in our solutions are really functions, not proper types. The point here is that the Apple data type just captures all of the data needed to represent an apple; it is not trying to be a subtype of GameObject. The reason we do this is to allow for more readable code. For example, the apple update function can now be rewritten as:

updateApple :: Apple -> Dt -> Apple
updateApple (Apple level elapsed) dt =
    let elapsed' = elapsed + dt
    in if elapsed' >= 5.0
        then Apple (level+1) (elapsed' - 5.0)
        else Apple  level     elapsed'

Had we not defined the Apple type, the updateApple function would take one argument for each apple attribute like in the solution to problem 4. This grows rather unreadable and unmaintainable as the representation of an apple becomes more complex, which is why we define the Apple data type.

Moving on, we can redefine the apple function itself to act directly on an Apple value and make use of the updateApple function we have just defined:

apple :: Apple -> GoID -> GameObject
apple a goid =
    GameObject
    { goID   = goid
    , render = printf "apple: id %d, level %d\n" goid (level a)
    , update = flip apple goid . updateApple a }

Full source code with the above changes and additions follows:

import Text.Printf

type GoID = Int
type Dt   = Float

data GameObject = GameObject
    { goID   :: GoID
    , render :: IO ()
    , update :: Dt -> GameObject }

type Level   = Int
type Elapsed = Float

data Apple = Apple
    { level   :: Level
    , elapsed :: Elapsed }

updateApple :: Apple -> Dt -> Apple
updateApple (Apple level elapsed) dt =
    let elapsed' = elapsed + dt
    in if elapsed' >= 5.0
        then Apple (level+1) (elapsed' - 5.0)
        else Apple  level     elapsed'

apple :: Apple -> GoID -> GameObject
apple a goid =
    GameObject
    { goID   = goid
    , render = printf "apple: id %d, level %d\n" goid (level a)
    , update = flip apple goid . updateApple a }

banana :: GoID -> GameObject
banana goid =
    GameObject
    { goID   = goid
    , render = printf "banana: id %d\n" goid
    , update = const $ banana goid }

The following example illustrates this last solution. Note that it is not much different from that of problem 4; it simply makes use of the new Apple type to construct an apple:

> mapM_ render . take 5 $ iterate (flip update 3) (apple (Apple 1 0) 17)
apple: id 17, level 1
apple: id 17, level 1
apple: id 17, level 2
apple: id 17, level 2
apple: id 17, level 3
> mapM_ render . take 5 $ iterate (flip update 3) (banana 17)
banana: id 17
banana: id 17
banana: id 17
banana: id 17
banana: id 17

Conclusions


Many times, we might feel tempted to think of new entities as subtypes of a more general type. This, however, might not be the best solution to a given problem and does not properly map to languages lacking subtyping. In Haskell, we can use plain functions to encode these new entities as closures and to provide a mechanism to build values of that more general type that act as the subtypes we were first trying to define. This effectively dodges any use of subtyping and yields code that is equally extensible. When we are doing functional programming, we have to stop thinking of functions as just a mere means of computation; functions in a functional language will often go all the way and beyond.





License


GDOL (Gamedev.net Open License)




Comments

I have several problems with your article. First of all, the article do not have in my opinion a well defined target. The reader should be already familiar with haskell to understand it, but it isn't particularly useful for an experienced haskeller. Moreover, the article basically explains how to write an object oriented program in haskell. This is not functional programming.. This is not how a program should be designed in haskell. You shouldn't start by assuming you have some class GameObject which some methods and some subclasses like Apple and Banana. This is OOD! 

To be fair, the approach presented here is more or less "Reactive"; I would recommend people to read the various papers on Functional Reactive Programming to get a feel for it; the Space Invaders coded with Yampa Arcade is a good example I think : http://haskell.cs.yale.edu/wp-content/uploads/2011/01/yampa-arcade.pdf

I don't think it is very reactive. There are in fact some similarities, but the article mostly describes how to implement some kind of fake object oriented hierarchy in haskell. It does not describe how to implement game mechanics or object behaviors which is what (I think) FRP is all about. Describing some data (with associated functions) is not difficult in haskell. There are actually often several different ways of doing it. The difficult part is IMO making the various parts work together in an efficient way. How often do you have a set of completely independent objects without any interaction? What changes are needed to update your apples based, for example, on the number of other apples at the same level? What if you want to add user interaction? These are the reasons I think this article is not particularly useful. 

I'm no fluent haskeller yet, but I would have wrote the banana function with a let construct instead of the recursive call to self:

banana goid =
  let b = GameObject
          { goID   = goid
          , render = printf "banana: id %d\n" goid
          , update = b }
  in b      

for the first updatable instance, and for the second:

banana goid =
    let b = GameObject
            { goID   = goid
            , render = printf "banana: id %d\n" goid
            , update = const $ b }
    in b

For what I understood (why recursive let make space efficient, Tying the Knot), this gives a truly "identical banana" each time update is called instead of a chunk that yields a similar banana.

Thank you, this is good approach.
 
There is an error, you missed a goID field:
 

data Apple = Apple
    { level :: Level
    , elapsed :: Float }

because it was used here:

updateApple (Apple goid level elapsed) dt = ...

Note: Please offer only positive, constructive comments - we are looking to promote a positive atmosphere where collaboration is valued above all else.




PARTNERS