From Linear Story Generation to Branching Story Graphs

Interactive narrative systems are storytelling systems in which the user can influence the content or ordering of story world events. Conceptually, an interactive narrative can be represented as a branching graph of narrative elements, implying points at which an interactive user's decisions influence the content or ordering of the remaining elements. Generative approaches to interactive narrative construct narrative at runtime or preconstruct--on a per-session basis--highly interactive branching narrative structures. One generative 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 narrative structures, then linear narrative generation techniques can be applied to interactive narrative generation. This article lays out this argument and sketches a proof that narrative mediation is at least as powerful as acyclic branching story structures.