Immutable game object, basic functional programming question.

Question

Hi all,

I'm in the process of trying to 'learn more of' and 'learn lessons from' functional programming and the idea of immutability being good for concurrency, etc.

As a thought exercise I imagined a simple game where Mario-esq type character can run and jump around with enemies that shoot at him...

Then I tried to imagine this being written functionally using immutable objects.

This raised some questions that puzzled me (being an Imperative OO programmer).

1) If my little guy at position x10,y100 moves right 1 unit do I just re-instantiate him using his old values with a +1 to his x position (e.g x11,y100)?

2) (If my first assumption is correct) If my input thread moves little guy right 1 unit and my enemy AI thread shoots little guy and enemy-ai-thread resolves before input-thread then my guy will loose health, then upon input thread resolving, gain it back and move right ...

Does this mean I can't fire-&-forget my threads even with immutability? Do I need to send my threads off to do their thing then new()up little guy synchronously when I have the results of both threaded operations? or is there a simple 'functional' solution?

This is a slightly different threading problem than I face on a day to day basis. Usually I have to decide if I care about what order threads resolve in or not. Where as in the above case I technically don't care if he takes damage or moves first. But I do care if race conditions during instantiation cause one threads data to be totally lost.

3) (Again if my first assumption is correct) Does constantly instantiating new instances of an object (e.g Mario guy) have a horrible overhead that makes it a very serious/important design decision ?

EDIT Sorry for this additional edit, I wasn't what good practice is on here about follow up questions...

4) If immutability is something I should strive for and even jump though hoops of instantiating new versions of objects that have changed...And If I instantiate my guy every time he moves (only with a different position) don't I have exactly the same problems as I would if he was mutable? in as much that something that referenced him at one point in time is actually looking at old values?.. The more I dig into this the more my head's spinning as generating new versions of the same thing with differing values just seems like mutability, via hack. :¬?

I guess my question is: How should this work? and how is it beneficial over just mutating his position?

for(ever)//simplified game-loop update or "tick" method
{
   if(Keyboard.IsDown(Key.Right)
      guy = new Guy(guy){location = new Point(guy.Location.x +1, guy.Location.y)};
}

Also confusing is: The above code means that guy is mutable!(even if his properties are not)

4.5) Is that at all possible with a totally immutable guy?

Thanks,

J.

Answer 1

Not everything in your program should be immutable. A player's position is something you would expect to be mutable. His name, maybe not.

Immutability is good, but you should perhaps rethink your approach to use more concurrent solutions than simple "immutable"ize everything. Consider this

Thread AI gets copy of your position You move three units to the left. AI shoots you based on your old position, and hits... shouldn't happen!

Also, most gaming is done in "game ticks" - there's not much multithreading going on!

Answer 2

A couple comments on your points:

1) Yes, maybe. To reduce overhead, a practical design will probably end up sharing a lot of state between these instances. For example, perhaps your little guy has an "Equipment" structure which is also immutable. The new copy and the old copy can reference the same "equipment" structure safely, since it's immutable; so you only have to copy a reference, not the whole thing. This is an common advantage you only get thanks to immutability -- if "equipment" was mutable, you couldn't share the reference, since if it changed, your "old" version would change too.

2) In a game, the most practical solution to this issue would probably be to have a global "clock" and have this sort of processing happen once, at a clock tick. Note that your exact scenario would still be a problem if you didn't write it in a functional style: Suppose H0 is the health at time T. If you passed H0 to a function which made a decision about health at time T, you took damage at time T+1, and then the function returned at time T+5, it might have made the wrong decision based on your current health.

3) In a language that encourages functional programming, object instantiation is often made as cheap as possible. I know that on the JVM, creating small objects on the heap is so fast that it's rarely a performance consideration in any practical situation at all, and in C# I've never encountered a situation where it was a concern either.

Answer 3

Read the series Purely Functional Retrogames, which describes how to implement Pac-Man using a mostly pure functional language Erlang. The problems that he describes there are common problems for all functional game programming, and he presents good, usable solutions to all of your questions above.

Answer 4

If everything in the global system state, outside the current stack frame, is immutable, unless gives another thread a reference to something on the stack (VERY DANGEROUS) there won't be any way for a threads to do anything to affect each other. You could fire and forget, or simply not bother firing in the first place, and the effect would be the same.

Assuming there are some parts of the global state that are mutable, one useful pattern is:

Do
  Latch a mutable reference to an immutable object
  Generate a new object based upon the latched reference
Loop While CompareExchange fails.

The compare exchange should update the mutable reference to the new one if it still points to old one. This avoids the overhead of locking if there is no concurrent access, but may perform worse than locking if many threads are try to update the same object and generating a new instance from the latched one is slow. One advantage of this approach is that there is no danger of deadlock, though in some situations liveLock could occur.

Answer 5

1) If my little guy at position x10,y100 moves right 1 unit do I just re-instantiate him using his old values with a +1 to his x position (e.g x11,y100)?

Well, not necessarily. You could instantiate the guy once, and change its position during play. You may model this with agents. The guy is an agent, so is the AI, so is the render thread, so is the user.

When the AI shoots the guy, it sends it a message, when the user presses an arrow key that sends another message and so on.

 let guyAgent (guy, position, health) =
     let messages = receiveMessages()
     let (newPosition, newHealth) = process(messages)
     sendMessage(renderer, (guy, newPosition, newHealth))
     guyAgent (guy, newPosition, newHealth)

"Everything" is immutable now (actually, under the hood the agent's dipatch queue does have some mutable state probably).

4) If immutability is something I should strive for and even jump though hoops of instantiating new versions of objects that have changed...And If I instantiate my guy every time he moves (only with a different position) don't I have exactly the same problems as I would if he was mutable?

Well, yes. Looping with mutable values and recurring with immutable ones is equivalent.

Edit:

1. For agents, the wiki is always helpful.
2. Luca Bolognese has an F# implementation of agents.
3. This book (called by some The Intelligent Agent Book), though targeting the AI applications (instead of having a SW engineering point of view) is excellent.