Modeling and formal veriﬁcation of gaming storylines
Holloway, Lane Thomas
MetadataShow full item record
Video games are becoming more and more interactive with increasingly complex plots. These plots typically involve multiple parallel storylines that may converge and diverge based on player actions. This may lead to situations that are inconsistent or impassable. Current techniques for planning and testing game plots involve naive means such as text documents, spreadsheets, and critical path testing. Recent academic research    examines the design planning problems, but neglect testing and veriﬁcation of the possible plot lines. These complex plots have thus until now been handled inadequately due to a lack of a formal methodology and tools to support them. In this dissertation, we describe how we develop methods to 1) characterize storylines (SChar), 2) deﬁne a storyline description language (SDL), and 3) create a storyline veriﬁcation tool based in formal veriﬁcation techniques (StoCk) that use our SDL as input. SChar (Storyline Characterization) help game developers characterize the category of story line they are working on (e.g. linear, branching and plot) through a tool that give a set of guided questions. Our SDL allows its users to describe storylines in a consistent format similar to how they reason about storylines, but in such a way that it can be used for formal veriﬁcation. StoCk accepts storylines, described in SDL, to be formally veriﬁed using SPIN for errors. StoCk is also examined in three common use cases found in the gaming industry used as a tool 1) during storyline creation 2) during quality assurance and 3) during storyline implementation. The combination of SChar, SDL, and StoCk provides designers, writers, and developers a novel methodology and tools to verify consistency in large and complex game plots.