Dataflow Analysis of Computer Game Narratives

Many modern computer games tend to provide large, complex narratives, ensuring both extended and interesting game play. Unfortunately, game narratives often contain defects, represented by unwinnable situations, unspecified outcomes, and so forth, reducing the quality of games, and in the worst case leading to unexpected program behaviour or crashes. We present an approach to formally verifying the correctness of a game narrative based on program analysis techniques. Dataflow analysis is applied to a precise narrative specification, and used to optimize a search of the complete game state space. By focusing on a "high-level" narrative model we are able to add several further analyses that provide additional semantic information, reducing the verification costs and resulting in an analysis system that can examine non-trivial narratives in relatively little time---an improvement of several orders of magnitude over the state-of-the-art. This work demonstrates a practical and effective design for improving computer games, as well as an interesting adaptation of program analysis techniques to game analysis.

Greg Steffan

Last modified: Tue Aug 26 09:59:09 EDT 2008