Pure functional programming and game state

Question

Is there a common technique to handle state (in general) in a functional programming language? There are solutions in every (functional) programming language to handle global state, but I want to avoid this as far as I could.

All state in a pure functional manner are function parameters. So I need to put the whole game state (a gigantic hashmap with the world, players, positions, score, assets, enemies, ...)) as a parameter to all functions which wants to manipulate the world on a given input or trigger. The function itself picks the relevant information from the gamestate blob, do something with it, manipulate the gamestate and return the gamestate. But this looks like a poor mans solution for the problem. If I put the whole gamestate into all functions, there is no benefit for me in contrast to global variables or the imperative approach.

I could put just the relevant information into the functions and return the actions which will be taken for the given input. And one single function apply all the actions to the gamestate. But most functions need a lot of "relevant" information. move() need the object position, the velocity, the map for collision, position of all enemys, current health, ... So this approach does not seem to work either.

So my question is how do I handle the massive amount of state in a functional programming language -- especially for game development?

EDIT: There are some game frameworks for building games in Clojure. There approach to solve this problem partially is to thread all objects in the game as "entities" and put it in a huge bag. A gigant main function is holding the screen and the entities and handle events (:on-key-down, :on-init, ...) for this entities and run the main display loop. But this is not the clean solution I am searching for.

Answer 1

I have written a few games using F# (multi-paradigm, impure, functional-first language), with approaches ranging from OOP to FRP. This is a broad question, but I'll do my best.

Is there a common technique to handle state (in general) in a functional programming language?

My preferred way is to have an immutable type that represents the entire game State. I then have a mutable reference to the current State that is updated each tick. This is not strictly pure, but it keeps mutability limited to one place.

If I put the whole gamestate into all functions, there is no benefit for me in contrast to global variables or the imperative approach.

Not true. Because the State type is immutable, you cannot have any old component mutating the world in ill-defined ways. This fixes the biggest problem with the GameObject approach (popularized by Unity): it is hard to control the order of Update calls.

And unlike using globals, it is easily unit-testable and parallelizable,

You should also write helper functions that receive sub-properties of the state to break down the problem.

For example:

let updateSpaceShip ship = 
  {
    ship with 
      Position = ship.Position + ship.Velocity
  }

let update state = 
  { 
    state with 
      SpaceShips = state.SpaceShips |> map updateSpaceShip 
  }

Here update acts on the whole state, but updateSpaceShip only acts on an individual SpaceShip in isolation.

I could put just the relevant information into the functions and return the actions which will be taken for the given input.

My suggestion would be to create an Input type that holds the keyboard, mouse, game-pad, etc. states. You can then write a function that takes a State and an Input returning the next State:

let applyInput input state = 
  // Something

To give you an idea of how this fits together, the overall game might look something like this:

let mutable state = initialState ()

// Game loop
while true do
  // Apply user input to the world
  let input = collectInput ()

  state <- applyInput input state

  // Game logic
  let dt = computeDeltaTime ()

  state <- update dt state

  // Draw
  render state

So my question is how do I handle the massive amount of state in a functional programming language -- especially for game development?

For simple games you can use the approach above (helper functions). For something more complicated, you might want to try "lenses".

Contrary to some of the comments here, I would strongly suggest writing games in an (impure) functional programming language, or at least giving it a try! I have found it makes iteration quicker, code-bases smaller and bugs less common.

I also don't think you need to learn monads to write games in an (impure) FP language. This is because your code will most likely be blocking and single threaded.

This is particularly true if you are writing a multiplayer game. Then things will become much easier with this approach because it allows you to trivially serialize the game state and send it across the network.

As for why more games aren't written this way... I cannot say. However, this is true in all programming domains (except perhaps finance), so I wouldn't use this as an argument that functional languages are ill-suited to game programming.

Also well worth a read is Purely Functional Retrogames.

Answer 2

Side-effects and state in functional programming languages are a broader problem in computer science. In case you haven't encountered them before, maybe take a look at monads. Be warned, though: they are a fairly advanced concept and most people I know (me included) struggle to grasp them. There are many, many tutorials online, with differing approaches and knowledge requirements. Personally, I liked Eric Lippert's best.

I’m a C# programmer with no “functional programming” background whatsoever. What is this “monad” thing I keep hearing about, and what use is it to me?

Eric Lippert on Monads

Some things to consider, though:

• Do you insist on using a purely functional language? If you're skilled in both functional programming and game development, maybe you could pull it off. (Even though I'd like to know whether the benefits are worth the effort.)
• Wouldn't it be better to use functional approach only where necessary? If you're using an object-oriented (or, more likely, a multi-paradigm) language, nothing's stopping you from using functional style to implement sections which profit from it. (Kinda like MapReduce, maybe?)

Some final thoughts:

• Parallelism: While games do use it heavily, AFAIK most of it already happens on the GPU anyway.
• Statelessness: Mutations of state are an integral part of games. Trying to get rid of them might just complicate matters unnecessarily.
• Maybe look at how the functional language F# plays with the object-oriented ecosystem of .NET, if you're interested.

All in all, I think even if it could be interesting academically, I doubt this approach is practical and worth the effort.

Answer 3

What your looking for is FRP game development.

Some Video Introductions:

• "Controlling Time and Space: understanding the many formulations of FRP" by Evan Czaplicki

• Bodil Stokke: Reactive Game Development For The Discerning Hipster [JSConf2014]

• Love this talk with Carmack, describes his experiences with purely functional programming in game development John Carmack's keynote at Quakecon 2013 part 4

It is 100% possible and preferable to make the core game logic in a purely functional way, the industry as a whole is simply behind, stuck in one paradigm of thinking.

Its possible to do it in Unity as well.

• Unity Redux Library

To answer the question a new game state will be updated/created every time something moves, as carmack says in his talk, it's not a problem. The drastic reduction in cognitive overhead that comes from a purely functional, highly maintainable, flexible architecture far out ways the performance hit, if it exists at all.