From Linear Story Generation to Branching Story Graphs

Narrative is an important part of the way we interact with and make sense of the world. Interactive narrative systems tell stories in a virtual world in which the user is an interactive participant. Since the behaviors the user performs in the virtual world can affect the way in which a storyline unfolds, interactive narrative systems often use a branching story structure where non-interactive story presentations are interleaved with user decision points. An alternative approach — narrative mediation — represents story as a linear progression of events with anticipated user actions and system-controlled agent actions together in a partially-ordered plan. For every possible way the user can violate the story plan, an alternative story plan is generated. If narrative mediation is powerful enough to express the same interactive stories as systems that use branching story structures, then linear narrative generation techniques can be applied to interactive narrative generation with the use of narrative mediation. This paper sketches out a proof that narrative mediation is at least as powerful as acyclic branching story structures.