14 ms·

Honestly, is functional programming really better for this type of game? I find the structure and nature of the game more fitting to an object oriented approach

Honestly, is functional programming really better for this type of game? I find the structure and nature of the game more fitting to an object oriented approach. IMO Chips, blocks, player character all tend to be better described as mutable objects, because that's what they actually are from the users perspective....

crimsonalucard 12y ago
FYI I'm in no way challenging the impressive nature of making this game with Haskell. I'm just challenging the hype around the style and asking whether it really is the most efficient solution to programming a game...
- orclev 12y ago
  It isn't really about efficient, it's about making it simpler to reason about. Functional style is a different way of reasoning about state than OO, but they're both fundamentally about abstracting state and making it simpler to work with and reason about. OO takes the divide and conquer approach, by dividing state into progressively smaller chunks until each piece is small enough to reason about. The flaw with that is that at some level you need to understand and reason about the entirety of the state, and if you have a bug in some lower level piece it often exhibits as bad behavior in one of the higher level pieces. Figuring out which of the lower level pieces is ultimately responsible is 90%+ of the time spent on debugging in a OO program. Another challenge is that because state is mutable, just finding the starting point to debug the problem is often a chore because you must first get the system into the state necessary to trigger the bug. Even worse is that often the state you initially detect the bug in, is actually significantly further along than where the bug originates so you end up having to attempt to progressively walk backwards through time to arrive at the originating point (which in practice means running a debug session to a point, finding the next piece of state that looks wrong, setting new breakpoints, and then repeating the whole exercise). Functional programming takes a different tack by instead strongly discouraging state altogether. A well written functional program will contain only the absolute bare minimum state necessary to accomplish the task at hand. Further state tends to be divided into two distinct camps, the global state that's referenced by name (largely non-existent barring mutable IO refs and such), and the local state that's passed explicitly as function arguments (ignoring for the moment the monad abstraction around that). Like with OO you sometimes arrive at a point where behavior isn't what you expect it to be and need to go to a debugger to figure out where the state has deviated from the expected. Unlike in OO however you have the call stack to reference and can see exactly where in the history the problem originated. Finding the source of a bug in a large functional program tends to be rather trivial compared to the similar task in a large OO program, due to the more concise and limited state that exists in functional programs.
gamegoblin 12y ago
You just have to change the way you think about the game. Rather than viewing the game as a wholistic "Game" object which changes state as the game progresses, view it instead as a series of game states or frames which are immutable. Then you define a function that is like (in C-ish): GameState tick(GameState current, Action playerMove) { ... set up the next frame and return it ... } And a function to play like: void play() { play(initialState()); } void play(GameState current) { if(current.gameOver()) return; Action playerMove = getPlayerMove(); GameState next = tick(current, playerMove); play(next); // In Haskell and C on higher optimizations, this tail recursive call will get compiled to a loop } Of course it can get a bit more complicated depending on the context, but you get the idea. So I'd say functional programming is neither better nor worse. A lot of people get hung up on the idea of immutability, but really I've found it to be a non-issue.
lucian1900 12y ago
> Chips, blocks, player character all tend to be better described as mutable objects That is just one way to look at it. You could also say that they can all be described by the universe's state at a point in time. Then, you'd have a function that takes the old state and some actions to produce a new state, by recursively doing the same to each object within the universe.
- bpage 12y ago
  This wording sounds remarkably similar to quantum mechanics. I wonder how far you could take the idea of building a game out of state vectors and linear transformations.
  - Zeebrommer 12y ago
    State vectors and linear transformations are by no means unique to quantum mechanics. A lot of dynamic systems can be described this way: robot arms, chemical plants, airplanes, even network dynamics.
    - bpage 12y ago
      Naively I can guess how robot arms and networks could be spoken of in terms of states (and perhaps even chemical plants), but airplanes? Do you have any more information on the topic?
      - Zeebrommer 12y ago
        The technique is called a state space model [0]. A complete airplane might have been a bit hyperbolic, but as long as the assumption of linear dynamics is allowable, extremely large systems with multiple inputs and outputs and thousands of states can be simulated. What's more, there are some elegant and practical ways to find controllers with mathematically proven performance (like LQG control, or Model Predictive Control). This field of study has lead to the Kalman filter, which might ring a bell. 0: https://en.wikipedia.org/wiki/State_space_representation https://en.wikipedia.org/wiki/State_space_representation
ehurrell 12y ago
I think from a perspective of learning functional approaches it's useful to have things like this, as a more complex worked example of applying functional concepts to a problem. That is to say it seems like a broader version of "You know how in OO you made a 'Car' object with an 'Engine' with attributes and functions, well this is how it's done functionally".
mbrock 12y ago
Haskell is a general-purpose programming language, and discrete simulation-type systems like Chip's Challenge can be very elegantly modelled with nice things like algebraic data types, pattern matching, etc. The code is right there on GitHub, although if you're not familiar with Haskell (and lens), it might seem cryptic. But you'll see that it is actually mostly written in an imperative style. The logic is mostly pattern matching on events to generate record updates. This is a common style in Haskell and fits the domain well. There are other more elegantly value-oriented ways of writing simulations in Haskell; look up functional reactive programming.
Dewie 12y ago
I know, right? This here is a classic example of a nail, so why wouldn't I use my trusty hammer..
lmm 12y ago
There are some advantages to thinking this way. You get replay functionality "for free" (even if you never expose this to users, it makes debugging much easier), and it becomes much easier to think about how the game will work in a network situation (where each client has its own "copy" of the world, and the two copies might be "out of sync"). I've written initially-imperative games that became more and more functional as I started to debug network problems.
- mijoharas 12y ago
  Can I ask what you mean by "replay functionality" specifically? I have to say the project looks interesting, looking forward to diving into the code.
  - Dewie 12y ago
    He probably means something like this: http://debug.elm-lang.org/ http://debug.elm-lang.org/
    - seanmcdirmid 12y ago
      You really don't get that for free though, since you saved versions of everything you'd quickly exhaust the heap. Also, one could bother with delta checkpointing (only copy dirty pages) to get something like this in an imperative language, or build a programming model especially suited for it [1]. Functional programming doesn't really make this much easier (even if you use persistent data structures). [1] http://research.microsoft.com/en-us/people/smcdirm/managedtime.aspx http://research.microsoft.com/en-us/people/smcdirm/managedti...
      - lmm 12y ago
        You don't have to save versions of everything because your functions are pure, so you just save your inputs and you can recompute what happened.
        12y ago
egonschiele 12y ago
Game author here. Honestly, I had the same concern when I started out. But Haskell turned out to be a surprisingly good fit. I made a short video explaining the code: http://vimeo.com/109663514 http://vimeo.com/109663514 It skips a little in the beginning, but I think you might find it interesting.
jerf 12y ago
In addition to the other fine replies: As a game gets bigger and more complicated, you'll often find that the direct mutable OO approach becomes an antipattern at scale. Do you have anything that you want to do, but discover halfway through for some reason it's not legal? Good luck undoing what was half done. Of course you might think the simple answer is "don't do that", but as the game gets bigger and responsibilities get spread out between all the objects it becomes increasingly easy for some action to become possible that requires a lot of checking, and if things are just willy-nilly mutating themselves the odds of you encountering this sort of problem skyrocket. And that's just one example... games by their nature resist the sort of decomposition that most "real" software can have done on it, because as soon as you tell a designer that X can't talk to Y, by golly they'll start thinking about how awesome it would be if X was talking to Y. You don't get a pretty tree of relationships with occasional crosstalk, you get a nasty snarl of communication patterns, irreducibly. Many games end up functional under the hood anyhow, with a clearly-defined loop: 1. Ask all the objects in the world what they "want" to do. 2. Validate and resolve conflicts. 3. Render the new world state. One of OO's big problems in general is lack of control over the profound, often-overpowerful effects of mutation, and used in an undisciplined manner, games often turn into a worst-case-scenario for OO. And most of using them in a "disciplined" manner turns out to be using "FP" techniques to keep the complexity under control. Of course nothing stops you from doing that in OO, with discipline and care unenforced by the compiler. But what it does mean is that suddenly the "mismatch" that you're referring to disappears, and one starts wondering whether perhaps FP is the better match for games and OO the accident of history.
- webjprgm 12y ago
  I might also point out that OO and FP are not strictly at odds. You can use object libraries in FP languages to encapsulate the state and logic but avoid the mutation of the state. So if the two issues are orthogonal then you're both right. :-)
  - crimsonalucard 12y ago
    Good point. So if I use OO while maintaining immutability then am I doing functional programming, OO or both?

crimsonalucard 12y ago

FYI I'm in no way challenging the impressive nature of making this game with Haskell. I'm just challenging the hype around the style and asking whether it really is the most efficient solution to programming a game...

orclev 12y ago
It isn't really about efficient, it's about making it simpler to reason about. Functional style is a different way of reasoning about state than OO, but they're both fundamentally about abstracting state and making it simpler to work with and reason about. OO takes the divide and conquer approach, by dividing state into progressively smaller chunks until each piece is small enough to reason about. The flaw with that is that at some level you need to understand and reason about the entirety of the state, and if you have a bug in some lower level piece it often exhibits as bad behavior in one of the higher level pieces. Figuring out which of the lower level pieces is ultimately responsible is 90%+ of the time spent on debugging in a OO program. Another challenge is that because state is mutable, just finding the starting point to debug the problem is often a chore because you must first get the system into the state necessary to trigger the bug. Even worse is that often the state you initially detect the bug in, is actually significantly further along than where the bug originates so you end up having to attempt to progressively walk backwards through time to arrive at the originating point (which in practice means running a debug session to a point, finding the next piece of state that looks wrong, setting new breakpoints, and then repeating the whole exercise). Functional programming takes a different tack by instead strongly discouraging state altogether. A well written functional program will contain only the absolute bare minimum state necessary to accomplish the task at hand. Further state tends to be divided into two distinct camps, the global state that's referenced by name (largely non-existent barring mutable IO refs and such), and the local state that's passed explicitly as function arguments (ignoring for the moment the monad abstraction around that). Like with OO you sometimes arrive at a point where behavior isn't what you expect it to be and need to go to a debugger to figure out where the state has deviated from the expected. Unlike in OO however you have the call stack to reference and can see exactly where in the history the problem originated. Finding the source of a bug in a large functional program tends to be rather trivial compared to the similar task in a large OO program, due to the more concise and limited state that exists in functional programs.

gamegoblin 12y ago

You just have to change the way you think about the game. Rather than viewing the game as a wholistic "Game" object which changes state as the game progresses, view it instead as a series of game states or frames which are immutable. Then you define a function that is like (in C-ish): GameState tick(GameState current, Action playerMove) { ... set up the next frame and return it ... } And a function to play like: void play() { play(initialState()); } void play(GameState current) { if(current.gameOver()) return; Action playerMove = getPlayerMove(); GameState next = tick(current, playerMove); play(next); // In Haskell and C on higher optimizations, this tail recursive call will get compiled to a loop } Of course it can get a bit more complicated depending on the context, but you get the idea. So I'd say functional programming is neither better nor worse. A lot of people get hung up on the idea of immutability, but really I've found it to be a non-issue.

lucian1900 12y ago

> Chips, blocks, player character all tend to be better described as mutable objects That is just one way to look at it. You could also say that they can all be described by the universe's state at a point in time. Then, you'd have a function that takes the old state and some actions to produce a new state, by recursively doing the same to each object within the universe.

bpage 12y ago
This wording sounds remarkably similar to quantum mechanics. I wonder how far you could take the idea of building a game out of state vectors and linear transformations.
- Zeebrommer 12y ago
  State vectors and linear transformations are by no means unique to quantum mechanics. A lot of dynamic systems can be described this way: robot arms, chemical plants, airplanes, even network dynamics.
  - bpage 12y ago
    Naively I can guess how robot arms and networks could be spoken of in terms of states (and perhaps even chemical plants), but airplanes? Do you have any more information on the topic?
    - Zeebrommer 12y ago
      The technique is called a state space model [0]. A complete airplane might have been a bit hyperbolic, but as long as the assumption of linear dynamics is allowable, extremely large systems with multiple inputs and outputs and thousands of states can be simulated. What's more, there are some elegant and practical ways to find controllers with mathematically proven performance (like LQG control, or Model Predictive Control). This field of study has lead to the Kalman filter, which might ring a bell. 0: https://en.wikipedia.org/wiki/State_space_representation https://en.wikipedia.org/wiki/State_space_representation

ehurrell 12y ago

I think from a perspective of learning functional approaches it's useful to have things like this, as a more complex worked example of applying functional concepts to a problem. That is to say it seems like a broader version of "You know how in OO you made a 'Car' object with an 'Engine' with attributes and functions, well this is how it's done functionally".

mbrock 12y ago

Haskell is a general-purpose programming language, and discrete simulation-type systems like Chip's Challenge can be very elegantly modelled with nice things like algebraic data types, pattern matching, etc. The code is right there on GitHub, although if you're not familiar with Haskell (and lens), it might seem cryptic. But you'll see that it is actually mostly written in an imperative style. The logic is mostly pattern matching on events to generate record updates. This is a common style in Haskell and fits the domain well. There are other more elegantly value-oriented ways of writing simulations in Haskell; look up functional reactive programming.

Dewie 12y ago

I know, right? This here is a classic example of a nail, so why wouldn't I use my trusty hammer..

lmm 12y ago

There are some advantages to thinking this way. You get replay functionality "for free" (even if you never expose this to users, it makes debugging much easier), and it becomes much easier to think about how the game will work in a network situation (where each client has its own "copy" of the world, and the two copies might be "out of sync"). I've written initially-imperative games that became more and more functional as I started to debug network problems.

mijoharas 12y ago
Can I ask what you mean by "replay functionality" specifically? I have to say the project looks interesting, looking forward to diving into the code.
- Dewie 12y ago
  He probably means something like this: http://debug.elm-lang.org/ http://debug.elm-lang.org/
  - seanmcdirmid 12y ago
    You really don't get that for free though, since you saved versions of everything you'd quickly exhaust the heap. Also, one could bother with delta checkpointing (only copy dirty pages) to get something like this in an imperative language, or build a programming model especially suited for it [1]. Functional programming doesn't really make this much easier (even if you use persistent data structures). [1] http://research.microsoft.com/en-us/people/smcdirm/managedtime.aspx http://research.microsoft.com/en-us/people/smcdirm/managedti...
    - lmm 12y ago
      You don't have to save versions of everything because your functions are pure, so you just save your inputs and you can recompute what happened.
      - 12y ago

egonschiele 12y ago

Game author here. Honestly, I had the same concern when I started out. But Haskell turned out to be a surprisingly good fit. I made a short video explaining the code: http://vimeo.com/109663514 http://vimeo.com/109663514 It skips a little in the beginning, but I think you might find it interesting.

jerf 12y ago

In addition to the other fine replies: As a game gets bigger and more complicated, you'll often find that the direct mutable OO approach becomes an antipattern at scale. Do you have anything that you want to do, but discover halfway through for some reason it's not legal? Good luck undoing what was half done. Of course you might think the simple answer is "don't do that", but as the game gets bigger and responsibilities get spread out between all the objects it becomes increasingly easy for some action to become possible that requires a lot of checking, and if things are just willy-nilly mutating themselves the odds of you encountering this sort of problem skyrocket. And that's just one example... games by their nature resist the sort of decomposition that most "real" software can have done on it, because as soon as you tell a designer that X can't talk to Y, by golly they'll start thinking about how awesome it would be if X was talking to Y. You don't get a pretty tree of relationships with occasional crosstalk, you get a nasty snarl of communication patterns, irreducibly. Many games end up functional under the hood anyhow, with a clearly-defined loop: 1. Ask all the objects in the world what they "want" to do. 2. Validate and resolve conflicts. 3. Render the new world state. One of OO's big problems in general is lack of control over the profound, often-overpowerful effects of mutation, and used in an undisciplined manner, games often turn into a worst-case-scenario for OO. And most of using them in a "disciplined" manner turns out to be using "FP" techniques to keep the complexity under control. Of course nothing stops you from doing that in OO, with discipline and care unenforced by the compiler. But what it does mean is that suddenly the "mismatch" that you're referring to disappears, and one starts wondering whether perhaps FP is the better match for games and OO the accident of history.

webjprgm 12y ago
I might also point out that OO and FP are not strictly at odds. You can use object libraries in FP languages to encapsulate the state and logic but avoid the mutation of the state. So if the two issues are orthogonal then you're both right. :-)
- crimsonalucard 12y ago
  Good point. So if I use OO while maintaining immutability then am I doing functional programming, OO or both?