Keywords

1 Introduction

Stories in emergent narrative arise bottom-up, usually from the interactions of autonomous characters in a simulated storyworld [77]. This approach to computational narrative is as old as the field itself. Novel Writer and Tale-Spin, the earliest known story generators, were emergent-narrative systems. In the former, a murder story forms from the simulated actions of a group of partygoers [40]; in Tale-Spin, characters in a storyworld autonomously carry out plans that may allow them to achieve their goals [56]. In recent decades, there have been a number of subsequent emergent-narrative systems, including other AI-research systems like Virtual Storyteller [78], FearNot! [13], and Prom Week [55], as well as commercial games like The Sims [54] and Dwarf Fortress [3]. Other character-based systems, such as the Petz series of digital games [28], the interactive-story system of Cavazza et al. [21], and Chris Crawford’s Storytron [24], might also be called emergent-narrative systems.

Many of these systems, however, are not fundamentally interactive. Novel Writer and Tale-Spin are only interactive in that, in each, a user may specify the initial state of the storyworld. Virtual Storyteller is not interactive at all (it employs an embodied agent that tells emergent stories), though later extensions to it incorporated interactivity [33, 73].

The emergent narrative research program, cultivated by Ruth Aylett, Sandy Louchart, and others, has typically concerned only interactive systems, most often FearNot!-like research systems. In this paper, we likewise limit our concerns to interactive systems, but we use the term ‘emergent narrative’ more broadly to include systems like the digital games listed above; this usage is not unprecedented [18, 22, 49, 82]. We note that nondigital storytelling systems, such as tabletop role-playing games, should also be called emergent-narrative systems [45], but in this paper we do not consider these (as our concerns herein pertain only to digital systems). So, to be clear, by ‘emergent narrative’, we mean the application area characterized by digital, fundamentally interactive systems whose narratives emerge bottom-up, typically from the richness of underlying simulations that feature autonomous characters.

A basic appeal of emergent narrative is of course the very emergence that it yields, producing stories that even a system’s designer might not have anticipated. Indeed, games with rich underlying simulations have often been lauded for their emergent qualities [4, 38]—this is what got Dwarf Fortress, which we discuss in Sect. 4, into the Museum of Modern Art [87]. The fundamental advantage to this bottom-up approach, however, is that it defeats the sticky issue in top-down interactive narrative of accommodating player actions [9, 64]. If the affordances given to a player are a subset of (or are coextensive with) the actions that non-player characters (NPCs) may themselves take in an underlying simulation, then an emergent-narrative system will be inherently reactive to player inputs. As such, the stories that emerge in these systems naturally incorporate player actions. Emergent narrative was articulated by Aylett as a solution to this problem of conciliating interactivity and narrativity [9], which has been called the narrative paradox [13, 47] and the interaction dilemma [60].

Papers in this area have typically introduced new systems [6, 13, 16] or more generally concerned the engineering of systems [11, 14, 46, 81, 85], though others have discussed emergent narrative through the lens of narrative theory [47, 48], creativity [10, 42, 62], and improvisation [76, 77]. One class of contributions to the discipline has concerned the particular design practices that are employed in the domain [49, 50, 75]. Most prominent among these practices is the iterative design cycle of crafting a simulation from which certain kinds of stories may emerge, testing for whether those stories do emerge, hypothesizing why they do not, revising the simulation according to these hypotheses, and repeating these steps until the desired stories reliably emerge. To facilitate this procedure, Suttie et al. introduced the notion of intelligent narrative feedback, where a system gives real-time feedback about how well the simulation is satisfying authorial goals [75]; earlier, an authoring tool with a similar purpose was proposed [43].

We contend, however, that this iterative loop fails to capture system performance at its most crucial level—the actual interactive experience. It is only when a player is brought into the loop that an emergent-narrative system materializes as a work of interactive storytelling. Iteratively tuning a simulation will certainly produce a better simulation, but a finely tuned simulation will not necessarily yield a well-crafted interactive experience. We subscribe to the stance articulated elsewhere that AI systems that are intended to support new types of interactive experiences cannot be truly appraised except through actual implemented experiences that get built atop them [41, 52, 74, 84].

Let us look then to implemented interactive experiences in this domain, which have largely been games like The Sims, Dwarf Fortress, and Prom Week. We assert that these experiences, though wildly successful in many respects, exhibit a series of major shortcomings that, in turn, raise significant design challenges for emergent-narrative systems. First, systems from which narratives emerge tend to yield these by virtue of a complex underlying simulation, but often the richness of this simulation (and the very stories that emerge from it) is not made apparent to the player. This problem has prevailed since the earliest emergent-narrative systems and, fittingly, has been called the Tale-Spin effect [83]. We believe it will continue to persist until our first two design challenges are met: we must invent new authoring strategies for yielding modular content and we must develop new compositional representational strategies. Next, systems from which narratives emerge are typically unable to discern those narratives from the uninteresting event sequences that more commonly appear. When this happens, emergent stories may not get showcased by the system, and in turn they may go unnoticed by the player. This problem represents a nascent task area and our third challenge, story recognition, for which little work has yet been done. Lastly, even if a system is able to recognize some emergent story, how should it showcase it? We call this last challenge story support, and conceive of systems that could showcase (and support) emergent stories as they are unfolding.

In this paper, we introduce a research framework for the design of interactive experiences in the domain of emergent narrative. Specifically, we motivate and discuss each of the above design challenges and, for each, summarize relevant prior work and propose new approaches that future work might take. Because our concerns are at a level of system design (the player experience) above what has typically been discussed (simulation crafting) in prior work directly situated in this area, we more often refer to promising work in other domains. Likewise, because we are most interested in widely disseminated interactive experiences, we use systems like Dwarf Fortress and The Sims, rather than FearNot! and Virtual Storyteller, as examples. It is our hope that this paper will encourage new projects that may advance the medium of emergent narrative by taking on these difficult challenges.

2 Challenge 1: Modular Content

By content, we mean here the material used to express the underlying system state to the player, such as the animations and Simlish icons in The Sims or the textual dialogue in Prom Week. To the degree that such content is instantial (i.e., non-procedural or ‘canned’), authorial burden grows monotonically with a system’s state space. This is intuitive: the more states a system can get into, the more states that must be expressible by the system, and thus the more content that must be authored for it. So while, for instance, games with huge state spaces are often lauded for this very enormity [4, 38, 87], that same property yields a serious authoring challenge: when a system cannot express many or most of the states that its simulation yields, the latter will appear to the player much simpler than it in fact is—this is the Tale-Spin effect, mentioned above [83]. Because its systems often employ rich simulations that exhibit huge state spaces, this problem is endemic in emergent narrative. Note that there are other forms of authored material, such as the Edith scripts associated with objects in The Sims and volition rules in Prom Week, that already exhibit modularity and thus avoid this blow-up of authorial burden. But a player’s experience of this authored procedural material (modularized simulation elements) is gated by the expressive content, which unfortunately tends to be instantial.

This issue is best alleviated by more content, but for games with particularly massive state spaces, it is not feasible to author by hand as much content as would be needed. Consider the case of L.A. Noire, a AAA game that does not have a massive state space, but for which a team of authors produced a script exceeding 2,000 pages [32]. This accumulation of dialogue is commensurate to that of ten full-length motion pictures—all this for an interactive experience that is very linear. The game, inasmuch as its narrative is concerned, cannot get into that many states—how else could it have a script? If this is the authorial burden commanded by L.A. Noire, imagine what is commanded by a system that can get into an essentially infinite number of states. The fact of the matter is that, in emergent narrative, standard authoring practice provides an author no hope for producing a base of content sufficient to give even marginal coverage to a massive state space.

2.1 Potential Approaches

We need to invent new, smarter authoring practices that are tailored to accommodate the massive state spaces and nonlinear properties that are characteristic of emergent narrative. We propose that such a scheme should exhibit two properties: first, with relatively little effort, a human should be able to produce many units of content that each express specific aspects of underlying state; second, these units of content should be largely independent of one another, but in a way that still affords sequencing and recombination.

Let us ground this out in an example. Prom Week [55] is a simulation game that features human-authored dialogue exchanges between NPCs. Each of these dialogue exchanges is composed of five to ten lines of dialogue and has on it a set of precondition rules that specify what must be true about the storyworld for the exchange to be enacted [70]. For instance, a precondition rule might enforce that a dialogue exchange only be enacted when the two characters who would carry it out are dating. But only some subset of the lines of dialogue that make up this exchange are likely to actually depend on the characters dating, which means that all the exchange’s other lines (that do not have this dependency) could have very well been used in cases where the characters were not dating. This represents misspent authoring effort, in that this content gets deployed less often than it could be. In [71], we worked to break down Prom Week dialogue exchanges into their constituent lines of dialogue (and then annotated the lines for their individual dependencies) in order to facilitate them getting deployed more often in a way that would increase coverage of the game’s state space. An obstacle arose, however, in that many lines strictly depended on others (e.g., due to anaphora) and thus could not be used independently of them.

From this exploration, we impart two general lessons that correspond to the content desiderata we outlined above: good content in emergent narrative should express one or few specific aspects of system state and should be as context-independent as possible, while still supporting content sequencing and recombination. This way, small units that each express individual things may be flexibly recombined into larger content units that express all those things simultaneously. Moreover, by being sequencable, content units may be used in a coordinated way that affords emergent linear experiences (e.g., by having units reference earlier ones). Content should also be explicitly marked up for what it expresses about underlying state. When this is done, a system may be able to reason about its current state at any time in order to select content (or recombine content into a larger unit) that expresses that state. Currently, we are developing an authoring tool whose design is specifically informed by these two lessons [72].

3 Challenge 2: Compositional Representational Strategies

Related to the severe authorial burden endemic to emergent narrative is another challenge that pertains to the actual deployment of content. Rather than the makeup of individual content units, we are concerned here with how such units may be deployed simultaneously in a coordinated expression of underlying state. In systems underpinned by simulations whose primitives (and the procedures that operate on them to evolve state) are easily expressible, system state can be expressed compositionally by deploying content units that collectively express all active simulation primitives and procedures. This is classically the case in systems that simulate Newtonian physics. Let us consider Angry Birds [68], a game with a minor physics simulation whose primitives are the positions of game objects and whose procedures are the forces of classical mechanics. While Angry Birds can get into a lot of states, it has no trouble expressing any of them because these primitives and procedures happen to be easily expressible using graphical logics, which afford a particularly feasible representational strategy. By ‘representational strategy’, we mean a strategy for expressing internal processes at the surface (usually through the deployment of expressive content). Graphical logics are a brand of operational logics (abstract procedural tropes) by which a system may model things like movement and collision quite easily [53]. While graphical logics can be used rhetorically to make different kinds of meaning [79, 80]—this has been done compellingly in games like Passage [67] and Dys4ia [7]—they really work best for expressing state in simulations of physical spaces.

So what representational strategy would afford compositional expression of state in a simulation that models, say, character internal state, as would be typical in emergent narrative? This is an open question, and it appears that until new (or currently immature) representational strategies are developed specifically for expressing things like this, experiences underpinned by simulations of such will not be able to express state compositionally. This means that, lacking such a strategy, designers of these experiences must author content units that essentially are each meant for big chunks of system state. But the better a content unit expresses a particular compound state, the more dependent it becomes on that state, and so the less generalizable it becomes to other states and the less often it can be deployed, as we discussed in the last section.

3.1 Potential Approaches

This is perhaps the hardest challenge we present in this paper, but we propose one potential compositional representational strategy that employs generative dialogue and procedural animation. A number of projects have explored using techniques from natural language generation to facilitate generative dialogue in interactive narrative systems [20, 35, 51, 63, 69]. A handful of other projects have explored expressive procedural character animation [36, 57]. If each character in an underlying simulation could express her internal state at the surface through bespoke dialogue or animation, the system could express its underlying state compositionally by enacting all such procedures for all (on-screen) characters. Another compelling approach would be to utilize a modality that conventionally has not been used to express character internal states: sound. Indeed, Ian Horswill is currently exploring this in the experimental game MKULTRA [34].

4 Challenge 3: Story Recognition

Systems whose narratives emerge from simulations currently have no way of discerning the very stories they support. To illustrate this, let us consider perhaps the most lauded work of emergent narrative, Dwarf Fortress [3]. A roguelike set in procedurally generated fantasy worlds, Dwarf Fortress is best known for its rich underlying simulation. This game is often talked about in terms of the stories that emerge from this simulation (both by fans [1] and academics [39]) and its creator, Tarn Adams, has called Dwarf Fortress a “story generator” [86]. Undoubtedly, its simulation generates narratives—but does it know that it does?

There is typically no explicit narratological modeling whereby narratives in simulationist systems get composed; this would constitute a top-down approach to story generation, but simulations work bottom-up. As in other emergent-narrative systems with sufficiently complex underlying simulations, stories happen in Dwarf Fortress only incidentally; they are remarkable event sequences among a huge boiling stew of things happening. While humans who play experiences like Dwarf Fortress are capable of recognizing which event streams are storylike, the system itself is not. We call this challenge story recognition: how does one make a system that can discern stories embedded in the morass of data that its simulation produces?Footnote 1

4.1 Potential Approaches

Story recognition is related to story understanding, in which a system processes an event sequence and attempts to understand the story it represents by attributing explanations to the events that account for causal and temporal relations among them. Though related, story understanding is a different task than story recognition. Systems that do the former operate over storylike event sequences as a given, while systems doing the latter must excavate such sequences from larger accumulations of data. In this sense, story recognition may be thought of as a preliminary task to story understanding—a story’s event sequence must first be recognized and compiled before it can be understood, though of course a system that does story recognition will probably have to operationalize a rudimentary notion of event temporality and causality, i.e., storiness.Footnote 2 To further distinguish the tasks, work in story understanding has typically focused on artifacts like newswire stories [25], while in story recognition the central artifact is a simulation’s event stream. Still, it is likely that techniques or insights from work on story understanding could inform the task of story recognition.

We are aware of preliminary work on story recognition outside the domain of interactive narrative. A handful of recent projects have explored recognizing storylike event sequences from structured representations of sports games (e.g., baseball box scores) [5, 15, 44]. Pablo Gervás has been actively exploring the generation of stories from event-sequence data in chess [29]. In [31], event logs constituting the lives of characters in a social simulation are curated by the system to produce stories that interweave character biographies. (We build on lessons from this preliminary work in our proposal at the end of this section.)

One approach would be to assume that the trace of player actions in a system playthrough will typically represent a storylike sequence, since it may be expected that players will tend to interact with the storyworld in interesting or meaningful ways. In another project, however, we found that players of Prom Week cannot be relied upon to produce storylike gameplay, which works against this intuition [8]. However, by generalizing story recognition to mean making inferences about gameplay event-sequence data, prior work on both goal recognition and gameplay summarization becomes useful for resolving this problem.

In goal (and plan) recognition, a system attempts to infer a player’s goals (and plans) from her playing behavior [23, 30]. This is often done as part of a player adaptation scheme, wherein a system dynamically adapts gameplay to improve player satisfaction [88]. In gameplay summarization, a system curates the event sequence constituting a gameplay session in order to summarize it [8, 26, 61]. These tasks differ from that of story recognition in that they are concerned with gameplay itself, not emergent stories that may be embedded in a gameplay session (or in parts of a simulation that are removed from player input). Still, we propose that they are similar enough to potentially inform our task here.

Finally, we propose a method whereby a human specifies interesting event sequences that the system will then attempt to match against sequences generated by its simulation. Indeed, a variant of this method has actually been employed in The Sims 2, as we discuss in the next section [17]. One concern here is that an author may not wish to specify precise event sequences, but rather higher-level patterns with major events that must remain constant and allowances for extraneous events that may be interspersed among those. For this, we believe Playspecs, a new formalism that supports regular expressions for play-trace data, could prove quite useful [58]. Relatedly, prior work in story understanding provides knowledge frameworks for expressing at higher levels of abstraction desired properties of storylike sequences. We are currently exploring this approach.

5 Challenge 4: Story Support

The last challenge that we will present is an extension of the previous one. Once a system has recognized a storylike event sequence that has emerged from its simulation, what should it do with it?

One thing the system could do is retell the story, either after gameplay or during it, perhaps by having NPCs conversationally relate stories about in-game events. This task would be quite related to prior work on gameplay summarization [8, 26, 61], but in this case the impetus is on summarizing a particularly interesting subset of gameplay events, not an entire gameplay sequence.

Perhaps more interestingly, a system could recognize partial event sequences as they are happening in order to influence the simulation or gameplay in a way that would support the emergence of interesting stories (i.e., interesting completions of those partial event sequences). We will call this design challenge that of developing methods for story support. This problem may appear to be very similar to narrative planning [65], drama management [66], or game mastering [12, 19, 27, 60]—these are certainly related notions (the latter might even be called an approach to story support), but we mean to encourage techniques that do not significantly compromise the integrity of the simulation, but rather gently nudge it toward the emergence of certain desirable event sequences. In other words, story support is not about enforcing some degree of narrativity on the simulation, but rather subtly manipulating it to facilitate and foreground emergent stories. Indeed, simulationist systems are appreciated for the emergent quality of their narratives [4, 38, 87], not necessarily the well-formedness of these stories according to narratological or dramatic concerns, and so we encourage the development of techniques that may promote emergence above other concerns.

5.1 Potential Approaches

One notable approach to story support was featured in The Sims 2 [17]. In that game, characters have fears and aspirations that are expressed by tree data structures that specify event sequences by which certain fears or aspirations may be realized. For instance, a teen character may aspire to have her first kiss, and so the event sequence may include events like meeting, becoming romantically interested in, and eventually kissing another character. As gameplay proceeds, the system parses its event stream to check for partial completions of the sequences specified in characters’ trees, and if a match is found, the system may nudge the simulation toward the event that would lead to that sequence’s completion. Once a given sequence culminates, the system triggers content that will showcase the story it represents. We note that this particular aspect of the game was received favorably by critics [2, 59].

6 Conclusion

We have introduced a research framework for the design of interactive experiences in the domain of emergent narrative, an application area of computational narrative in which stories emerge bottom-up from the behavior of autonomous characters in a simulated storyworld. Prior work in this area has largely concerned the development and tuning of the simulations themselves from which interesting stories may reliably emerge, but we have argued that this will not necessarily improve system performance at its most crucial level—the level of interactive experience. Looking to completed experiences in this area, namely games like Dwarf Fortress and The Sims, we assert a series of major shortcomings that yield four design challenges. First, the richness of underlying simulations (and the very stories that emerge from them) are often not made apparent to the player. We have argued that it will continue to persist until our first two design challenges are met: we must invent new authoring strategies for yielding modular content and we must develop new compositional representational strategies. Next, systems from which narratives emerge are typically unable to discern those narratives from the uninteresting event sequences that more commonly appear. When this happens, emergent stories may not get showcased by the system, and in turn they may go unnoticed by the player. This problem represents a nascent task area and our third challenge, story recognition, which we have outlined. Lastly, even if a system is able to recognize some emergent story, how should it showcase it? We have called this last design challenge story support and forecasted systems that may be capable of supporting and showcasing emergent stories as they are unfolding. It is our hope that this paper will spur new projects that may advance the medium of emergent narrative by taking on these difficult challenges.