Space Invaders


_images/SpaceInvaders.jpg

Architecture and Features

With the following features the space invaders clone is a show-case for game programming with HGamer3D:

  • Sound, GUI, Key-Input
  • Game modes: intro screen, playing, camera move mode
  • Animated invaders
  • Collision detection
  • Actors based game architecture
  • Reader and State Monad for Actor functions
  • Persistent tree data-type for data of all game elements
  • Separation of concerns by actor architecture

Howto Play

  • install aio (see The Arriccio Tool)
  • run the command aio start http://www.hgamer3d.org/game/SpaceIn3d
  • allow the downloads (only first time, next time it is cached)
  • you might put the aio start .. command in a batch file or start link
  • try the “fly” feature by hitting F1 and using the keys W, A, S, D, Q, up, down

Howto Compile

  • create a new directory and cd into it
  • follow the steps below:
git clone http://github.com/atzeus/HMap
git clone http://github.com/urs-of-the-backwoods/SpaceIn3d
cd SpaceIn3d
aio http://www.hgamer3d.org/component/Stack install --local-bin-path .
aio http://www.hgamer3d.org/component/Run ./game (Linux)
aio http://www.hgamer3d.org/component/Run game.exe (Windows)

Actors

A small actor implementation serves the purpose of separating different concerns to different high-level components. The capabilities of an actor are to receive messages, act upon them in a function looping endlessly and sending messages to other actors as outcome of their specific logic piece. Additionally they might spawn new actors to support them with functionality. The Actor type itself is decoupled from the function running the actor to enable circular dependencies between actors. The main function is a Reader-State-Monad to keep state between loops and to carry read only configuration type of information.

Note

the forkIO in the runActor function creates a new thread for each actor.

newtype Actor = Actor (MVar Message) 

newActor :: IO Actor
newActor = do
    mv <- newEmptyMVar
    return (Actor mv)

type ReaderStateIO r s a = StateT s (ReaderT r IO) a

runActor :: Actor -> (Actor -> Message -> ReaderStateIO r s () ) -> r -> s -> IO ()
runActor a@(Actor mv) f ri si = do
    let loop mv s = do
            msg <- takeMVar mv
            (_, s') <- runReaderT (runStateT (f a msg) s) ri
            loop mv s'
    forkIO $ loop mv si
    return ()

sendMsg :: Actor -> Message -> IO ()
sendMsg (Actor mv) m = putMVar mv m

The code base of the space invader clone is split into a number of actors, as shown in the following table. Each actor is running its own function in a separate IO thread.

Actor spawns sends messages to rec. messages from function
Switch Music, Key, Animate, Flying, GameLoop, StatusBar Music, Key, Animate, Flying, GameLoop, StatusBar Key, GameLoop, main game routine (heartbeat) main handler for modes, event distribution
GameLoop Move, Canon, Collision Switch, Move, Canon, Collision Collision, Switch handles main movement of invaders, shots, canon and collision detection
Move   Collision, Music, StatusBar GameLoop moves invaders
Canon   Collision, Music GameLoop moves canon, shots
Collision   GameLoop GameLoop, Move, Canon Collision detection
Flying     Switch moves camera in “fly” mode
Animate     Switch animates invaders
StatusBar     Move, Switch display game status
Key   Switch Switch (poll pressed keys) pick up keys from Input, keep keys pressed down
Music     Switch, Move, Canon plays sounds and music

Switch Actor

The switch actor is the coordination center of the complete appication. It keeps an indicator in which mode the game is currently executing and processes events, depending on this mode. As an example the key-input from the key actor is routed through the switch actor and is interpreted differently if the game is in “playing” mode or in “pause” state. The switch actor initializes new actors also depending on progress in game state. In the beginning it also displays the entry screen and after the user entered her name, the switch actor progresses to build state and creates the moving entities. For the main activities during the “play” mode the switch actor creates a gameloop actor, which handles parallel computations and collision detection. Finally the switch actor interconnects the auxilliary actors like music, animation, status bar and key input.

    case gameState of

        ProgramInitializing -> 
            case msg of
                StartProgram -> do
                    -- initialize music, keys and start screen
                    mA <- liftIO $ newMusicActor hg3d
                    kA <- liftIO $ newKeyActor hg3d switchA
                    startScreenText' <- liftIO $ showInitScreen hg3d
                    liftIO $ sendMsg mA StartMusic
                    -- create hearbeat of program
                    let cycleLoop n m = do
                            if n == 0 
                                then sendMsg switchA SlowCycle
                                else return ()
                            sendMsg kA PollKeys
                            sendMsg switchA FastCycle
                            sleepFor (msecT 30)
                            cycleLoop (if n == 0 then m else n - 1) m
                    liftIO $ forkIO $ cycleLoop 0 10

                    put (myActors {keyA = kA, musicA = mA}, startScreenText', name, InitScreen)
                _ -> returnStay

The typical code example above shows the first lines of the big switch statement the switch actor executes. Specifically if in ProgramInitializing state the switch actor initializes the init screen and the key and music actor upon receiving the StartProgram message. After this is done it forwards the state to InitScreen.

GameLoop Actor

The gameloop actor is a prototypical actor and short enough to display here completely. It creates the move, canon and collision actor and communicates in addition with the switch actor. In addition it hands over the music and status bar actor to the move and collision actors, created.

The main function of the gameloop actor is coordinating the computation of the next gamestate by running the move and the canon actor in parallel. Those actor hand over the result of their computations to the collision actor which computes the collision status and sends it back to the gameloop actor for progressing with the next step. This makes up an efficient and fast gameloop with some parallel computation for movement of invaders (move actor) and movement of canon (canon actor), whereas collision detection is sequenced after having the results of both previous steps. Also note that the animation is done completely independently from the gameloop actor. This works since the 3D scene graph allows us to move the invader and canon entities independently from the pixels they are composed of. Also interesting to see how the data flow is implemented. The actual date for the current step is simply send in a message to the next computing actor. This is functional programming with immutable data structures at its best.

data MyActors = MyActors {
    moveA :: Actor,
    canonA :: Actor,
    collA :: Actor,
    switchA :: Actor
}

type GlaR = MyActors
type GlaS = (Maybe GameData, Maybe GameData, Maybe [Unique])

newGameLoopActor :: Actor -> Actor -> Actor -> Keys -> GameData -> GameData -> IO Actor
newGameLoopActor switchA musicA statusA keys invaders canons = do

    actor <- newActor

    collA <- newCollisionActor actor keys
    moveA <- newMoveActor collA musicA statusA keys
    canonA <- newCanonActor collA musicA keys

    runActor actor gameLoopActorF (MyActors moveA canonA collA switchA) (Nothing, Nothing, Just [])
    return actor


gameLoopActorF :: Actor -> Message -> ReaderStateIO GlaR GlaS ()
gameLoopActorF loopA msg = do

    myActors <- lift ask
    (slotMoveData, slotCanonData, slotCollData) <- get

    case msg of

        ActualCanonData canonData -> put (slotMoveData, Just canonData, slotCollData) >> return ()
        ActualInvaderData moveData -> put (Just moveData, slotCanonData, slotCollData) >> return ()
        ActualCollData collData -> put (slotMoveData, slotCanonData, Just collData) >> return ()

        FastCycle -> do
            case (slotMoveData, slotCanonData, slotCollData) of
                (Just moveData, Just canonData, Just collData) -> do
        --                            liftIO $ print "good cycle"
                    liftIO $ sendMsg (collA myActors) (CollisionStep canonData moveData)
                    liftIO $ sendMsg (canonA myActors) (CanonStep canonData collData)
                    liftIO $ sendMsg (moveA myActors) (MoveStep moveData collData)
                    put (Nothing, Nothing, Nothing)
                    return ()
                _ -> do
                    liftIO $ print "missed cycle"
                    return ()

        MoveLeft -> liftIO $ sendMsg (canonA myActors) MoveLeft
        MoveRight -> liftIO $ sendMsg (canonA myActors) MoveRight
        Shoot -> liftIO $ sendMsg (canonA myActors) Shoot

        GameLostOverrun -> liftIO $ sendMsg (switchA myActors) GameLostOverrun
        GameWon -> liftIO $ sendMsg (switchA myActors) GameWon

        _ -> return ()

Data Structure

Message ADT

All messages used in the program are shown below. They constitute the high level run-time coordination flow, used in the game.

data Message = StartProgram
             | StartMusic | StopMusic | PlayShot | PlayNoShot | PlayExplosion | PlayStep
             | KeysPressed [T.Text] | SingleKey T.Text | PollKeys 
             | FastCycle | SlowCycle 
             | MoveLeft | MoveRight | Shoot 
             | RollRight | RollLeft | PitchUp | PitchDown | YawLeft | YawRight | MoreSpeed | LessSpeed | ZeroSpeed  
             | ResetCamPosition | RestoreCamPosition | SaveCamPosition
             | DisplayStatus | HideStatus | AddCount Int | SetMode T.Text 
             | ActualInvaderData GameData | ActualCanonData GameData | ActualCollData [Unique] 
             | CanonStep GameData [Unique] | MoveStep GameData [Unique] | CollisionStep GameData GameData
             | GameLostOverrun | GameWon

Tree for game elements

The main game status is held in a tree data structure. The elements of the tree contain a node type and node data. The node data contains different entries, position information, size information, the HGamer3D entities, animation information and a unique key for each node. To be more flexible the node data is stored in an heterogenous map.

data NodeType = Canon | ReserveCanon | Boulder | Invader Int | Ship | Shot 
              | InvaderRow | CanonRow | BoulderRow | ShotRow
              | Pixel | PixelA | PixelB      -- the single pixel cubes, different variants for animation
              | Empty
              deriving (Eq, Show, Ord)

type NodeData = HM.HMap

type GameData = Tree (NodeType, NodeData)

type KPos = HM.HKey HM.T PixelPos
type KHits = HM.HKey HM.T HitInfo
type KDim = HM.HKey HM.T DimInfo
type KEnt = HM.HKey HM.T Entity
type KAnim = HM.HKey HM.T AnimInfo
type KUni = HM.HKey HM.T Unique

HGamer3D Entities

The function createMoveNode in the Data module creates the HGamer3D entities and stores them in the node data as an entry. This seems weird because the approach mixes non-mutual with mutual data. But think for a while. The entities are fully thread safe. Upon each modification step from one gameloop step to the next, data changes and a new immutable tree is created. During this step, simply the data is synchronized with the entity data of the 3D world. There is no reason to be concerned. References are not created or destroyed only values are being set. This makes up a working model, where the benefits of the immutable tree data structure can be kept. Even in parallel the animation takes place, which is explained in the next section.

Animation

The animation is the movement of the “legs” and “arms” of the invaders. If you watch closely, you see that each invader has its own rythm, when to move. This is done by storing a random number and move only each n cycles. Since also the starting point is not uniform, state for the animation is also stored in the node data. On each animation step, pixels are exchanged from a hidden location to the screen and back in the next cycle. The animations are completely independent from the other changes on the data. This is leveraged to parallelize the animation completely. In the beginning, after the creation of the game data tree, the tree is copied to both the animation actor and the gameloop actor. Both actors work independently with their local copies and advance their respective node data states only on their data.

animateLevel :: ReaderStateIO AnaR AnaS ()
animateLevel = do

    keys <- lift ask
    let (kent, kdim, kpos, khits, kanim, kuni) = keys
    (count, gameData) <- get

    (gameData', _) <- liftIO $ mapAccumLM (\(nodeType, nodeData) (nt, nd) -> case nodeType of
                (Invader _) -> do
                    let ai = nodeData ! kanim
                    let ai' = getCurrentAnimation ai count
                    let nodeData' = setData kanim ai' nodeData
                    return ((nodeType, nodeData'), (nodeType, nodeData')) -- set acc to nodeData of Invader

                PixelA -> do
                    let ai = nd ! kanim         -- accu, this is the previous Invader node info!
                    if aiSwapNow ai
                        then do
                            let (x, y) = nodeData ! kpos
                            case aiType ai of
                                PixelA -> setC (nodeData ! kent) ctPosition $ relativePosFromPixelPos (nd ! kdim) (x, y)
                                PixelB -> setC (nodeData ! kent) ctPosition (Vec3 (-1000.0) 0 0)
                                _ -> return ()
                        else return ()
                    return ((nodeType, nodeData), (nt, nd))

                PixelB ->  do
                    let ai = nd ! kanim         -- accu, this is the previous Invader node info!
                    if aiSwapNow ai
                        then do
                            let (x, y) = nodeData ! kpos
                            case aiType ai of
                                PixelB -> setC (nodeData ! kent) ctPosition $ relativePosFromPixelPos (nd ! kdim) (x, y)
                                PixelA -> setC (nodeData ! kent) ctPosition (Vec3 (-1000.0) 0 0)
                                _ -> return ()
                        else return ()
                    return ((nodeType, nodeData), (nt, nd))

                _ -> return ((nodeType, nodeData), (nt, nd)) -- noch changes

            ) (undefined, undefined) gameData

    put (count, gameData')
    return ()

The code of the animation function makes use of the tree structure of the invaders data. For each invader there is a central node holding the animation information and sub-nodes with the pixels. The pixels have different node types Pixel, PixelA and PixelB indicating to which animation state they belong. The overall loop is an accumL type of function in the accumulator during the fold the last node information of the central node is stored. When the algorithm visits the sub-node pixels the top node info is still available and used to decide the exchange of pixels on the screen.

Collision Detection

During collision detection the tree is flattened to a list and on the list different filters are applied. Then collisions are detected between shots and invaders and between invaders and boulders for detecting an overrun of the invaders in the position of the boulders.

runCollisionDetection :: Actor -> Keys -> GameData -> GameData -> ReaderStateIO CoaR CoaS ()
runCollisionDetection gameLoopA keys invaderData canonData = do
    let (kent, kdim, kpos, khits, kanim, kuni) = keys
    let invaderList = flatten invaderData
    let invaders = filter (\(nt, nd) -> case nt of
            (Invader _) -> let (x, y) = nd ! kpos in if x < (-500) then False else True
            _ -> False
            ) invaderList

    if length invaders == 0
        then do
            liftIO $ sendMsg gameLoopA GameWon
            return ()
        else do
            let boulders = filter (\(nt, nd) -> case nt of
                    Boulder -> let (x, y) = nd ! kpos in if x < (-500) then False else True
                    _ -> False
                    ) invaderList
            let invsAndBoulders = invaders ++ boulders
            let shots = filter (\(nt, nd) -> nt == Shot) (flatten canonData)

            -- collision invader boulder -> game end
            let colsBoulders = [ (s ! kuni, i ! kuni) | (_, s) <- boulders, (_, i) <- invaders, isCollision keys i s]
            if length colsBoulders > 0
                then do
                    liftIO $ sendMsg gameLoopA GameLostOverrun
                    return ()
                else do
                    let cols = concatMap (\(a, b) -> [a, b]) [ (s ! kuni, i ! kuni) | (_, s) <- shots, (_, i) <- invsAndBoulders, isCollision keys i s]

                    liftIO $ sendMsg gameLoopA $ ActualInvaderData invaderData 
                    liftIO $ sendMsg gameLoopA $ ActualCanonData canonData 
                    liftIO $ sendMsg gameLoopA $ ActualCollData cols
                    put (Nothing, Nothing)
                    return ()

Multi-Threaded Game Architecture

As a summary it is fair to say that the standard functional methodologies work well with game programming. Immutable data structures combined with actors make up for a good toolset. Actors are not more then functions itself, encapsulated with their own state and interacting via messages. So compared to object oriented programming where objects encapsulate state, runtime and pure functions in one object in the example shown here, more coarse grained runtime information is structured with actors whereas all other aspects are implemented with mostly pure functions. This leds to a mult-threaded game architecture with a separation of concerns.