Thursday, March 6, 2014

Experimenting with game engine concepts in Haskell

I've had Jason Gregory's excellent Game Engine Architecture (GEA) on my bookshelf for a while and every time I skim through I want to try out the ideas in it. Watching John Carmack talk about Haskell at QuakeCon got me thinking about trying them out in Haskell.

Armed with some notion that this was a good idea and some idea of how real games are set up I worked out a few details in haskellGame.  It's not even a demo at this point, but so far I've learned some things that I'd like to share.

(Thanks to for awesome free game graphics!)

Game Loop

Most games are driven by a game loop.  The loop grabs events, applies them to the game state then renders it.  In an imperative language, this might look like:


while(!gameEngine.done()) {
    currentTicks = getTicks();
    frameDelay = currentTicks - lastTicks;
    lastTicks = currentTicks;

GEA describes reasons why most engines update objects in batched phases.  This works out nicely in Haskell as it naturally operates on batches of objects of the same type.

In Haskell, each of these phases can be implemented as a function from GameState -> GameState. Then the loop just needs to apply all the phases to the game state on every run through. I later had to add some communication between the phases, which I represented as GameEventQueues. So a game phase is now (GameState, GameEventQueues) -> (GameState, GameEventQueues).

Could the GameState contain the event queues?  Maybe, I don't have a good idea of which is better at this point.


gameLoop :: (GameState -> IO t) -> IO Event -> GameState -> GHC.Word.Word32 -> IO ()
gameLoop drawAction eventAction gameState lastFrameTicks = do
  events <- HaskellGame.HumanInterface.Manager.pollEvents eventAction []
  let gameEvents = GameEventQueues { gameActions = concat $ (HaskellGame.HumanInterface.Manager.playerGameAction playerId) events,
                                  physicsActions = [] }
  let state = Data.Maybe.isNothing $ find (\x -> x == Graphics.UI.SDL.Events.Quit) events 
  currentTicks <- Graphics.UI.SDL.Time.getTicks
  let frameDelay = fromIntegral $ currentTicks - lastFrameTicks
  let (finalState, finalQueues) = 
        Data.List.foldl' ( \ currentGameState gameStep -> gameStep currentGameState) (gameState, gameEvents) 
                   [ HaskellGame.Gameplay.Simulator.processGameStateOutputEvents, 
                     HaskellGame.Physics.Simulator.applyPhysics frameDelay, 
                     HaskellGame.Physics.CollisionDetector.detectAndResolveCollisions frameDelay
  _ <- drawAction finalState

  case state of
    True -> do 
      Graphics.UI.SDL.Time.delay 30
      gameLoop drawAction eventAction finalState currentTicks
    False -> return ()

Game State

The game loop applies phases that operate on different slices of data.  Well that was the theory at least, most of these update position information.  The original theory seemed to work well with what GEA calls a "pure component model" for game objects.  Entities in the game are just distinct components that are bound together by a unique identifier.

With that in mind, the GameState became mostly a collection of IntMaps from identifiers to game components:

type BoundingBoxState = Data.IntMap.Lazy.IntMap BoundingBox

type PhysicsState = Data.IntMap.Lazy.IntMap VelocityAcceleration

type WorldState = Data.IntMap.Lazy.IntMap Position

type AnimationStates = Data.IntMap.Lazy.IntMap AnimationClip

type RenderingHandlers = Data.IntMap.Lazy.IntMap RenderingHandler

type ActorStates = Data.IntMap.Lazy.IntMap ActorState

data GameState = GameState { worldState :: WorldState, 
                             _resources :: GraphicResources, 
                             actorStates :: ActorStates, 
                             boundingBoxState :: BoundingBoxState,
                             _animationStates :: AnimationStates,
                             renderingHandlers :: RenderingHandlers, 
                             _font :: Font }

I was trying to push the design a bit to see where it breaks by separating Position and VelocityAcceleration.  A funny thing came out of it, I can omit the VelocityAcceleration component of platforms and the physics phase won't be able to move them.

Originally I initialized each of the maps separately, but calling code that adds entities will usually want to define all of the components together.  First I added a union type to work with the cases, but later, I added a convenience typeclass.  I've been trying to avoid using a lot of typeclasses but this one seemed to work out well.

{-# LANGUAGE TypeSynonymInstances, FlexibleInstances #-}
module HaskellGame.Game where

-- .... snipped code

data GameComponent = PositionComponent Position 
                       | CollisionComponent BoundingBox 
                       | PhysicsComponent VelocityAcceleration 
                       | RenderingComponent RenderingHandler 
                       | ActorComponent ActorState
                       | AnimationComponent AnimationClip

class GameComponentStore a where
    toComponent :: a -> GameComponent

instance GameComponentStore Position where
    toComponent = PositionComponent 

instance GameComponentStore BoundingBox where
    toComponent = CollisionComponent 

instance GameComponentStore VelocityAcceleration where
    toComponent = PhysicsComponent 

instance GameComponentStore RenderingHandler where
    toComponent = RenderingComponent 

instance GameComponentStore ActorState where
    toComponent = ActorComponent 

instance GameComponentStore AnimationClip where
    toComponent = AnimationComponent 

This makes entity definition a lot easier since the caller does not need to know the union constructor names.

initializeGameState :: GameState -> GameState
initializeGameState gameState = 
    insertEntities gameState [GameEntity randomSquareId [toComponent (BoundingBox 0 0 10 10), 
                                              toComponent (Position 300 5),
                                              toComponent HaskellGame.Rendering.Renderer.rectRenderer ],
                              GameEntity playerId [toComponent $ Position 5 5,
                                                    toComponent $ VelocityAcceleration {vx = 0, vy = 0.00, ax = 0, ay = 0.0002},
                                                    toComponent $ BoundingBox 0 0 66 92,
                                                    toComponent $ Idle,
                                                    toComponent $ HaskellGame.Rendering.Renderer.animatedRender,
                                                    toComponent $ AnimationClip {_resourceId = playerId, _startTime = 0, _rate = 125}
                              GameEntity floorId  [toComponent $ Position 0 400,
                                                     toComponent $ HaskellGame.Rendering.Renderer.rectRenderer,
                                                     toComponent $ BoundingBox 0 0 640 10
                              GameEntity platformId  [toComponent $ Position 500 300,
                                                     toComponent $ HaskellGame.Rendering.Renderer.rectRenderer,
                                                     toComponent $ BoundingBox (-25) (-25) 50 50


This structure should lead to easier tests, one nice thing is that only the components that are being tested need to be added to the test case.

I've only made two HUnit tests so far, specifically for this blog post, but I hope to add more as it goes:

ts :: Test
tests = TestList [   
    TestLabel "AccelTest"
            (do  let intialGameState = HaskellGame.Types.emptyGameState
                 let playerEntityId = 201404
                 let playerEntity = GameEntity playerEntityId [toComponent $ Position 5 5,
                                                         toComponent $ VelocityAcceleration {vx = 0, vy = 0.00, ax = 0, ay = 0.0002},
                                                         toComponent $ BoundingBox 0 0 66 92]
                 let gameState = insertEntity intialGameState playerEntity
                 let physicsTimeInterval = 1000
                 let (gameStateAfterPhysics, _) = HaskellGame.Physics.Simulator.applyPhysics physicsTimeInterval (gameState, HaskellGame.Types.emptyGameEventQueues)
                 let positionAfterPhysics = Data.IntMap.Lazy.lookup playerEntityId $ worldState gameStateAfterPhysics
                 assertEqual "Force was applied" (Just $ Position 5 205) positionAfterPhysics)
    TestLabel "Collision Test"
            (do  let intialGameState = HaskellGame.Types.emptyGameState
                 let playerEntityId = 20140401
                 let playerEntity = GameEntity playerEntityId [toComponent $ Position 5 5,                                                         
                                                         toComponent $ BoundingBox 0 0 10 10]
                 let enemyEntityId = 20140402
                 let enemyEntity = GameEntity enemyEntityId [toComponent $ Position 5 5,                                                         
                                                         toComponent $ BoundingBox 0 0 5 5]
                 let gameState = insertEntities intialGameState [playerEntity, enemyEntity]
                 let [((collisionEntityA,_,_), (collisionEntityB,_,_)) ] = HaskellGame.Physics.CollisionDetector.collisions gameState
                 assertEqual "Collisions detected" (playerEntityId, enemyEntityId) (collisionEntityA, collisionEntityB))

HUnit produces pretty decent errors, wondering if something like Hamcrest would help though.


### Failure in: 0:AccelTest               
Force was applied
expected: Just (Position {_x = 1, _y = 205})
 but got: Just (Position {_x = 5, _y = 205})
### Failure in: 1:Collision Test          
Collisions detected
expected: (20140401,20140403)
 but got: (20140401,20140402)
Cases: 2  Tried: 2  Errors: 0  Failures: 2

Next steps and general impressions

I've implemented the basics of an animation system, an animation clip points to an array of images, but now the current game time needs to be threaded through the GameState, which will be also be needed to pause and save the game.  Eventually the clips will have to change based on changes to entity states, but because the animation frame is just a function of the current time and the start time of the clip, AnimationClip itself does not need to change.  This could help for background elements that just repeat a single animation cycle.

Having Int typed time is also inconvenient in a lot of places so I'll have to think about how to change it.

I cheated to play around with animation by adding a separate SDL getTicks call in the animation handler.  It's definitely wrong, but I've found it's kind of nice to have IO pockets here and there to cheat a bit, as long as it's clear that it's happening.


data AnimationClip = AnimationClip { _resourceId :: GameEntityIdentifier , _startTime :: Int, _rate :: Int }

So far I've been pretty happy with the project, and I haven't gotten really stuck at this early stage.  Refactoring to move the individual phases into different modules cleared a lot of things up and I've learned a lot.  I've been trying to prefer constructs that reduce the impact of changes over those that produce shorter code, though it's more of a feeling that I can't put into writing at the moment.

Changes are starting to get easier, and are starting to feel more localized.  Pattern matching is awesome but sometimes it feels like it introduces too much coupling.  Naming record fields with underscores got rid of a lot of compiler warnings, though there are still a lot left to clean up.

Eventually I need to work through a full usage of the event passing mechanism for some more involved game mechanics, work on saving the game, better resource loading, menu screen, then loading/storing levels and more.

I guess I'm saying if you're looking for a Haskell side project, a game engine will definitely burn some cycles :)