Interactive storytelling (also known as interactive drama) is a form of digital entertainment in which the storyline is not predetermined. The author creates the setting, characters, and situation which the narrative must address, but the user (also reader or player) experiences a unique story based on their interactions with the story world. All interactive storytelling systems must make use of artificial intelligence (AI) to some degree. The architecture of an interactive storytelling program includes a drama manager, user model, and agent model to control, respectively, aspects of narrative production, player uniqueness, and character knowledge and behavior . Together, these systems generate characters that act "human," alter the world in real-time reactions to the player, and ensure that new narrative events unfold comprehensibly.
The field of study surrounding interactive storytelling encompasses many disparate fields, including (but not limited to) psychology, sociology, cognitive science, linguistics, natural language processing, user interface design, computer science, and emergent intelligence. They fall under the umbrella term of Human-Computer Interaction (HCI), at the intersection of hard science and the humanities. The difficulty of producing an effective interactive storytelling system is attributed to the ideological division between professionals in each field: artists have trouble constraining themselves to logical and linear systems, and programmers are disinclined to appreciate or incorporate the abstract and unproven concepts of the humanities.
What characteristics distinguish an interactive story from another form of interactive media is subject to much debate. Interactive storytelling is defined as distinct from interactive fiction (or IF) by user agency and open-ended narrative. IF does not make use of AI, and the commands understood by the system are predetermined, as are the outcomes. The narrative itself is constrained, whether by puzzles, battles, or a series of unchangeable plot points.
To Mateas and Stern, creators of Facade and The Party, interactive storytelling is best understood as interactive theater, in that its goal is dramatic meaning rather than fun - hence reference to interactive drama rather than storytelling in most research. It was Chris Crawford who coined the term interactive storytelling in the 90s, arguing that IS is not a video game with a narrative, and that a game and IS cannot be combined successfully .
By its open-ended nature, interactive storytelling immerses the player in a social interaction without the clear player goals that define most games. Because of limited technology and the amount of work required, it is still difficult to combine a robust interactive storytelling system and a game engine without detracting from the effectiveness of both. Sandbox games like The Sims and Spore, which involve extensive AI-based social interaction, do not manage dramatic tension or produce a cohesive narrative. Roleplaying games, which do offer a narrative arc and believable characters, do so only from a narrow set of pre-written possibilities.
Emerging voices in the field, however, argue for the possibilities of adding narrative complexity and realistic characters to existing video game genres. Using MADE (Massive Artificial Drama Engine), a team of AI researchers developed a Genetic Algorithm to guide emergent behavior for secondary non-player characters (NPCs) based on literary archetypes . In the open-source AI engine of TES: Skyrim, this was tested to elaborate on the mechanistic behavior of townspeople:
...hungry inhabitants could become thieves, guards could pursue the thieves, villagers could fall in love with others, or different war alliances could emerge.— García-Ortega et al., My life as a sim: evolving unique and engaging life stories using virtual worlds, 2014
Early attempts to understand interactive storytelling date back to the 1970s with such efforts as Roger Schank's research at Northwestern University and the experimental program TaleSpin . In the early 1980s Michael Liebowitz developed "Universe", a conceptual system for a kind of interactive storytelling. In 1986, Brenda Laurel published her PhD dissertation, "Toward the Design of a Computer-Based Interactive Fantasy System" .
During the 1990s, a number of research projects began to appear, such as the Oz Project led by Dr. Joseph Bates and Carnegie-Mellon University, the Software Agents group at MIT, the Improv Project led by Ken Perlin at New York University, and the Virtual Theater group at Stanford, led by Dr. Barbara Hayes-Roth.
There were also a number of conferences touching upon these subjects, such as the Workshop on Interactive Fiction & Synthetic Realities in 1990; Interactive Story Systems: Plot & Character at Stanford in 1995; the AAAI Workshop on AI and Entertainment, 1996; Lifelike Computer Characters, Snowbird, Utah, October 1996; the First International Conference on Autonomous Agents at Marina del Rey, CA. February 5–8, 1997.
The first conference to directly address the research area was the 1st International Conference on Technologies for Interactive Digital Storytelling and Entertainment, which took place in March 2003 and focused specifically on concepts and first prototypes for automated storytelling and autonomous characters, including modelling of emotions and the user experience . The concepts were developed by Chris Crawford, in his 2005 book. 
The 2000s saw a growth in work on interactive storytelling and related topics, presented at events including the alternating bi-yearly conferences, TIDSE (Conference on Technologies for Interactive Digital Storytelling and Entertainment) and ICVS (International Conference on Virtual Storytelling), hosted in Germany and France, respectively. TIDSE and ICVS were superseded by ICIDS (International Conference on Interactive Digital Storytelling), a yearly event established in 2008 .
The first published interactive storytelling software that was widely recognized as the "real thing" was Façade, created by Michael Mateas and Andrew Stern. The system was publicly released in 2006 , and was the winner of the Grand Jury Prize at the 2006 Slamdance Independent Games Festival.
Crawford discusses three potential strategies for developing interactive storytelling systems. Firstly, environmental approaches are those which take an interactive system, such as a computer game, and encourage the actions of a user in such a way as to form a coherent plot. With a sufficiently complex system, emergent behavior may form story-like behavior regardless of the user's actions.
Secondly, data-driven strategies have a library of "story components" which are sufficiently general that they can be combined smoothly in response to a user's actions (or lack thereof). This approach has the advantage of being more general that the directed environmental approach, at the cost of a much larger initial investment.
Finally, language-based approaches require that the user and system share some, very limited, domain-specific language so that they can react to each other and the system can 'understand' a greater proportion of the users actions. Crawford suggests approaches that only use, for example, pictorial languages or restricted versions of English 
Planning-based systems can be integrated into any of the above approaches to ensure narrative cohesion. The system does this by anticipating potential holes in the plot and repairing them by introducing new information and events. Two such systems include Automated Story Director (ASD), which forms narrative repairs based on plot points predefined by the author, and Player-Specific Automated Storytelling (PAST), which chooses from several possible repairs according to the player's previous behaviors . PAST characterizes a player along five vectors of style based on Robin Laws' work on player types - fighter, power gamer, storyteller, method actor, and tactician - and may choose to solve a broken plot point for a fighter by adding a battle with a new character, or for a storyteller by adding new background information that justifies the break.
The success of an interactive storytelling experience depends on a balanced dramatic structure and user agency. A dramatically interesting narrative experience is one that moderates tension between characters and events over time, such that conflicts arise logically and are not left without resolution. It must also differ noticeably on every "playthrough" as a function of the user's freedom to interact with characters and objects in the virtual world . This can be achieved to varying degrees of success by branching, emergent, character-driven, and plot-driven systems, but no existing system fully achieves a lifelike experience. AIs do not yet have a human grasp of the rules of drama and narrative, so existing interactive dramas produce a limited number of significantly different story outcomes, relative to the amount of labor required of the author.
There have been several attempts at formalizing an evaluation system for interactive dramas, despite the fact that all existing projects are still in experimental stages. Player agency and fun remain the primary concerns, though fun is often exchanged for more narrative-specific metrics, like "interestingness" and "suspense" . Likert scales filled out by players create a rough quantitative picture of user experience, but leave out much of the subjective interpretation that lies behind complex human interactions.
Mehta et al. focused on conversation-centric systems to develop qualitative metrics for the user's successful engagements, instead of quantitative measures of "inappropriate utterances" (in which the AI misunderstands player input and responds nonsensically) and other technical failures . After a "breakdown" in conversation, how effectively the user incorporates it into the overall understanding of the characters and story depends on design features - in Facade, background information is referenced often enough for a player to invent narrative justifications for apparently strange behaviors .
The Oz Project
The Oz Project was an attempt in the early 1990s to use intelligent agent technology to attack the challenges in IS. Its architecture included a simulated physical world, several characters, an interactor, a theory of presentation, and a drama manager.  Users communicated with the system using either a text based or graphical interface .
Façade is an artificial-intelligence-based approach created by Michael Mateas and Andrew Stern. It was the winner of the Grand Jury Prize at the 2006 Slamdance Independent Games Festival and is recognized as the first true interactive storytelling software. It is text based and uses natural language processing and other artificial intelligence routines to direct the action .
The Hybrid Evolutionary-Fuzzy Time-based Interactive (HEFTI) storytelling system was produced at the University of Texas at Austin and uses genetic algorithms to recombine and evaluate story components generated from a set of story templates. Although Crawford described it as the "wrong approach to development systems [...] incomprehensible to the kind of creative talent needed for storytelling,"  it continues to be discussed as a research and approach and genetic algorithm continue to be considered a potential tool for use in the area.
Library of story traces
Figa and Tarau have used WordNet to build technologies useful to interactive storytelling. This approach defines 'story traces' as an abstract reduction (or skeleton) of a story, and 'story projection' as a fragment of a story that can be treated as a single dramatic building block. This work seeks to build up large repositories of narrative forms in such a way that these forms can later be combined .
Interactive narrative design
As defined by Stephen Dinehart, Interactive narrative design combines ludology, narratology and game design to form interactive entertainment development methodologies. Interactive entertainment experiences allow the player to witness data as navigable, participatory, and dramatic in real-time: “a narratological craft which focuses on the structuralist, or literary semiotic creation of stories." Interactive Narrative design seeks to accomplish this via viewer/user/player (VUP) navigated dataspaces 
Interactive narrative design focuses on creating meaningful participatory story experiences with interactive systems. The aim is to transport the player through play into the videogame (dataspace) using their visual and auditory senses . When interactive narrative design is successful, the VUP (viewer/user/player) believes that they are experiencing a story .
Story possibilities are not precisely calculable, and are represented as orders, such that O(10) would be in the order of tens of stories, and O(1) would be fewer than 10 unique story possibilities.
|System||Virtual world||Interaction with objects||Social interaction||Dramatic structure||Story possibilities|
|Oz||Simple graphics||Yes||Some||Plot graph||O(10)|
|Virtual Theater Project||Text||Some||Yes||Plot graph||O(1)|
|Facade||Simple graphics||Some||Some||Plot graph||O(10)|
|IDA||Simple graphics||No||Some||Plot graph||O(1)|
|U-DIRECTOR||Simple graphics||Some||Some||Bayesian networks||O(1)|
|PaSSAGE||Neverwinter Nights graphics||Yes||No||Plot graph||O(10)|
|Mimesis||Simple graphics||Yes||No||Plot graph||O(1)|
|GADIN||Text||Some||Yes||Planning and dilemmas||O(∞)|
|Erasmatron||Text||No||Yes||Dramatic interest rules and general patterns||O(10)|
|DEFACTO||Text and simple graphics||Some||Some||Dramatic interest rules and general patterns||O(10)|
|OPIATE||Simple graphics||Yes||Some||Proppian structures||O(10)|
|DED||Second Life||Yes||Yes||Schemas and emergence||O(∞)|
|IDtension||Text||No||No||Planning and tasks||O(10)|
|I-Storytelling||Simple graphics||No||Some||Character HTNs||O(10)|
|FAtiMA||Simple graphics||No||Yes||Character goals and emergence||O(10)|
- Interactive media
- Types of fiction with multiple endings
- Narrative Structure: Interactive narration
- Interactive fiction
- Visual novel
- Ergodic literature
- Bostan & Marsh 2012.
- Crawford 2012.
- Rauch 2006.
- Mehta et al. 2007, p. 24.
- García-Ortega et al. 2014.
- Meehan 1977.
- Lauren 1986.
- Göbel 2004.
- Crawford 2005.
- Mateas & Stern 2003.
- Christensen 2006.
- Crawford 2005, Ch.8-10.
- Ramirez, Bulitko & Spetch 2013.
- Wand 2002.
- Rieser & Zapp 2002, pp. 163–178.
- Arinbjarnar, Barber & Kudenko 2009.
- Ramirez, Bulitko & Spetch 2013, p. 66.
- Mehta et al. 2007, p. 25.
- Mehta et al. 2007, p. 30.
- The Oz Project Homepage.
- Mateas 1997.
- Kelso, Weyrauch & Bates 1993.
- A genetic algorithm approach to interactive narrative generation, JJ Leggett and T. J. Ong - Proceedings of the fifteenth ACM conference, 2004
- WordNet, wordnet.princeton.edu/, retrieved April 2011
- Dinehart 2009c.
- Dinehart 2009a.
- Dinehart 2009b.
- Arinbjarnar, Maria; Barber, Heather; Kudenko, Daniel (2009). "A Critical Review of Interactive Drama Systems". Heslington, York, UK: Games Interactive Entertainment and Drama Group at York.
- Bostan, Barbaros; Marsh, Tim (2012). "Fundamentals of interactive storytelling". 3 (8). Online Academic Journal of Information Technology.
- Christensen, Louise (2006). "CoC Professor Wins Slamdance Gamemaker Competition". College of Computing. Georgia Institute of Technology. Retrieved 2014-09-24.
- Crawford, Chris (December 2012). Chris Crawford on Interactive Storytelling (2 ed.). Indianapolis, IN: New Riders Publishing. ISBN 0321864972.
- Chris Crawford (2005). Chris Crawford on Interactive Storytelling. New Riders. ISBN 978-0-321-27890-6. Retrieved 8 April 2011.
- Crawford, Chris (Speaker) (2015). Crawford Lecture at ICIDS: Interactive Storytelling (Conference lecture). Copenhagen, Denmark: Chris Crawford.
- Dinehart, Stephen (2009a). "Defining Interactive Narrative Design 2 – The Narrative Design Exploratorium". Narrativedesign.org. Retrieved 2010-09-02.
- Dinehart, Stephen (2009b). "Features - Dramatic Play". Gamasutra. Retrieved 2010-09-02.
- Dinehart, Stephen E. (2009c). "What is Interactive Narrative Design? | The Narrative Design Explorer". Narrativedesign.org. Retrieved 2012-05-18.
- García-Ortega, R. H.; García-Sánchez, P.; Mora, A.; Merelo Guervós, J.J. (2014). "My Life as a Sim: Evolving Unique and Engaging Life Stories Using Virtual Worlds". Proc. The Fourteenth Conference on the Synthesis and Simulation of Living Systems. New York, NY.
- Göbel, Stefan (2004). Proceedings of the 2nd Technologies for Interactive Digital Storytelling and Entertainment Second International Conference (TIDSE). Darmstadt, Germany.
- "International Conference on Interactive Digital Storytelling".
- Kelso, M; Weyrauch, p; Bates, J (1993). "Dramatic Presence". 2 (1). MIT Press.
- Laurel, B.K. (1986). "Toward The Design Of A Computer-Based Interactive Fantasy System (PhD dissertation)". Department of Theater, Ohio State University.
- Magerko, Brian (2005). "Story Representation and Interactive Drama". First Artificial Intelligence and Interactive Digital Entertainment Conference. Marina Del Rey, California.
- Mehta, Manish; Dow, Steven; Mateas, Michael; MacIntyre, Blair (2007). "Evaluating a conversation-centered interactive drama". Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems. Sao Paolo, Brazil.
- Mateas, Michael (1997). "An Oz-Centric Review of Interactive Drama and Believable Agents". Pittsburgh, PA: Carnegie Mellon School of Computer Science.
- Mateas, Michael; Stern, Andrew (2003). "Façade: An experiment in building a fully realized interactive drama" (PDF). Proceedings of the Game Developers Conference, Game Design track.
- Meehan, James R. (1977). "TALE-SPIN, An Interactive Program that Writes Stories". Proceedings of the Fifth International Joint Conference on Artificial Intelligence.
- "Oz Project Home Page". Carnegie Mellon School of Computer Science.
- Ramirez, Alejandro; Bulitko, Vadim; Spetch, Marcia (2013). "Evaluating Planning-Based Experience Managers for Agency and Fun in Text-Based Interactive Narrative". Proceedings of the Ninth AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment. Boston, MA.
- Rauch, Jonathan (Nov 2006). "Sex, lies, and video games". The Atlantic. London. pp. 76–86. Retrieved 27 September 2016.
- Rieser, Martin; Zapp, Andrea (2002). New Screen Media. British Film Institute / ZKM. ISBN 978-0-85170-864-5. Retrieved 2 May 2011.
- Si, Mei; Marsella, Stacy; Reidl, Mark O. (2008). "Interactive Drama Authoring with Plot and Character: An Intelligent System that Fosters Creativity". Creative Intelligent Systems, Papers from the 2008 AAAI Spring Symposium. Stanford, CA.
- Szilas, Nicolas (2005). "The future of interactive drama". Macquarie University Department of Computing.
- Wand, Eku (2002). "Interactive Storytelling: The Renaissance of Narration".
- Glassner, Andrew. Interactive Storytelling: Techniques for 21st Century Fiction. A. K. Peters. ISBN 1-56881-221-3.
- Crawford, Chris. Chris Crawford on Interactive Storytelling. New Riders. ISBN 978-0-321-27890-6.
- Murray, Janet. Hamlet on the Holodeck: The Future of Narrative in Cyberspace. The MIT Press. ISBN 978-0-262-63187-7.
- Bhatty, Michael. Interaktives Story Telling: Zur historischen Entwicklung und konzeptionellen Strukturierung interaktiver Geschichten. Shaker Verlag. ISBN 978-3826567179.
- "Video Games are Dead: A Chat with Storytronics Guru Chris Crawford", Gamasutra
- Erasmatazz - More information by Chris Crawford.
- ICIDS — Interactive Storytelling, hub of the International Conference on Interactive Digital Storytelling series (includes ICVS and TIDSE)
- Interactive Storytelling and Narrative Theories wiki Grouping descriptions of various narrative theories, IS systems and the computational models behind the systems.