Wednesday, 27 August 2008

Functional Update Musings

Recently I've been focussing a lot on the rendering part of this project. Quite fruitfully at times, but it certainly wasn't my intention.

The reason for this is simply when I sat down to work on some gameplay stuff, I found a hard problem, and the solutions I've arrived at so far have not been... nice.

As fair warning, this is a brain dump, and a long, boring one at that. It contains much partly-functional waffle because my brain is full of partially functional waffle.

Background: Mostly for my own illumination, I've been trying to use more functional idioms in this game than is strictly sensible. I've mentioned before that I wish to have a (mostly) immutable world, for example. The world update step therefore creates a new world state every 'turn'. The current world state is stored in a mutable variable at the end of each update, but other than that the entire update should be immutable and cuddly from a gameplay viewpoint.

Problem: Creating a suitable update step for my basic case is very easy. The only entities that can affect the world are Agents. Each agent has a (poorly named) 'energy' integer value. When an agent has zero energy, it can act. Actions themselves are the things that change the world state, they are essentially partial functions of type Action :: WorldState -> WorldState, and almost all have the secondary effect of reducing the current agent's energy value when they're executed. After the current agent has acted, the agent list is sorted, some simple transformations are applied to the entity list (dead creature agents are replaced with corpse entities, for example) and time is advanced to bring another agent into relevancy.

This works after a fashion, but certain things are more sensibly represented as continuous functions of time than as agents that act with some (possibly inconsistent) frequency. A better way might be to allow these functions of time to run after the current agent acts, as conveniently we implicitly have the delta time before the next agent is ready to act. This will allow us to damage creatures in lava/acid, or heal creatures that are regenerating, for example. Easy enough, we can make something like TimeFunction :: Int -> WorldState -> WorldState. This is very ugly in practise, especially if there is no ordering defined over the set of active TimeFunctions (consider the joyous difference in observed state if a timefunction spawns a monster and then another damages/kills it, versus damaging monsters then spawning them). There are also potentially huge problems if the list of active TimeFunctions is part of the world state, subject to being updated by TimeFunctions as they run. Blurgh!

There's another big source of ugly too: edge detection. In general, we're quite interested in observing certain changes in world state. An example which Andrew Doull writes about here is a quest to scare seven goblins, which I think can be done by detecting changes in the afraid state of goblin entities. If we perform a comparison of world state before and after the player-controlled agent acts, we can in theory unambiguously attribute any newly-scared goblins to the player and update quest progress. Again we can create something like: EdgeDetector :: WorldState -> WorldState -> WorldState, but it's even nastier now than the case for TimeFunctions. We also have three transitions that may be of interest and could have associated detectors: comparing the original world state to that after the current agent acts; post-agent-action world state to post-timefunction world state; and original state to post-timefunction world state. This would allow us to differentiate between the player killing a goblin with a mace and the goblin burning to death because it stupidly fell into some lava, even in the absence of creatures storing their last attacker or whatever.

It may help to constrain these ugly bits somewhat. For example mandating that TimeFunctions must define a strict ordering and only affect the list of entities and their own internal state, whilst EdgeDetectors can only update their internal state. This in turn means that some other object has to dig through the EdgeDetectors to extract useful data, but I suppose that's not too evil. Both edge detectors and time functions are created and destroyed only by agents, which is closer to the simplicity of the initial design.

But even with these slightly draconian measures in place, a single update is a far nastier affair than I feel it has any right to be, with multiple intermediate world states, and I'm unwilling to set this down in code outside my messy prototype framework.

I've been wrestling with the few papers I've found talking extensively about reactive/game programming in functional languages (by which I mean Haskell) but it's dense, dry, nearly unintelligible stuff as far as I'm concerned. Admittedly they're generally solving the far harder problem of realtime games, whereas I currently go the cheatsy route of using a great deal of mutable state for all realtime code paths such as rendering.

Anyway, brain dump complete. I hope I'll find a better solution and can come back and mock my doubtless shocking ignorance in this post, but right now it just makes me uneasy. The net result of which is my experimented with deferred rendering pipelines and funky post process effects, so its not all bad.


Alex said...

What is the reactive game programming / functional language literature? Dry though it may be, I'd like to peruse it. Also, I just found your blog while cruising looking for pages related to Scala and OpenGL / LWJGL and really think it's pretty cool stuff. Wish I could follow blogger sites from tumblr.

Snut said...

Hi Alex,

It's been a long time, but I'm thinking the best example would be Frag.

I still do not understand FRP well enough to use it myself, but it's a fascinating area.

Cheers for the comment, I may cross-pollinate to tumblr in the future when I've a better idea where the games and blog are going!