Best Practices for Procedural Narrative Generation

[Music] Hello everybody. Um I'm Chris Martins and this is Roelio Cordona Rivera. Uh we are both at North Carolina State University and we're both really excited to be here uh to tell you about some of the things that we've learned about as uh researchers. So we are both researchers at NC State. Um I just started there as faculty in the fall and Raelio is finishing up his PhD. Um, I do work on tools for rapid prototyping of interactive stories and Raelo does work on computational models of how players think about interactive stories. Uh, so this is our first GDC talk. We are really excited. Um, we're we're kind of motivated by um this idea that in academia we have a whole lot of techniques that people have explored and debated over the years. Um, and when I come to conferences like GDC, um, I talk to a lot of people who are who are saying like, I really want to create a procedural story and I have no idea how to get started. So, uh, we're hoping

that we can share with you some some interesting ideas and techniques that you may be able to use in your designs. So, um, a lot of academic work as well as a lot of early game development work started by sort of being inspired by this idea of the hollow deck from Star Trek. Um, in other words, a simulated reality that affords not only the experience, an immersive experience of a story that you can enter and take part in um as a a reader of sort of a script, but also a reality in which you can take improvised actions and have this the system respond in a meaningful way to those reactions. Um, in the early days, this was kind of realized through some of the uh early adventure games like the Hobbit DOSs game from Beam Software in 1983. Uh, and on the surface, adventure games like this sort of seem to offer the promise of the hollow deck, sort of showing you these um first-person images of spaces that you could inhabit and and

narrating story around you and allowing you to make some kind of choices. Um, and ultimately these experiences centered a particular kind of plot and progression. They they really wanted you to in some sense follow the script of what the designer had in mind. Um, but they're not very permissive of the kind of spontaneity and improvisation that people initially sort of um fantasy designed in the Star Trek holiday. More recently, people have been very excited about the idea of emergent gameplay realized by games like Dwarf Fortress, um, in which there's a rich simulation underlying this game system and players can play players and the artificial agents within the system can very much improvise and have the system respond. Um, and then people perceive that sort of there are narratives that that get overlaid on top of these experiences. Uh, for example, many people like to post on Reddit uh detailed descriptions of their narrative experiences within Dwarf Fortress that

that they think are are really compelling. So, this is sort of representative of the other end of a spectrum in a sense. Um, these these experiences are very permissive of player and procedural spontaneity, but on the other hand, there is no enforcement of sort of authored narrative arcs. So just as a working definition for those of you who may not have encountered the term procedural narrative generation before, I'm including both of these things under this umbrella term. Um, and basically considering any kind of automatic process that creates a narrative over time where that narrative is not determined at the outset uh before the process begins to be procedural narrative generation. So, I've given a couple of examples and I'm listing a few more here, including some that I think are a bit lesser known that I'm really excited about um as examples in procedural narrative generation. And I kind of have these, you know, loosely following a spectrum of prioritizing agent spontaneity uh to prioritizing authoral structure. And largely what this talk is about is the challenge in uh first of all introducing agent

spontaneity in the first place. this kind of improvisation and and simulation, but also how to balance it with author structure. So, going forward, um I'm gonna show you just a simple example that we can use to walk through a lot of the terminology and ideas and then we're going to go through in detail a couple of approaches, the simulation ccentric approach and the plot-centric approach um that have been really thoroughly explored in academic research. Um and then Raelio is going to uh well Raelio will will talk about the plot-centric approach and he'll also conclude with some of the ongoing challenges uh in procedural narrative generation. So the example that we're going to start with is an ASUP fable um largely because as fables tend to be relatively simple and small and they can fit in a talk slide. Um so the uh so this is the the ant and the dove. So a dove saw an ant fell fall into a brook. The ant struggled in vain to reach the bank, and in pity, the dove dropped a blade of straw close beside it. Clinging to the

straw like a shipwrecked sailor to a broken spar, the ant floated safely to shore. Soon after, the ant saw a man getting ready to kill the dove with a stone. But just as he cast the stone, the ant stung him in the heel so that the pain made him miss his aim, and the startled dove flew to safety in a distant wood. Uh, the moral is at the bottom. A kindness is never wasted. So when we start to think about how to introduce some kind of generativity into the story um or interactivity which ideas are closely interrelated um one technique that underlies a lot of uh that opens up a lot of possibilities for procedurality is logical modeling. So some kind of formal representation of who the characters are and what situations they're in and how those situations change across story events. So if we first think about discretizing this story into kind of a comic book form uh where we show different narrative situations in each panel, we can start describing um each situation in a a sort of formal logical form. So

we can represent this first panel where the ant is uh near the stream getting ready to fall into the stream as uh the ant being thirsty and the ant being at the left shore. Uh the next panel is uh where the ant falls into the stream. So we can represent that as ant at ant stream and the dove is above the stream and so on for the rest of the panels in kind of the first half of this story. So that's our formal representation of a little example story. And now I'm going to go through the simulation ccentric approach. So the basic idea with this is that you're going to design the author is going to design a bunch of characters and sort of world elements and identities in terms of their uh personalities, desires, and relationships to one another. Then give a whole bunch of rules describing how these entities can interact with one another and potentially change those properties. Uh then you kind of throw them into a world and press play and see what they do. Uh so you have your

designer who's going to feed these interaction rules and initial state into a story generator and then that whole thing kind of gets packaged up and becomes an interactive narrative which then the player can interact with in the usual way by uh submitting actions and receiving responses. So we're going to zoom into specifically what the authoring process looks like uh for this kind of approach and uh we're going to look at what's what interaction what it means to design interaction rules. So an interaction rule is basically a transition between story situations. Basically going from the ant is beside the stream and thirsty to the ant being in the water. Um, we can label this transition with a story event like the ant falls into the stream. And to make this formal, we simply have to think about our logical representation of each of these situations and then give a formal label to this transition event. Um, the next thing that we do in order

to start introducing generativity into the story is to make the rule more general. So I'm using a particular kind of quirky syntax with um this question mark which designates a variable which is an argument to the rule uh that can range over any character. Basically any character can be substituted into this rule to have it apply to them. Um so we could say if someone is thirsty and someone is at a location somewhere and that somewhere happens to be near a stream then one way their situation might transform is that they could fall into the stream and become in the stream. Um, it's important to know that when we're representing things formally like this, we also have to uh make sure we're preserving information that doesn't change. So, if our situation doesn't change the fact that this location is near the stream, we have to repeat it on the other side. Um, so that's enough dense syntax for now. We're going to go back to pictures. Um so we'll represent this kind of uh rule with a variable in it with this um you know outline of a person uh to say if the person is thirsty and the person is near a stream then the person can fall

into the stream. So that's one way of introducing generativity is sort of generalizing these interaction rules uh into things that can be instantiated with multiple characters and entities. Another way is to introduce choices into the world to sort of say that well if a person is near a stream and thirsty then they might fall into the stream and we can label that rule drink fall. On the other hand we could have a rule called drink succeed in which they don't fall into the stream and simply stop being thirsty. Other kinds of interaction rules we can represent with this rulebased style include movement for uh movement to location. So if a character wants to move to a particular location that they happen to be near, then they can simply transition to being in that new location. Uh more interestingly perhaps we can also represent social interaction rules. So we can say something like if two characters X and Y are in a shared location and X doesn't like Y then um they can transition into a situation

where they don't like each other and we can call this this uh story event insulting X insulting Y. We can also represent social interactions like helping. So if somebody uh has a cure for uh if somebody named X has a cure for an ailment that somebody named Y has um and X happens to like Y then um perhaps they uh spend the cure to get rid of the element and now Y is grateful to X. So those were just a few examples of the kinds of interaction rules that you can create in a simulation. And then I mentioned before that you also have to feed in an initial state. So what does that look like? Initial state is simply a uh sequence of logical operators representing the situation that the story is in before the simulation begins. Uh so for example the dove being on the shore um sorry the the dove being above uh above the shore at the street at the treetops the ant being at the

shore and um other properties of the world that will be manipulated by these rules then when this is actually executed at runtime um what happens okay so the algorithmic concept is that our system is going to randomly explore this state space and more concretely as an example What that might mean is that uh we start with some initial state including the locations and relationships between the world entities and then we take a random movement in a particular direction like say the ant moves to the stream and note that the other part of the situation wherever the dove is and which locations are near each other and so on uh doesn't change across this transition. Then we can follow that with another part of the sequence where the dove moves to the stream. Now both of the characters are in the same location and some interaction might take place between them. On the other hand, we might start from the initial state and first move the dove and then move the ant which takes us back to the uh same

situation as doing so the other way around. So in doing this, we are creating not what you may be more familiar with is sort of like a branching story tree but rather um a branching story graph where things might connect to the same node. Um, so a concept that we could consider for sort of generating stories includes randomly exploring the state space. Um, but a perhaps more useful way to think about it as sort of interactive experience designers is that we can also include the player in the loop and allow them to control some of the steps through the state space. uh and whether it's a player or an or an automated uh decision maker taking these steps we can consider each traversal through the state space to be approximately a story. So sometimes of course these things may not be very interesting stories uh but some of them might be. So if uh you know the ant moves towards the stream and the dove moves towards the stream um the ant could insult the dove and then the dove might eat the ant.

Uh in terms of interacting with simulations, there are of course a lot of design questions to ask for using this technique. So uh one of the one of the biggest ones is where is the locus of control? How can the player intervene in the narrative? Are they playing as one character? Are they able to manipulate all of the characters in the story and completely control what takes place in the simulation? um or are they perhaps able only to um subtly manipulate the world around the characters as they go about their you know daily activities um using these interaction rules and try to subtly manipulate their behavior in that way. Uh there's a couple of examples I wanted to highlight. One of which is the game prom week uh which came out of research from UC Santa Cruz uh in which the player does get to control all characters but kind of one at a time. So they select one character who's the actor and then another character that that first character will act upon uh and they get to decide what kind of interaction will will be started but how that second character responds is automated. Um, another example is Blood

and Laurels, um, which uses the Versu storytelling engine. And in that, uh, in that case, it's it actually plays a lot like a like a traditional choice-based narrative, but all of the choices that are presented to you are generated by the simulation possibilities underlying the world. Okay. And so with that, I am going to pass this off to Roelio, who's going to tell you how to actually introduce some kind of control over your dramatic arcs that unfold. Hi everybody. I'm super excited to be here. So in order to set up a specific narrative progression, which you won't have in the simulationcentric approach because you kind of get to decide where the narrative is going on the fly, you need a way of specifying and enforcing goals, which is again achieved through the techniques that I'm going to outline. However, the plot-centric approach does build upon the simulationcentric approach. So you you need to describe you know what is the initial state of the narrative universe as well as what are the interaction rules that allow the states of the

universe to change. Additionally you require a narrative agenda. So the agenda represents the desired plot that you as a narrative designer want to have happen in terms of the trajectory through the state space that Chris was describing. So to give you a kind of diagrammatic representation of what's going on, this is the diagram that Chris finished upon. And we're going to just shift the story generator to the left. And in addition to specifying, like I said, the initial state and the interaction rules, you also have the narrative agenda. Now the story generator in creating this story actually needs an additional agent storytelling agent and one will generate the partial story structure which is the generator and the other will try to enforce that story structure. So there's this idea that you have the narrative agenda that you want as a designer to have happen in the interactive narrative experience. You now need an additional agent that will monitor what the player is doing and try to get the player directed on that narrative trajectory.

So the partial story is created, passes to this agent called a story mediator agent and the player once again takes actions that the mediator interprets. It then requests story content from the story generator which in turn in response to the player's actions creates this partial story and then delivers those responses to the player. So you can think of it as an iterative process that takes place between the player and the story system. Essentially they're taking turns advancing the chronology. So the player takes a turn in the interactive environment and then the system responds in turn. So like I said earlier you all you have to describe the initial state as well as the interaction rules that can evolve states. The way that we approach authorship in this plot-centric approach is again I have I have an idea as a designer which of the states in that space are desirable and that is the narrative agenda. So say for example that at the end I want the ant to be at the shore right then what that does in

terms of the simulated world is distinguish a state as desirable which I've highlighted there in that alternative color. So as we specify more conditions in the state space we get a more specific trajectory of the interactive narrative. So the more that we specify the more we have in terms of constraints of things that we as designers would like to have hit during the progression of the player. And this sets up nicely the first technique in the plotcentric approach which is this notion of beats. So the idea that you have some state you have the states of the state space and a subset of those states which are the desired ones. And in the literature you'll find these referred to as beats. The second technique in the plot-centric approach is this notion of turn taking which I kind of alluded to and you can think of it through an analogy through uh Dungeons and Dragons when you roll for initiative, right? You you the DM have players roll for initiative, establish the turn order of players, then the players go and the DM responds in kind. So the DM and the players take

turns advancing the narrative arc. So the same principle applies here. From the initial state, the player is allotted or afforded the opportunity to take action in the state space and then the system is allowed to respond in kind. And so this continues throughout the progression of the plot structure. And the third technique is that idea of mediation which I talked about earlier, the notion that there are some actions in that state space which essentially take us away from the desired plot points. So we have the beats that we have specified in the narrative trajectory and any action that takes us away from those beats from the systems perspective constitutes an exception. We want to avoid those because we want to hit those plot points during the progression of the player's experience. So those dotted arrows that I'm highlighting in the diagram represent those exceptional actions. And so if we consider these beats to be hard constraints, so we don't want the player to deviate from these beats, then the system must fail the user's action when

the player tries to take that or never present the action in the first place and otherwise the system will accept the player's action during the experience. There's actually a third option here, replanning, but this requires a story generator. In essence, if the player tries to deviate from the beat path and you have access to a story generation system, then you can request additional story content to try to replan the experience around the player's interaction and find a story that gets us back on track. During runtime, the plot-centric technique is all about deciding how to evolve the story in response to the player's actions. So, like I said earlier, the player in the initial state will decide what action to pursue for the narrative plot. Then when the systems the systems turn is is is up, it will suggest or the story manager will s suggest which action will get us closer to a narrative beat. And so this interaction, like I said, it's a turn- taking mechanism. And every time the system is afforded the opportunity to interact, it will choose an action that

will get get us closer to the narrative beats. So, some plot- ccentric examples, and I have to call out facade because it is an unstated rule in academic talks that reference interactive narrative that facade must appear at some point. It's part of the PhD manual. Um, so facade is an example where you have the player afforded the opportunity to interact in the environment, but invariably you will hit some specific plot points. Of course, the trajectory that you take to get to those beats will affect the way that the experience culminates. Another example is a game that was developed at North Carolina State by Justice Robertson called Base Case, which in essence, the interactive environment is procedurally generated in response to the player's actions. But it's also with this notion of turn taking. So every time the player acts, the system responds in kind and actually can manipulate things behind the scenes to try to make sure that the player's plot progression is as intended.

So that concludes the plot-centric approach and I want to shift over to talking about some challenges in new frontiers. So one big challenge that is currently uh that we're currently facing as an academic research community is going from this plot-centric approach to a more discoursecentric approach. So this is in service of what Emily Short has called out before, which is there's no need to simulate part of the environment that ultimately will not be told to players because it's not relevant. If it doesn't in some way advance the interactive narrative experience, there's no point in talking about it at the simulation level. So traditionally, systems have gone from this simulation approach where you generate the simulation of the story world and through its state space and then you pick and choose and present over that that state space and lay a discourse above it. And that's ultimately what is presented to players. Ideally, we like to go the other way around. So, the simulation of an unnarrated part of the story is unnecessary. Uh Chris and I actually have been investigating new models of

communication, understanding what is it that we have to communicate to a player and then figuring out the simulation in service of that. And I hope to continue that. That's really exciting work. I think another challenge is this idea of scaling. So, uh, Nano Genenmo, the National Novel Generation Month, where you have one month to create an AI system that generates a 50,000word novel. That's correct. Um, clearly we are not at a state as a as a community where we can do this automatically and ideally we would want to scale our interactive narrative generation systems to encompass a wider story experience. Um there's an interesting problem in that in trying to write a small amount of interaction rules that generate a large body of text. So what is I guess the minimal amount of authoring that we have to do in terms of input to these systems to get a wide array of output. So some parting thoughts. One thing that we feel procedural narrative generation

will get us toward is opening up the possibility in terms of interactive story experiences. So yes, for you talks about this idea of progression versus emergence in terms of the kinds of games that exist. And the basic idea is that you have games in narrative about progression where you have a very linear structured plot, something like what you might find in the secret of Monkey Island where you have some space to explore interactions, but the main plot kind of progresses like checkpoints. you do some actions in the environment, you progress to the next plot point and the progression is very tied to your interactive experience. Contrast that with a game of emergence um where like for example in civilization where you can think of games of emergence as games that are simple to learn and difficult to master. And so the narrative or the narrativization of your experience happens through the interactions that you have in that game. And Chris and I

feel that procedural narrative generation can help move story games which have traditionally been games of progression to explore games of emergence. And this is not to say that these story systems one is better than the other, but we feel that developing these tools and techniques allow us to explore narrative games that exist beyond the traditional mold. And lastly, uh this is um we're both very excited about this. Uh we have a new resource to share with y'all. the story genen.org website which should be live and hopefully you won't give it a hug of death and then knock it out. Uh but so we've compiled a list of procedural narrative generators that represent systems that you can download and play with and we recognize of course that this is some of it is still research software but hopefully that you can actually play with and use to explore these interesting narrative designs going forward. So as a recap, so we've covered you know the simulationcentric approach and plot centric approaches and like I said just

now what we have presented is not normative. You know designer designers still have to decide what the experience will be and hopefully the technology that we've developed in our community can help enable those experiences. We've talked very briefly about some challenges and new frontiers and we really encourage you to visit storyen.org. Hopefully you will be able to suggest new systems. We'd love to have that array of procedural narrative generators expanded. Um, and that's it. I'm Rael Cardono Rivera. This was Chris Martins. Thank you very much. [Applause]