Beyond Story Graphs: Story Management in Game Worlds

  1. 1. Michael Mateas

    Georgia Institute of Technology (Georgia Tech)

Work text
This plain text was ingested for the purpose of full-text search, not to preserve original formatting or readability. For the most complete copy, refer to the original conference program.

Bringing truly interactive story structures to computer games is hotly debated topic within the worlds of computer game design and academic game studies. For some designers and theorists, interactive story worlds are a holy grail of game design (e.g. Murray, Crawford), while for others narrative is antithetical to interactive experiences, destroying the high-agency, procedural potential of games (e.g. Eskelinen, Frasca). The heart of the tension between games and narrative lies in player agency. A player is said to have agency when she can form intentions with respect to the experience, take action with respect to those intentions, and interpret responses in terms of the action and intentions. Those who argue against narrative games point to the predetermined or predestined nature of narrative; strong narrative structures have complex sequences of cause and effect, complex character relationships and sequences of character interactions. Since player interaction can at any moment disrupt this narrative structure, the only way to maintain the structure is to remove or severely limit the player's ability to effect the structure. This eliminates so-called global agency, forcing the player down a predetermined path. Thus ludologists argue that if narrative must inevitably mean a diminishment in player agency, it should not be used in game design.

Contemporary games do seem to support the ludologist position. In all contemporary story-based games the story structure is completely fixed, or has an extremely simple branching structure. The player has local agency, that is, can move around the environment and interact with objects and non-player characters, but the narrative structure is a linear sequence of cut scenes unlocked during the gameplay. In order to provide global narrative agency, computational and design methods must be devised that can incorporate player interaction into large scale story structures. This problem can be best understood by contrasting it with story graphs.

The standard best practice in interactive narrative is the story graph, where each node represents a story event and each arc represents player actions. In a story graph the author has manually unwound all possible paths through the narrative space. However, the manual authoring overhead of story graphs means that, in practice, they tend to have a very small branching factor (quasi-linear) and a small number of nodes (limited story-level variation), leading precisely to the lack of global (story) agency evident in the contemporary game scene.

Story management

The alternative to the story graph is story management. The first story manager was proposed by Brenda Laurel in her thesis on interactive drama (Laurel), and further developed by AI research groups exploring interactive narrative. A story manager replaces the graph structure with a policy for story event selection. The author still creates the nodes of the story graph, where nodes represent story events such as scenes or individual character actions (depending on the granularity of global agency). However, rather than manually linking the nodes, that author instead creates a selection policy for story events; story events are activated as a function of the history of the story so far and the actions performed by the player. The story policy implicitly defines a story graph; theoretically, one can imagine unrolling the policy into a graph by recording the story function's response to all possible inputs (story histories + player action). The whole point of the story management approach, however, is to keep the graph implicit. By implicitly specifying graphs via a story policy, authors can create interactive stories that would be impractical to explicitly specify as graphs, and can thus create experiences with rich global agency.

In order to define a story policy, the author must specify:

•A representation of the desired story. In order for the story policy to select the next story event, it will need some model of the desired story (what a good story looks like within the domain) so as to decide what direction the story should move in given the story history plus player actions.

•A collection of story events. The story events may correspond to discrete units of storyness, such as scenes or dramatic beats, or may be more abstract story moves that manipulate the world in such a way as to make a desirable story happen in the future.

•A function that, given a model of the desired story, the story history, and the player actions, selects a story event.

•When story event selection happens. In general, a game world presents the player with a continuous, real-time experience while story guidance only happens at discrete points. This presents the design problem of deciding when guidance should happen.

Example story managers

In this paper I survey three approaches to story management, the beat-based drama manager of the interactive drama Façade (Mateas & Stern 2003), Magerko and Laird's IDA (2003), and the search based drama manager (SBDM) first defined by Bates and Weyhrauch (1992; 1997), describing the different design decisions made by each approach with respect to the four design questions above.

In the Façadedrama manager the story events are inspired by dramatic beats (McKee), the smallest units of dramatic value change. The desired story is modeled by one or more story value arcs (in Façade, the tension story value), and by declarative knowledge represented on each beat. This declarative knowledge includes:

one or more preconditions, tests over facts pertaining to the episodic memory of the story-so-far that must be true for the beat to be potentially selectable;

one or more priority tests that, given a satisfied precondition, boost the importance of a beat being selected;

one or more weight tests that, given a satisfied precondition and highest-priority, boost the probability of a beat being selected;

one or more effects that describe how the beat, assuming it is successfully executed in the world, will change the story values.

This knowledge, plus the desired story value arc(s), is used to compute a probability distribution over possible next beats; beats are selected by drawing from this changing distribution. When a beat is selected it activates a collection of behaviors that support the autonomous characters in carrying out the beat. These character-specific behaviors, which model the intentional structure of the characters, are written so as incorporate the player's moment-by-moment activity into the performance of the beat. If the player's activity deviates too far from the context assumed by the beat, the beat is aborted and a new one selected. Beat selection occurs on beat success (the beat successfully accomplishes the drama value change) or failure (the player's activity violates the beat context).

In SBDM, a player's concrete experience in the world is captured by a sequence of Player Moves, abstract plot points that a player's activity can cause to happen. A single Player Move may encapsulate 5 or 10 minutes of concrete player activity in the world - moving around, picking up objects, interacting with characters and so forth. When the concrete activity accomplishes a plot point, then a Player Move is recognized. A SBDM has a set of System Moves available that can materially alter the world (e.g. move objects around, change goals in characters' heads, etc.) in such a way as to encourage or obviate a Player Move. System Moves give the SBDM a way to warp the world around the player so as to make certain Player Moves more or less likely. Besides the System Moves, the author also provides the SBDM with a story-specific evaluation function that, given a complete sequence of Player and System Moves, returns a number indicating the "goodness" of the story. Whenever the drama manager recognizes a Player Move occurring in the world, it projects all possible future histories of Player and System moves, evaluates the resulting total histories with the evaluation function, and backs these evaluations up the search tree (in a manner similar to game-tree search) to decide which system move to make next that is most likely to cause a good total story to happen.

The future of story management

Story management virtualizes the links of a story graph; while the nodes of the graph must be authored, the possible paths through the graph remain implicit. The future of story management is to virtualize the nodes of the story graph as well; the nodes (story events) will be dynamically constructed as needed. The challenge will be to adapt algorithmic story generators to incorporate interaction. All artificial intelligence-based models of story generation, including story grammars, character modeling, and author modeling, assume that all elements of the story are under the complete control of the generator. In interactive narrative, however, the player can perform actions at any time that may compromise the current causal structures established by the generator. In the context of story management, generation must be able to dynamically adapt to player action.


Bates, J.
Virtual Reality, Art, and Entertainment
Presence: The Journal of Teleoperators and Virtual Environments

Cavazza, M.
Charles, F.
Mead, S.J.
Sex, Lies and Videogames: an Interactive Storytelling Prototype
Forbus, K.
El-Nasr, M.S.
Proceedings of the AAAI 2002 Symposium on Artificial Intelligence and Interactive Entertainment

Crawford, C.
Chris Crawford on Interactive Storytelling
New Riders

Eskelinen, M.
Towards Computer Game Studies
Forbus, K.
El-Nasr, M.S.
Proceedings of SIGGRAPH 2001, Art Gallery, Art and Culture Papers

Frasca, G.
Ludologists love stories too: notes from a debate that never took place
Proceedings of Level Up 2003, Utrecht, The Netherlands

Lamstein, A.
Mateas, M.
Search Based Drama Management
Working Notes of the AAAI Workshop Challenges in Game AI, AAAI

Laurel, B.
Towards the Design of a Computer-Based Interactive Fantasy System
Ph.D. Dissertation., The Ohio State University

Mateas, M.
An Oz-Centric Review of Interactive Drama and Believable Agents
Wooldridge, M.
Veloso, M.
AI Today: Recent Trends and Developments. (= LNAI 1600)
Berlin, New York
n. pag.

Mateas, M.
Stern, A.
Integrating plot, character and natural language processing in the interactive drama Façade
Paper delivered at the 1st International Conference on Technologies for Interactive Digital Storytelling and Entertainment (= TIDSE '03), Darmstadt, Germany, March 2003

Mateas, M.
Stern, A.
A Behavior Language for Story-Based Believable Agents
Working notes of the Artificial Intelligence and Interactive Entertainment Symposium, AAAI Spring Symposium Series
AAAI Press

Magerko, B.
Laifo, J.
Building an Interactive Drama Architecture with a High Degree of Interactivity
Paper delivered at the 1st International Conference on Technologies for Interactive Digital Storytelling and Entertainment (= TIDSE '03), Darmstadt, Germany, March 2003

McKee, R.
Story: Substance, Structure, Style, and the Principles of Screenwriting
New York, NY

Murray, J.
Hamlet on the Holodeck
MIT Press
Cambridge, MA

Pérez y Pérez, Rafael
Sharples, Mike
Three computer-based models of
storytelling: BRUTUS, MINSTREL and MEXICA
Knowledge-Based Systems

Weyhrauch, P.
Guiding Interactive Drama
Ph.D. Dissertation, Tech report CMU-CS-97-109, Carnegie Mellon University

Conference Info

In review


Hosted at University of Victoria

Victoria, British Columbia, Canada

June 15, 2005 - June 18, 2005

139 works by 236 authors indexed

Affiliations need to be double checked.

Conference website:

Series: ACH/ICCH (25), ALLC/EADH (32), ACH/ALLC (17)

Organizers: ACH, ALLC

  • Keywords: None
  • Language: English
  • Topics: None