7 ms·

Purely Functional Retrogames (2008)

87 points by adgasf 10y ago

collyw 10y ago
This is cool. A lot of people tell us how great functional programming is (I can see the benefits of avoiding state not having side effects). But it is rare to see an article that shows how you go about designing something in that style.
vanderZwan 10y ago
> Back when I actually wrote 8-bit games, much of my code involved updating timers and counters used for animation and special effects and so on. At the time it made a lot of sense, given the limited math capabilities of a 6502. In the modern world you can achieve the same by using a single clock counter that gets incremented each frame. So just to demonstrate an IMO elegant approach for the destructive style for updates that depend on current time values: for each update, pretend all computation happens in an instant, specifically: at the moment an event triggered an update (this could be the central game loop, user input, etc). Doing so makes it easy to keep everything synchronised; it's the abstraction Céu uses to great effect for its synchronous concurrency model[0]. The only limitation is that you need to keep your updates small and fast enough to finish before the next update is triggered, but that's a good goal to strive for anyway. Pretending all computation happens instantly let's me use two values: a timestamp referencing to global time, and time difference with the previous time this update was triggered. Counters that get updated every time this update is triggered just increment by time difference. Counters that don't always get updated (or if different events can trigger the update) have to store the timestamp of the last update they were called, compute their own time-difference on the fly with a simple subtraction, update their value and store the new time-stamp. Very simple. Using timers just means checking if the updated value is more than a certain value, and if so subtract that value and call another function. Basically, incremental error algorithms[1], like it is applied in Bresenham's Line Algorithm[2], but for timers instead of slopes. (Note that this could all be written in a functional style with functions that take a current counter value and current/previous timestamp, returning a new counter value, but at that point it just feels like writing functional code imperatively) I often use this in my Arduino code. It speeds up my programs, because calls to millis() are not as cheap as referencing a global, and all we need computatationally with this approach are addition and subtraction, avoiding multiplication, division and modulo. More importantly it makes it much easier to reason about what is happening, because if all updates reference the same time-step, side effects are much more predictable. The aforementioned Céu language really takes this style of concurrency to heart in a very elegant way. [0] http://www.ceu-lang.org/ http://www.ceu-lang.org/ [1] https://en.wikipedia.org/wiki/Glossary_of_computer_graphics#incremental_error_algorithm https://en.wikipedia.org/wiki/Glossary_of_computer_graphics#... [2] https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm
- w0utert 10y ago
  >> Doing so makes it easy to keep everything synchronised; it's the abstraction Céu uses to great effect for its synchronous concurrency model[0]. The only limitation is that you need to keep your updates small and fast enough to finish before the next update is triggered, but that's a good goal to strive for anyway. I think the usual way games typically implement more or less what you are describing but without the hard-realtime update constrains, is what is commonly referred to as a 'fixed timestep'. It's what I used to implement the main loop of the game I'm currently working on, which has an 'action replay' function that has to be capable of producing the exact same gameplay sequence based on recorded input events, which means 100% accurate, discrete and predictable updates to the game state. It's pretty cool to record some gameplay on actual hardware, then replay it in the simulator, which has completely different performance characteristics, and get a pixel-perfect reproduction of the gameplay clip :-). Extremely useful for gameplay debugging and prototyping as well. There's a nice article here [1] that explains the concept much better than I could, so I'll just refer to that instead ;-) [1] http://gafferongames.com/game-physics/fix-your-timestep/ http://gafferongames.com/game-physics/fix-your-timestep/
  - vanderZwan 10y ago
    > It's pretty cool to record some gameplay on actual hardware, then replay it in the simulator, which has completely different performance characteristics, and get a pixel-perfect reproduction of the gameplay clip :-). Extremely useful for gameplay debugging and prototyping as well. Yeah, determinism in programming seriously rocks! BTW, I think what I described was the variable delta time, not the fixed time step. That semi-fixed time-step looks pretty interesting too!
rwmj 10y ago
This is my pure-functional Katamari "game" (more of an outline / example, than a full-blown game): https://github.com/fccm/OCamlODE/blob/master/examples/katamari.ml https://github.com/fccm/OCamlODE/blob/master/examples/katama...
zaro 10y ago
Maybe it's just me but I find the part about structures a bit silly. So let's get rid of the big fat structs, and replace them with tuples. Nested tuples. How is that any different than a struct, apart from immutability? And it is worsened by the fact that the fields now are just indexes in a tuple/list instead of being named.
- bunderbunder 10y ago
  I think I'd go for records over tuples, so that the values can be named.
  - douche 10y ago
    If you're using a record, you're effectively just using a struct again...
    - haasn 10y ago
      Mathematically, structs and tuples are virtually equivalent. They are both examples of the same fundamental data construct: Product types (i.e. grouping multiple values together) The other two most important abstractions are sum types, i.e. unions or alternatives, and exponent types, i.e. function types, and IMO they're the two that are far more important for the success of functional programming.
    - bunderbunder 10y ago
      I think that one depends on the language. In F#, for example, records are pass-by-reference and structs are pass-by-value. In a language-unspecified setting I like to follow the convention that structs are implied to be mutable data types and records are implied to be immutable data types. I don't know how widely-used that convention is, though.
- pmarreck 10y ago
  I think the design of this part depends on how well your functional language of choice implements immutable data structures, from a performance and memory consumption (and by inference, garbage collection) perspective.
ceronman 10y ago
> An open question is "Is being purely functional, even excepting I/O, worthwhile?" Or is it, as was suggested to me via email earlier this year, the equivalent of writing a novel without using the letter 'e'? This is a great question. I've been playing with pure functional programming, and I also noticed that applying it to video games is very hard. In other areas, FP provides many advantages such as testability and safe parallel execution. But for simple games these are not that useful. Simple games seem very well suited for the imperative, global state model. There is one aspect that might make FP worth it for games and it's interactive programming. The immediate feedback loop described by Bret Victor [1], with the possibility of going back and forth in time is easier to achieve with a pure functional approach. The Elm debugger [2] is an implementation of this concept, using hot swapping and functional reactive programming it's possible to design games interactively in a very unique way that it's hardly achieved with the traditional imperative approach. [1] https://www.youtube.com/watch?v=PUv66718DII https://www.youtube.com/watch?v=PUv66718DII [2] http://debug.elm-lang.org/ http://debug.elm-lang.org/
- Peaker 10y ago
  > But for simple games these are not that useful. Simple games seem very well suited for the imperative, global state model. I think this indicates a bias -- resulting from years of programming games in these models. I think pure FP in the form of FRP is a far better match for simple games than the imperative, global state model.
- the_af 10y ago
  > But for simple games these are not that useful. Simple games seem very well suited for the imperative, global state model. Could you elaborate? I think this is one of those things we "know" which isn't necessarily so. Simple sprite-based games can be written using purely functional techniques (see: https://github.com/nikki-and-the-robots/nikki https://github.com/nikki-and-the-robots/nikki). It's just that it's not common to use FP languages for this.
  - ceronman 10y ago
    Yeah, I know you can develop games in a purely functional fashion. My point what is the advantage of doing so, given that most resources are developed for an imperative way. I think the interactive approach taken by Elm is a very good advantage of FP for games.
Peaker 10y ago
It seems at least some of the difficulties described are managed better in Haskell. For example, rebinding to the same name (as an alternative to destructive update) can be handled conveniently and nicely via state monad and the lens library, with syntax roughly like: pacman.position += speed This is still purely functional because the resulting type is roughly: State Game () which is equivalent to: (Game -> Game) (a pure function that takes a game and returns a modified game).
- jstimpfle 10y ago
  > This is still purely functional because the resulting type is roughly: State Game () which is equivalent to: (Game -> Game) (a pure function that takes a game and returns a modified game). This is the kind of arguing that could easily be extended to C and other "impure" languages. And even the IO monad is "pure" -- it's just values containing computations executed by the runtime (i.e. the computational side-effects are not part of the language / type system) Using the State Monad for += syntax is no better than doing the equivalent in C. The real enemy is accidental state. That is, meaningless (but significant) dependencies between conceptually independent calculations. For example: pacman.position += speed pacman.lives = ghostAt pacman.position While updating the position based on the speed and deciding whether pacman was hit by a ghost are conceptually independent, the outcome of the above code is dependent on the order of these lines. Instead it's often cleaner to do something along the lines of pacmanLives :: Pacman -> Ghosts -> Bool pacmanNewPosition :: Pacman -> Position -- use both of these functions in the update routine. -- Hand them the pacman from the last frame -- (i.e. don't "chain" the functions) This way a dependency on the "order" of these computations is "avoided" (kind-of. There is still an order between the frames, but that is not as "accidental").
  - Peaker 10y ago
    You cannot implicitly read pacman.position as a subexpression like in C, because it is an effect, and the order of effects has to be explicit in Haskell. So it would have to look like: pacman.position += speed pos <- pacman.position g <- ghostAt pos pacman.lives .= g Though a dead Pacman probably has no position, so it makes more sense that the last line is: when g (pacman .= DeadPacman) Messing up the order because of implicitness becomes much harder.
haasn 10y ago
Two links that come to mind: - https://github.com/ocharles/netwire-classics https://github.com/ocharles/netwire-classics - https://github.com/ekmett/lens/blob/master/examples/Pong.hs https://github.com/ekmett/lens/blob/master/examples/Pong.hs

87 points by adgasf 10y ago

This is cool. A lot of people tell us how great functional programming is (I can see the benefits of avoiding state not having side effects). But it is rare to see an article that shows how you go about designing something in that style.

vanderZwan 10y ago

> Back when I actually wrote 8-bit games, much of my code involved updating timers and counters used for animation and special effects and so on. At the time it made a lot of sense, given the limited math capabilities of a 6502. In the modern world you can achieve the same by using a single clock counter that gets incremented each frame. So just to demonstrate an IMO elegant approach for the destructive style for updates that depend on current time values: for each update, pretend all computation happens in an instant, specifically: at the moment an event triggered an update (this could be the central game loop, user input, etc). Doing so makes it easy to keep everything synchronised; it's the abstraction Céu uses to great effect for its synchronous concurrency model[0]. The only limitation is that you need to keep your updates small and fast enough to finish before the next update is triggered, but that's a good goal to strive for anyway. Pretending all computation happens instantly let's me use two values: a timestamp referencing to global time, and time difference with the previous time this update was triggered. Counters that get updated every time this update is triggered just increment by time difference. Counters that don't always get updated (or if different events can trigger the update) have to store the timestamp of the last update they were called, compute their own time-difference on the fly with a simple subtraction, update their value and store the new time-stamp. Very simple. Using timers just means checking if the updated value is more than a certain value, and if so subtract that value and call another function. Basically, incremental error algorithms[1], like it is applied in Bresenham's Line Algorithm[2], but for timers instead of slopes. (Note that this could all be written in a functional style with functions that take a current counter value and current/previous timestamp, returning a new counter value, but at that point it just feels like writing functional code imperatively) I often use this in my Arduino code. It speeds up my programs, because calls to millis() are not as cheap as referencing a global, and all we need computatationally with this approach are addition and subtraction, avoiding multiplication, division and modulo. More importantly it makes it much easier to reason about what is happening, because if all updates reference the same time-step, side effects are much more predictable. The aforementioned Céu language really takes this style of concurrency to heart in a very elegant way. [0] http://www.ceu-lang.org/ http://www.ceu-lang.org/ [1] https://en.wikipedia.org/wiki/Glossary_of_computer_graphics#incremental_error_algorithm https://en.wikipedia.org/wiki/Glossary_of_computer_graphics#... [2] https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm

w0utert 10y ago
>> Doing so makes it easy to keep everything synchronised; it's the abstraction Céu uses to great effect for its synchronous concurrency model[0]. The only limitation is that you need to keep your updates small and fast enough to finish before the next update is triggered, but that's a good goal to strive for anyway. I think the usual way games typically implement more or less what you are describing but without the hard-realtime update constrains, is what is commonly referred to as a 'fixed timestep'. It's what I used to implement the main loop of the game I'm currently working on, which has an 'action replay' function that has to be capable of producing the exact same gameplay sequence based on recorded input events, which means 100% accurate, discrete and predictable updates to the game state. It's pretty cool to record some gameplay on actual hardware, then replay it in the simulator, which has completely different performance characteristics, and get a pixel-perfect reproduction of the gameplay clip :-). Extremely useful for gameplay debugging and prototyping as well. There's a nice article here [1] that explains the concept much better than I could, so I'll just refer to that instead ;-) [1] http://gafferongames.com/game-physics/fix-your-timestep/ http://gafferongames.com/game-physics/fix-your-timestep/
- vanderZwan 10y ago
  > It's pretty cool to record some gameplay on actual hardware, then replay it in the simulator, which has completely different performance characteristics, and get a pixel-perfect reproduction of the gameplay clip :-). Extremely useful for gameplay debugging and prototyping as well. Yeah, determinism in programming seriously rocks! BTW, I think what I described was the variable delta time, not the fixed time step. That semi-fixed time-step looks pretty interesting too!

rwmj 10y ago

This is my pure-functional Katamari "game" (more of an outline / example, than a full-blown game): https://github.com/fccm/OCamlODE/blob/master/examples/katamari.ml https://github.com/fccm/OCamlODE/blob/master/examples/katama...

zaro 10y ago

Maybe it's just me but I find the part about structures a bit silly. So let's get rid of the big fat structs, and replace them with tuples. Nested tuples. How is that any different than a struct, apart from immutability? And it is worsened by the fact that the fields now are just indexes in a tuple/list instead of being named.

bunderbunder 10y ago
I think I'd go for records over tuples, so that the values can be named.
- douche 10y ago
  If you're using a record, you're effectively just using a struct again...
  - haasn 10y ago
    Mathematically, structs and tuples are virtually equivalent. They are both examples of the same fundamental data construct: Product types (i.e. grouping multiple values together) The other two most important abstractions are sum types, i.e. unions or alternatives, and exponent types, i.e. function types, and IMO they're the two that are far more important for the success of functional programming.
  - bunderbunder 10y ago
    I think that one depends on the language. In F#, for example, records are pass-by-reference and structs are pass-by-value. In a language-unspecified setting I like to follow the convention that structs are implied to be mutable data types and records are implied to be immutable data types. I don't know how widely-used that convention is, though.
pmarreck 10y ago
I think the design of this part depends on how well your functional language of choice implements immutable data structures, from a performance and memory consumption (and by inference, garbage collection) perspective.

ceronman 10y ago

> An open question is "Is being purely functional, even excepting I/O, worthwhile?" Or is it, as was suggested to me via email earlier this year, the equivalent of writing a novel without using the letter 'e'? This is a great question. I've been playing with pure functional programming, and I also noticed that applying it to video games is very hard. In other areas, FP provides many advantages such as testability and safe parallel execution. But for simple games these are not that useful. Simple games seem very well suited for the imperative, global state model. There is one aspect that might make FP worth it for games and it's interactive programming. The immediate feedback loop described by Bret Victor [1], with the possibility of going back and forth in time is easier to achieve with a pure functional approach. The Elm debugger [2] is an implementation of this concept, using hot swapping and functional reactive programming it's possible to design games interactively in a very unique way that it's hardly achieved with the traditional imperative approach. [1] https://www.youtube.com/watch?v=PUv66718DII https://www.youtube.com/watch?v=PUv66718DII [2] http://debug.elm-lang.org/ http://debug.elm-lang.org/

Peaker 10y ago
> But for simple games these are not that useful. Simple games seem very well suited for the imperative, global state model. I think this indicates a bias -- resulting from years of programming games in these models. I think pure FP in the form of FRP is a far better match for simple games than the imperative, global state model.
the_af 10y ago
> But for simple games these are not that useful. Simple games seem very well suited for the imperative, global state model. Could you elaborate? I think this is one of those things we "know" which isn't necessarily so. Simple sprite-based games can be written using purely functional techniques (see: https://github.com/nikki-and-the-robots/nikki https://github.com/nikki-and-the-robots/nikki). It's just that it's not common to use FP languages for this.
- ceronman 10y ago
  Yeah, I know you can develop games in a purely functional fashion. My point what is the advantage of doing so, given that most resources are developed for an imperative way. I think the interactive approach taken by Elm is a very good advantage of FP for games.

Peaker 10y ago

It seems at least some of the difficulties described are managed better in Haskell. For example, rebinding to the same name (as an alternative to destructive update) can be handled conveniently and nicely via state monad and the lens library, with syntax roughly like: pacman.position += speed This is still purely functional because the resulting type is roughly: State Game () which is equivalent to: (Game -> Game) (a pure function that takes a game and returns a modified game).

jstimpfle 10y ago
> This is still purely functional because the resulting type is roughly: State Game () which is equivalent to: (Game -> Game) (a pure function that takes a game and returns a modified game). This is the kind of arguing that could easily be extended to C and other "impure" languages. And even the IO monad is "pure" -- it's just values containing computations executed by the runtime (i.e. the computational side-effects are not part of the language / type system) Using the State Monad for += syntax is no better than doing the equivalent in C. The real enemy is accidental state. That is, meaningless (but significant) dependencies between conceptually independent calculations. For example: pacman.position += speed pacman.lives = ghostAt pacman.position While updating the position based on the speed and deciding whether pacman was hit by a ghost are conceptually independent, the outcome of the above code is dependent on the order of these lines. Instead it's often cleaner to do something along the lines of pacmanLives :: Pacman -> Ghosts -> Bool pacmanNewPosition :: Pacman -> Position -- use both of these functions in the update routine. -- Hand them the pacman from the last frame -- (i.e. don't "chain" the functions) This way a dependency on the "order" of these computations is "avoided" (kind-of. There is still an order between the frames, but that is not as "accidental").
- Peaker 10y ago
  You cannot implicitly read pacman.position as a subexpression like in C, because it is an effect, and the order of effects has to be explicit in Haskell. So it would have to look like: pacman.position += speed pos <- pacman.position g <- ghostAt pos pacman.lives .= g Though a dead Pacman probably has no position, so it makes more sense that the last line is: when g (pacman .= DeadPacman) Messing up the order because of implicitness becomes much harder.

haasn 10y ago

Two links that come to mind: - https://github.com/ocharles/netwire-classics https://github.com/ocharles/netwire-classics - https://github.com/ekmett/lens/blob/master/examples/Pong.hs https://github.com/ekmett/lens/blob/master/examples/Pong.hs