Game programming patterns; Game Loop; Etc

[JasonJAyalaP]

I've been reading an online book about game programming patterns. Even though it's imperative and definitely not FRP, it raises issues that any game must solve. One of those is the game loop. I'd like to compare his suggestion with what we've been doing, and get your feedback. Sorry for rambling.

http://gameprogrammingpatterns.com/game-loop.html

My understanding of the game loop as described in the Elm pong blog post is something like:

- Every so many milliseconds (that is, the time Delta, based on desired max framerate)

  - Get current Input

  - Update game, with that Input, *using the Delta to stretch/adjust as necessary*

  - Render game

Is this the standard FRP way of handling the game loop? This seems to fall somewhere between the optimal way (as described in the book) and the second best.

The second best way is described as:

- Loop

  - Get time since last loop (delta)

  - Get Input

  - Update using delta

  - Render

In our FRP games (`foldp update intialGame input` -- where input is a signal updated at a predetermined Time Signal -- is essentially the "loop") and this imperative loop I've just described, "Slow" players are accommodated with jerkier updates and rendering. In our FRP, "Faster" players are given the predetermined max FPS. In the imperative, they're given as smooth an experience as their computer is capable (no fixed maximum). Not a huge problem, I don't think.

Our "loop" is sampled 60 (or whatever) frames per second (ie `sampleOn delta input`) -- as opposed to "loop as fast as you can and calculate delta".

Now, the argument against the these "flexible" (my term) update versions -- that is, Update(delta) -- is that it may move the ball (or whatever) by 100 in one iteration, but by 57 in the next (because you never know the exact delta). The author argued that this causes havoc with AI, multiplayer, etc. 

---

My understanding of the author's best (imperatively speaking) game loop

- Set Fixed update interval constant in milliseconds (based loosely on desired *minimal* framerate)

- Loop

  - Calculate Lag variable based on Fixed interval constant + time since last loop

  - Get input

  - Update (No delta. Update function knows of fixed size and always "moves" the game the same amount)

    - Lag = Lag minus Fixed

    - Run Update again if lag is too high, repeat *just the* Update function until lag cleared

  - Render (Ideally with offset (Lag divided by Fixed) to help visual issues)

The big difference is that it: 1. Separates rendering from updating 2. Update always moves the same amount.

I have no idea if this has anything to teach us.

----

P.S.

While you're there, do checkout the chapters on update and state (automata)

http://gameprogrammingpatterns.com/update-method.html

In Haskell, you might make your game objects part of the Update and Render typeclass. In Elm, would the game objects be extensible records with an update function meant to be called on itself?

http://gameprogrammingpatterns.com/state.html

Games need menus. Maybe state machines is the best way do this? Just thinking out loud.

[Joseph Collard]

This is pretty much what my Playground library is attempting to do. It attempts to abstract away the Signals so you can focus on writing your game.

Some examples here: https://github.com/jcollard/elm-playground

--
You received this message because you are subscribed to the Google Groups "Elm Discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elm-discuss...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Zinggi]

You should also read this article (in fact the whole series). It basically describes the same thing, but it goes a bit more in detail.

I’d also be interested how one could implement such a gameloop in Elm. It seems very difficult…

[Jeff Smits]

Here's an example of a little fixed timestep game. I hacked this together quickly, so I apologise for the messy code.
The red dot moves to your cursor like there is a spring attached to it. There is no dampening of movement so if you don't move the mouse the dot will accelerate toward the upper left corner and come back later because it overshot the default Mouse.position at the corner.

I log the timeCount' value, so you can see in the developer console that the fps is usually above the timestep (although performance degrades when you have the console open).

BTW: I think this could be written much easier and more nicely decomposed if we had signal loops.

--

[Zinggi]

Could you explain that code a bit more? Which of these techniques mentioned in the article does this implement?

Fixed time step with no synchronization? Fixed time step with synchronization? Fixed update time step, variable rendering?

Also what does the default fps signal implement? It look like Variable time step with an upper limit, which would be pretty bad for games.

Wouldn't it be better to have a designated game loop signal directly implemented in Javascript, probably with RequestAnimationFrame? I think that's the best option on browsers for a smooth game loop.

[Zinggi]

This Javascript snippet looks like pretty much what we want. Can we create a native js function that takes an elm function? (In this case update and render)
I know we can pass around values to js, but can we pass over functions?

var now,
    dt   = 0,
    last = timestamp(),
    step = 1/60;

function frame() {
    now = timestamp();
    dt = dt + Math.min(1, (now - last) / 1000);
    while(dt > step) {
        dt = dt - step;
        update(step);
    }
    render(dt);
    last = now;
    requestAnimationFrame(frame);
}

requestAnimationFrame(frame);

Am Dienstag, 1. Juli 2014 03:20:03 UTC+2 schrieb JasonJAyalaP:

[Dandandan]

I thought about this too. Currently it's not implemented the way you want it.

Some things to note

1: Diffs in Time signals create (rounding) errors, which can be corrected using your technique.

2: Elm uses setTimeOut instead of requestAnimationFrame. requestAnimationFrame is much better for smooth rendering by trying to sync with the monitor. Even with 60fps, setTimeOut doesn't look smooth. Also with lower fps it still looks nice because of that. Maybe it would be nice to have a signal like requestAnimationFrame.

3: Renderer in Elm is currently quite slow.

You could try to implement this function? You only need to define a signal in JavaScript, the rest you could all do in Elm.

frame : Signal Time

frame = Native.frame

JavaScript implementation of this function probably looks like:

function frame() {
  var time = Signal.constant(Date.now());
  function update() {
    elm.notify(time.id, Date.now());

    requestAnimationFrame(frame);
  }
  requestAnimationFrame(update);
}

This is how the time signals are implemented  now in Elm.

Op dinsdag 1 juli 2014 21:49:19 UTC+2 schreef Zinggi:

[John Mayer]

I thought we already did animation frame?

--

[Zinggi]

Well this implementation doesn’t solve most problems we have with the current implementation.
While I agree that it is better than SetTimout, it would only really work well for animations, not game logic.

The snippet I posted before shows a nice logic loop / render loop combination, but it doesn’t really fit in the concept of signals. We would need two signals that way, one for rendering and one for logic.
However, I don’t know if we could then combine those nicely in elm.

[Jeff Smits]

Fixed is the fixed time variable, used in the logic function to do deterministic updates.
The loop function expresses the functionality the OP and that blog post you linked to describe as the best way: accumulate timesteps, when the accumulated value is higher than the fixed time value do an update, subtract the fixed time from the accumulated value, loop again.

Focus on the loop function, ignore the rest of the code. That's just to have a compiling example.

[Zinggi]

Thanks, I understand it better know. Now I only need to puzzle through the main function. (I'm still quite new to elm)

So your solution seems to work, but it's obviously quite slow, a native js implementation would be better

[Evan Czaplicki]

Rendering is done with requestAnimationFrame. every is done with setInterval and fps is done with setTimout that automatically does smoothing to try to achieve the desired rate based on how your logic is doing.

Seems like dropWhen could be used to skip rendering. Pair that with every and it seems like you can achieve the ideal loop.

I feel like a lot of the performance claims in this thread are dubious. I'd be curious if elm-benchmark can help us assess this in a data driven way.

[Dylan Sale]

I was looking at doing a "fix your timestep" style accumulator a while ago. It is very out of date now, but you can see the thread about at at https://groups.google.com/forum/#!msg/elm-discuss/ZwwivXw3w-I/GK0Fm11b2qEJ

Dylan Sale

[Zinggi]

That won’t solve the main problem we have, that is to have a (strictly) constant deltaTime value for the logic loop. Both every and fps do not provide a constant, deterministic deltaTime value. (Because both setInterval or setTimeout are absolutely not reliable)
This works fine for many games, but for games with multiplayer, physics based games or games that react to music, a non deterministic deltaTime leads to too many problems.

 Rendering is done with requestAnimationFrame

Does that mean that no matter how fast (or slow) we think we are drawing to main, it always updates at the same rate? (Which would be a good thing)

So for me it seems like the best solution would be to change the fps signal to be this part of the js snippet:

var now,
    dt   = 0

,
    last = timestamp(),
    step = 1/60;    // here we would plug in the argument of fps x: step = 1/x

function frame() {
    now = timestamp();
    dt = dt + Math.min(1, (now - last) / 1000);
    while

(dt > step) {
        dt = dt - step;
        update(step);   // This should trigger the fps signal.
                        // The argument 'step' isn't really necessary
                        // (because we know it's value), but for simplicity and
                        // backwards compatibility we could still provide it.
    }
    // Elm would render the scene for us here. Using dt, Elm could now linearly interpolate
    // between the last frame and the current one.

    render(dt);

    last = now;
    requestAnimationFrame(frame);
}
requestAnimationFrame(frame);

To unsubscribe from this group and stop receiving emails from it, send an email to elm-discuss+unsubscribe@googlegroups.com.

​

[Evan Czaplicki]

I think I get it... So there could be a value like this:

renderComplete : Signal Float

Where the values are time deltas indicating the time since the last frame was caused by a renderComplete event. Given that as an input, you could do the smoothing you describe where you step as many times as it takes to match up with the time delta.

Sound correct?

P.S. I'm not sure loops would cover this because it needs to be hooked up to requestAnimationFrame to pump values through the cycle correctly.

 Rendering is done with requestAnimationFrame

Does that mean that no matter how fast (or slow) we think we are drawing to main, it always updates at the same rate? (Which would be a good thing)

Yeah, you only do one render at most. So if you ask for 10 view updates, the most recent one will win when requestAnimationFrame actually runs, the others are ignored because we know the render code is pure.

[Dylan Sale]

To keep it in line with the existing API, I proposed an "every frame" signal in the other thread I linked that used requestAnimationFrame instead of setInterval.

Ultimately I ended up just using "every millisecond" (which actually just runs every 16ms - on each frame - on Chrome and Firefox anyway), so a new API might not be necessary.

Dylan Sale

--

[Zinggi]

@Evan:

Yes that sounds correct. We could roll our own update loop in elm then, that should work. Also it would be better for animation too, because requestAnimationFrame was exactly designed for that.

There is just a small problem, that is you can't nicely separate that signal from the main rendering loop anymore.

Not really a problem, but that might mean that you might not be able to put it in the time module anymore.

@ Dylan:

"every frame" sounds like a good name, +1.

"every millisecond" Just seems to run at a constant 16ms, but the times aren't stable enough for games that require reproducibility or accurate physics. I made that mistake once in a music based game I made in JavaScript and run into this issue. After playing for about one minute, the music and gameplay weren't in sync anymore. At that time I had no idea how to fix this, but as I know now, a fixed timestamp would have fixed it.

[Dylan Sale]

Yeah you still need to implement an accumulator for the "every millisecond" or "every frame" solution.    I agree that locking it to the render (requestAnimationFrame) is best because you avoid the interval timer becoming out of sync with the frames. I'm not sure that actually happens in modern browsers, but even if it doesn't, it is relying on nonstandard behaviour.

Dylan Sale

[Alexander Foremny]

I have been tinkering with a game in Elm for a while and wanted to share my experience. I second the conclusion that render and update (step) should be decoupled. Games are performance critical applications and even in a well-designed game, the update function requires a lot of CPU cycles still. However, updating the state does not have to be done nearly as frequently as rendering, ie. update rates of 100ms (10 FPS) are common, while frame rates should aim for something like 13 ms (72 FPS). To fake a smooth animation of the game state, one should take the last two snapshots of the game state and interpolate (linearly) between them. In practice interpolating is notably cheaper than applying the update function.

As an added benefit the update function does not need the time delta anymore, and thus you do not have to account for time deltas that are too small or too large.

In (untested) pseudo code, my skeleton application looks like this:

> main : Signal Element

> main = Signal.map view (Signal.map2 interpolate currentTime (Signal.sampleOn frameRate snapshot))

>

> type alias Snapshot =

>   { lastState : Model

>   , currentState : Model

>   }
>

> snapshot : Signal Snapshot

> snapshot =

>   let

>     f newCurrent { currentState } =

>       { lastState = currentState, currentState = newCurrent }

>   in

>     Signal.foldp f { lastState = initialModel, currentState = initialModel } model

>

> model : Signal Model

> model = Signal.foldp update initialModel (Signal.sampleOn tickRate input)
>

> tickRate, frameRate, currentTime : Signal Time

> tickRate = Time.fps 10

> frameRate = AnimationFrame.frame

> currentTime = Signal.foldp (+) 0 frameRate
>

> interpolate : Time -> Snapshot -> Model

>
> update : Input -> Model -> Model
>

> view : Model -> Element

>

> input : Signal Input

Note that Model has to have a field that tells the time it was updated so that you can compute the time difference in interpolate. Instead of Input being a series of key presses, key presses should be folded into a data structure that tells you what keys are pressed now, and which are not.

If you let your update function take a time delta still and set it to a fixed 10 ms in the model declaration, you can disable interpolation by just calling update (with the variable time delta). This does not make any sense performance wise, but it is an easy way to test changes in the update function without adapting interpolate to those changes first.

PS. Sampling input on tickRate symbolizes that the costly update function is run only every tick. Usually you want to have other inputs which are not sampled on tickRate, and have cheap update functions.

2015-08-02 5:13 GMT+02:00 Duncan Fairbanks <bonsa...@gmail.com>:

I tried adapting Jeff's demo to use WebGL and linear interpolation for a comparison. I'm not sure how to measure the framerate, but at least I can't notice any stuttering. The movement doesn't look too great, but I assume that's because of the high contrast between the triangle and the background.

Here's the code:

-- Try adding the ability to crouch or to land on top of the crate.

import Graphics.Element exposing (..)

import Http exposing (..)

import Keyboard

import Math.Vector2 exposing (Vec2)

import Math.Vector3 exposing (..)

import Math.Vector3 as V3

import Math.Matrix4 exposing (..)

import Task exposing (Task)

import Text

import Time exposing (..)

import WebGL exposing (..)

import Window

-- MODEL

type alias Person =

    { position : Vec3

    , velocity : Vec3

    }

type alias Inputs =

    ( Bool, {x:Int, y:Int}, Float )

eyeLevel : Float

eyeLevel = 2

defaultPerson : Person

defaultPerson =

  { position = vec3 0 eyeLevel -10

  , velocity = vec3 0 0 0

  }

-- UPDATE

update : Inputs -> Person -> Person

update (isJumping, directions, dt) person =

  person

    |> walk directions

    |> jump isJumping

    |> gravity dt

    |> physics dt

walk : { x:Int, y:Int } -> Person -> Person

walk directions person =

  if getY person.position > eyeLevel then

    person

  else

    let

      vx = toFloat -directions.x

      vz = toFloat  directions.y

    in

      { person |

          velocity <- vec3 vx (getY person.velocity) vz

      }

jump : Bool -> Person -> Person

jump isJumping person =

  if not isJumping || getY person.position > eyeLevel then

    person

  else

    let

      (vx,_,vz) = toTuple person.velocity

    in

      { person |

          velocity <- vec3 vx 2 vz

      }

physics : Float -> Person -> Person

physics dt person =

  let

    position =

      person.position `add` V3.scale dt person.velocity

    (x,y,z) = toTuple position

  in

    { person |

        position <-

            if y < eyeLevel then vec3 x eyeLevel z else position

    }

gravity : Float -> Person -> Person

gravity dt person =

  if getY person.position <= eyeLevel then

    person

  else

    let

      v = toRecord person.velocity

    in

      { person |

          velocity <- vec3 v.x (v.y - 2 * dt) v.z

      }

-- SIGNALS

world : Maybe Texture -> Mat4 -> List Entity

world maybeTexture perspective =

  case maybeTexture of

    Nothing ->

        []

    Just tex ->

        [entity vertexShader fragmentShader crate { crate=tex, perspective=perspective }]

main : Signal Element

main =

  let

    person =

      Signal.foldp update defaultPerson inputs

    entities =

      Signal.map2 world

        texture.signal

        (Signal.map2 perspective Window.dimensions person)

  in

    Signal.map2 view Window.dimensions entities

texture : Signal.Mailbox (Maybe Texture)

texture =

  Signal.mailbox Nothing

port fetchTexture : Task WebGL.Error ()

port fetchTexture =

  loadTexture "/texture/woodCrate.jpg"

    `Task.andThen` \tex -> Signal.send texture.address (Just tex)

inputs : Signal Inputs

inputs =

  let

    dt = Signal.map (\t -> t/500) (fps 25)

  in

    Signal.map3 (,,) Keyboard.space Keyboard.arrows dt

      |> Signal.sampleOn dt

-- VIEW

perspective : (Int,Int) -> Person -> Mat4

perspective (w,h) person =

  mul (makePerspective 45 (toFloat w / toFloat h) 0.01 100)

      (makeLookAt person.position (person.position `add` k) j)

view : (Int,Int) -> List Entity -> Element

view (w,h) entities =

  layers

    [ webgl (w,h) entities

    , container w 100 position message

    ]

position =

  midLeftAt (absolute 40) (relative 0.5)

message : Element

message =

  leftAligned <| Text.monospace <| Text.fromString <|

      "Walk around with a first person perspective.\n"

      ++ "Arrows keys to move, space bar to jump."

-- Define the mesh for a crate

type alias Vertex =

    { position : Vec3

    , coord : Vec3

    }

crate : List (Triangle Vertex)

crate =

  List.concatMap rotatedFace [ (0,0), (90,0), (180,0), (270,0), (0,90), (0,-90) ]

rotatedFace : (Float,Float) -> List (Triangle Vertex)

rotatedFace (angleXZ,angleYZ) =

  let

    x = makeRotate (degrees angleXZ) j

    y = makeRotate (degrees angleYZ) i

    t = x `mul` y

  in

    List.map (WebGL.map (\v -> {v | position <- transform t v.position })) face

face : List (Triangle Vertex)

face =

  let

    topLeft     = Vertex (vec3 -1  1 1) (vec3 0 1 0)

    topRight    = Vertex (vec3  1  1 1) (vec3 1 1 0)

    bottomLeft  = Vertex (vec3 -1 -1 1) (vec3 0 0 0)

    bottomRight = Vertex (vec3  1 -1 1) (vec3 1 0 0)

  in

    [ (topLeft,topRight,bottomLeft)

    , (bottomLeft,topRight,bottomRight)

    ]

-- Shaders

vertexShader : Shader { position:Vec3, coord:Vec3 } { u | perspective:Mat4 } { vcoord:Vec2 }

vertexShader = [glsl|

attribute vec3 position;

attribute vec3 coord;

uniform mat4 perspective;

varying vec2 vcoord;

void main () {

  gl_Position = perspective * vec4(position, 1.0);

  vcoord = coord.xy;

}

|]

fragmentShader : Shader {} { u | crate:Texture } { vcoord:Vec2 }

fragmentShader = [glsl|

precision mediump float;

uniform sampler2D crate;

varying vec2 vcoord;

void main () {

  gl_FragColor = texture2D(crate, vcoord);

}

|]

[Duncan Fairbanks]

Alexander,

You might find these gists of interest:

fixed delta time:

https://gist.github.com/bonsairobo/fe9b040ecc4c4bb8b940

variable delta time:

https://gist.github.com/bonsairobo/e4534d4ff00a6eab2e2f

They are my attempts at comparing fixed and variable dt simulations in Elm using WebGL. I doubt they're perfect, because I wrote them with only a couple days of Elm experience, but they illustrate my intent. Also, they seem to have some unfortunate performance issues for which I don't know the cause. It may be that, in Elm's current state, this technique is not trivial to optimize. I'd love to hear from any other users of elm-webgl if they see any improvements to be made to my code.