Tuesday, 13 January 2009

More references

I sometimes (often) feel the Internet is too damn big to be useful.

But it is possible to find some really good stuff...

Like these fascinating posts dealing with writing retro games in functional languages. I linked the last part in the mini-series, because it posits a solution to one of my many current problems. Rather than allowing game logic to modify game state directly, emit a list of 'actions' which can be dealt with in a more or less atomic fashion at the end of a frame.

Initially this smacks of just moving hard work elsewhere, but I think it does help more than that. Your world state/list of entities becomes static for the bulk of a frame, so the order in which you process things is irrelevant, and consequently dereferencing entity handles becomes slightly more tractable. Of course there's a real danger that by the end of a frame, you may have accumulated mutually incompatible actions. However, imposing an ordering over actions and allowing them to be tolerant of faults seems like a better solution than threading the complete game state through everything related to an update - which essentially allows these supposedly transparent areas to side effect by fiddling with the world state directly.


Another fascinating post calls out the lack of a simple dictionary type as a major implementation headache for games in the chosen functional language (Erlang). That seems to be tacit support for the 'property bag' model of game entities in a functional context. I wonder how many other game programmers are lurking out there in the wilds of the internet, ready and willing to provide useful feedback from the experience of using these patterns in functional languages, if only my Google-fu were strong enough to find them.


Enne Walker said...

I was going to suggest deferring work as a solution to your entity reference problem, but my impression was that it would cause just as much trouble.

Generating order-independent actions doesn't seem to map very well to the logically serialized game state update loop. A hypothetical example: if an attacking monster wants to attack a currently-adjacent moving monster, then which action it chooses is entirely dependent on whether or not the moving monster moves first. (In other words, not order independent at all.) For example, if the moving monster moves out of range, then the attacking monster may not choose to attack. The fault tolerance here (of sorts) would then consist of recalculating the attacking monster's action using the intermediate state of the world.

This seems like the exact same situation of threading the world state through each serial update that you were trying to avoid in the first place.

Jotaf said...

Fault tolerance can deal with incompatible actions, but IMO it should never involve rerunning any of the purely functional code. You could easily find yourself in a deadlock situation. Instead, the action should always resolve the situation, no matter what happened. In the example it would cancel the attack. Yes, it's order-dependent. But making choices close to border conditions (like near "out of range") is always subject to mistake, miscalculations (happens IRL too). The more coarse-grained the action, the worse (like a control system with a low sampling rate). It's endemic to doing State->State transformations, so maybe we should just embrace it and make preparations (ie, keep in mind that every action is fallible). My opinion at least (sorry the the ramble :).

Thanks for the link! Accumulating actions seems like a good approach. Here's another one: rebuild the entities list every frame. Some pitfalls are pointed out. They're the same as with actions, and ultimately boil down to order dependence. (Which IMHO we can't get rid of.)

That's the output. How about the input? What form should the state of entities have when it reaches a transformation function? I'm leaning towards something like this... You already have a system in place, can you spare some details? The good, the bad? :)

Snut said...

Enne, thankfully it's a little better than that. Every update only allows one agent to act. You can still get yourself in an invalid state if, say, status effects are allowed to execute at some point between emitting actions and actually performing them (poison killing the monster you take a swing at, for example). Another tricky case might be a magical buff that reflects damage, which could kill the current active entity at some point between it performing an attack and the generic code that re-inserts it into the entity list with an updated energy value.

I don't think this fundamentally breaks the approach, it just means actions have to fail gracefully. Probably not a bad thing in itself.

Jotaf, that's an interesting insight. Lists are a good starting point for a lot of these functional approaches, not least because there's usually lots of syntactic sugar for dealing with them, but it's interesting that someone has run into performance problems even in small-scale testing with them! Thankfully abstracting away the container type is fairly easy...

I think I'll have to make a posting with some actual code, showing some of the prototypes I've been playing with. If nothing else it provides a comparison point. Now, where did I leave htmlize-buffer?