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..