Tuesday, December 21, 2010

Static analysis of gameplay

Last night, couldn't really sleep, and my mind somehow landed at Fallout 3 and how complex a game like that is. It must've been an QA nightmare to test a game that has so many ways to play, so many different quests which may or may not be compatible with each other.

So I was thinking, what if game developers had a sort of editor, where they can see all the triggers in the game and their relationships between them, and have some sort of static analysis going on there to make sure you're not accidentally creating impossible situations.

In this editor, every trigger would have some 'hard' prerequisites, some of these would be added automatically from the trigger itself 'trigger will be triggered when you have object X and walk into region Y', and others would be implicit 'you can't get object X unless you finished quest Z', which would mean that all the prerequisites required to complete quest Z are automatically added to the trigger. Less quantifiable rules, I call them soft' prerequisites, could be added manually, for example 'Player must have strength X to reach this trigger'.

The difference between soft and hard prerequisites is that hard prerequisites would be checked at runtime (indirectly or directly) and soft prerequisites would only be used to check for situations where you don't want your average player to get stuck, but a good player might still be able to get through it. Each of these prerequisite rules would be either a boolean true/false 'do you own object X' or a simple comparison 'is your health > Y'.

Another idea I had is that the game's navigation meshes (which presumably are also the exact areas that the player can traverse) are divided into regions, and these regions are defined in such a way that you can get to anywhere from anywhere within a region without crossing a trigger, and the only way to leave a region is through a trigger. Triggers that have a location in the world are then associated with one or two regions (depending if it's a doorway or not).
Using this information we can then do some sort of flood fill where we start at the players' starting location, and while we go from region to region, we remember the prerequisites that are required to go from one region to the next and add them to the the triggers we encounter.
We actually have to do that for every possible path taken, skipping identical paths and avoiding loops. This can quickly become pretty complex, but it wouldn't have to be done in real-time or even all the time.

Regions can also be used to detect situations where a player jumps down from region A into region B, which he can't possibly get out anymore (nor finish the game from that location). (because, for example, the prerequisites of region A are in direct conflict with region B)

In the end we'll end up with basically a big expression tree, which can be simplified at every iteration. This expression tree can then be checked for conflicting expressions (for example, to trigger a certain trigger 'apple must be eaten' AND 'apple must've been thrown in bottomless pit'), and be shown to the game designer who can then check if it makes any sense ('you can only finish the game if science = 100'). The game designer could even do a sort of stack trace to see how the current expression tree was created.

I wonder if anyone out there has ever attempted to create something like this, it's basically a gameplay unit test of sorts..


  1. I actually work in the systems group at Bethesda, and we talk about this informally on occasion. The sheer amount of scripting we do for our games means that writing a set of propositions besides the actual scripts, just to check the scripts, just isn't feasible in terms of manpower. The question then becomes: Can we design a scripting system that's constrained enough to be used as input to what's effectively an automated theorem prover, yet flexible enough to implement everything we want to put into our games?

    My instinct is that we can for 95% of what we do, but the remaining 5% is what makes the game world truly alive and vibrant and interesting -- and too intractable for static analysis.

  2. Well of course it's easy for me to write down this idea from a purely theoretical point of view, practice is obviously more complicated and messy. I didn't mean to make it sound like this would solve everything, all the time, but it might avoid at least *some* of the headaches. I can imagine that a game would have to build around something like this from the start to make it work at all.

    I can also imagine, that if a system like this is attempted, that there would have to be a sort of feedback loop between QA and the game designers, so that every time a bug is discovered a new test of sorts would be added to try to detect it. Increasing the quality of the tests at each iteration. I suppose going through all this effort makes more sense when you're planning on making lots of games with the same underlying technology.

    In the case of pushing a rock in front of a door, it's probably possible to create a test for it, but probably wouldn't be worth it. (not to mention that it would be a dynamic test, not a static test, but I definitely get your point)

    There would always be cases that would fall through the cracks I suppose. I guess you'd have to just ignore the "total uncertainty" parts for the static analysis and really really try to keep them down to a minimum.


To you spammers out there:
Spam will be deleted before it shows up, so don't bother.