We are interested in the application of interactive storytelling in videogames. In particular, we want to create a more satisfying story experience in open-world adventure and role-playing games. A game that features an open world allows its players to move freely in a large space with few or no artificial barriers, choosing what to do and when. The flexibility of an open world and the fact that adventure and role-playing games tend to have strong story components  make these genres an interesting place to explore interactive storytelling techniques.
Combining IS and games introduces a new challenge: a balance must be achieved between creating a satisfying story and maintaining a reasonable level of player control in both the story and gameplay. This is no easy task, as Costikyan points out: “Divergence from a story's path is likely to make for a less satisfying story; restricting a player's freedom of action is likely to make for a less satisfying game” . It also brings an important difference between interactive storytelling and storytelling in games to the forefront. In traditional interactive storytelling, the IS system is primarily responsible for arranging the story being told, making adjustments according to user interactions. When telling interactive stories with games, however, it is the gameplay that drives the story forward and determines how it should unfold. Gameplay is what we call the interaction between players and a game system's rules . Gameplay includes physically moving through an open world's space, fighting enemies, conversing with non-player characters, and collecting items.
Figure 1: Our spectrum of how storytelling integrates with gameplay
Some gameplay actions might allow players to interact with the game's story elements, and others can indirectly affect the direction of the story. Viewed as a spectrum (Figure 1), the least interactive types of game stories come as a result of gameplay not having any effect on the story at all. The most interactive stories are directly affected by gameplay. In the middle, stories are affected by gameplay, but only indirectly. Many authors who wish to create compelling story experiences in games aim to create experiences as far right on the spectrum as possible, but several challenges make this more difficult than it may seem.
Figure 2: Lebowitz and Klug's storytelling in games spectrum
Lebowitz and Klug  also proposed a spectrum to analyze videogame stories (Figure 2). As presented, non-interactive stories are at the far left. The level of control that players have over the story increases to the right of the spectrum. Implicitly, the spectrum also captures how much control an author has over a story, with the largest level of control to the far left. Furthest right, the author has no control at all; games that Lebowitz and Klug call fully player-driven are highly emergent with no set plot.
We are more interested in how directly gameplay affects a story rather than the magnitude of control the player has, partly because gameplay and story often feel like separate activities. Furthermore, most open-world games we are interested in fit into the open-ended story category of Lebowitz and Klug’s spectrum, which they characterize as games that allow players to progress how they wish and that often (but not always) feature open worlds. Some open-world games allow players to explore and complete various tasks without any relation to the story. Others have similar tasks to complete, but doing so will cause the story to change in some way. We want to be able to distinguish games within the open-ended category, and we are able to do so with our spectrum.
In the following, we discuss the types of strategies used to implement game stories across our spectrum and discuss problems that arise for each. We begin at the far left of our spectrum, where gameplay has no effect on story. This does not necessarily mean that the game is not an example of interactive storytelling, as the player may be able to interact with the story in ways that do not change it. The player might choose which parts of the story to consume and when, explore the world the story is set in, or interact with the characters within. Games in the Zelda series, such as The Legend of Zelda: Skyward Sword, feature fixed stories but allow the player to converse with non-player characters and take on missions that have no story consequences. Not allowing gameplay to affect a story results in stronger authorial control over how the story unfolds. However, it also introduces a risk of creating gameplay that does not align well with the narrative being told, especially in games that offer much freedom in terms of how to approach gameplay. A story told about a hero that in gameplay can rob innocent citizens at will leads to ludonarrative dissonance, a term originally coined by Clint Hocking. Red Dead Redemption openly tracks the player's heroism, but it does not matter how heroic the player is deemed to be: non-player characters treat the player character the same way, and the same tasks are required of him. The worst case of a story not affected by gameplay is a “constipated story,” where strictly alternating presentations of gameplay and story fail to interact with each other at all .
Stories that are indirectly affected by gameplay lie in the middle of our spectrum. With such games, players do not directly make choices that alter the course of a story. Instead, players interact with the game system, resulting in changes to the game state. How the story is presented or arranged depends on the current game state. For example, a portion of a story might only be available if the player character has enough experience points. Many areas of Fallout 3 were technically available all the time, but the player could only survive long enough to explore them after gaining enough experience points through gameplay elsewhere. Alternatively, the outcome of a plot point might depend on how evil the player acted in previous encounters. In Fable II, the player has opportunities to be good or evil through various tasks. Which approach is chosen unlocks some new tasks, and changes the player character's appearance on screen. Some games with branching stories, including those with multiple endings, are also found near the middle of the spectrum. In BioShock, for example, gameplay actions indirectly cause the story to change. The game ends differently depending on what the player decides to do with certain characters that can either be spared or harvested for player benefit.
The structuralist approach of defining an implicit graph at run-time could be applied here; gameplay statistics can be used in scene preconditions, for example. Although players can only affect the story indirectly, most players will be satisfied. In two surveys of game players, Mallon and Webb  discovered that players actually prefer episodic and directed story experiences over unrestricted freedom, and Lebowitz and Klug  found that while the majority of players place great importance on a game’s story, they do not require full control over it.
Games with quests commonly feature gameplay that indirectly affects story [1, 6]. A quest system in a game is used to organize what quests are available and when. It will also take care of offering quests to the player, possibly through conversations with non-player characters or markers in the world the player interacts with to trigger a quest. Many games with open-ended stories feature quest systems. Each quest contains a fragmentary story and provides short-term gameplay goals [7, 8]. Story consistency is enhanced by making the quests self-contained and largely independent . As a result, completing a quest reveals a portion of the game's story that the player would not otherwise see, but rarely affects any other part of the story. The only indirect effect of choosing a quest through gameplay is the addition of the non-essential bit of story contained within. The stories revealed in quests would likely be more interesting if they connected better with what happens in the core plot; instead, they often feel like busy work, or little more than a way to improve your character's statistics.
If quests were less task-based and more goal-oriented, they might lie closer to the right of our spectrum where gameplay directly affects story. Quests in videogames tend to focus on tasks such as fetching items or engaging in combat instead of higher-level goals that can be achieved in various ways [7, 9, 10]. Instead of asking players to complete tasks, quests could be used to introduce meaningful conflict between characters that the player must resolve through gameplay, allowing for more direct interaction with the story. Games in the Mass Effect series use quests to introduce conflict between characters. Sullivan's GrailGM framework , designed to work with game mechanics based on social moves, also allows for conflict-oriented quests. GrailGM makes quests available based on the current social dynamics between player and non-player characters in the story. Players have the choice to complete the quest as put forth by the quest giver, or to create conflict by going against the quest giver's wishes. If more quests were explicitly connected to the game's main storyline, the gameplay act of choosing a quest could give a stronger sense of affecting the story.
There are games that more clearly lie to the right of our spectrum. Some games make their core mechanic a direct interaction with the story, as in Telltale Games’ The Walking Dead series. In The Walking Dead, players are primarily asked to decide how the main character should respond to various situations. Heavy Rain offers similar gameplay with one interesting difference. When players fail to complete an action move, the game does not ask them to try again. Instead, the following scene or scenes continue, but the exact content is affected by whether the player has failed or succeeded. Sometimes gameplay as simple as which quests the player chooses to embark on can directly impact the story. For example, Fallout: New Vegas tracks statistics about who the player is most loyal to. Which quests the player completes can affect loyalty and, by extension, how certain parts of the story will play out.
A challenge of games whose gameplay directly affects the story is to find ways to allow players to make meaningful dramatic decisions. The Walking Dead is a game that almost entirely consists of what appears to be dramatically significant choices. However, most choices the player makes impact only the next line of dialog, nothing more. While perceived agency can be important , it is easy to have the effect wear off when few or none of your choices are dramatically relevant.
 J. Lebowitz and C. Klug. Interactive Storytelling for Video Games. Focal Press (2011).
 G. Costikyan. Second Person: Role-Playing and Story in Games and Playable Media, chapter Games, Storytelling, and Breaking the String, pages 5 13. MIT Press (2007).
 K. Salen and E. Zimmerman. Rules of Play: Game Design Fundamentals. The MIT Press (2003).
 C. Crawford. Chris Crawford on Interactive Storytelling. New Riders, 2nd edition (2012).
 B. Mallon and B.Webb. Stand up and take your place: identifying narrative elements in narrative adventure and role-play games. Computers in Entertainment (CIE) 3, 1 20 (2005).
 J. Howard. Quests: Design, Theory, and History in Games and Narratives. A K Peters, Ltd. (2008).
 E. Aarseth. From hunt the wumpus to everquest: Introduction to quest theory. In F. Kishino, Y. Kitamura, H. Kato, and N. Nagata, editors, Entertainment Computing - ICEC 2005, volume 3711 of Lecture Notes in Computer Science, pages 496 -506. Springer Berlin Heidelberg (2005).
 M. Trenton, D. Szafron, J. Friesen, and C. Onuczko. Quest patterns for story-based computer games. In Proceedings of the Sixth Arti cial Intelligence and Interactive Digital Entertainment Conference (AIIDE) (2010).
 C. Lindley. Developing Interactive Narrative Content: sagas/sagasnet reader, chapter Story and Narrative Structures in Computer Games. High Text Verlag (2005).
 A. Sullivan. The Grail Framework: Making Stories Playable on Three Levels in CRPGs. Ph.D. thesis, University of California Santa Cruz (2012).
 M. W. Fendt, B. Harrison, S. G. Ware, R. E. Cardona-Rivera, and D. L. Roberts. Achieving the illusion of agency. In D. Oyarzun, F. Peinado, R. Young, A. Elizalde, and G. Méndez, editors, Interactive Storytelling, volume 7648 of Lecture Notes in Computer Science, pages 114 -125. Springer Berlin Heidelberg. (2012).