Interactive narrative has been defined as “a timebased representation of character and action in which a reader can affect, choose, or change the plot” [23]. Derived from experimental literature, the first interactive narratives to be written were textbased hypertexts (eg. [28]). This kind of branching structure between media chunks has since been applied to multimedia and video based interactive narrative systems. The resulting experience for the reader/viewer is a linear narrative that may have a three act restorative structure irrespectively of its partially interactive mode of presentation. Traversing these systems is not game play, since it involves selection rather than problemsolving or competition. Nevertheless, branching narrative structures can also be applied within game design, as discussed below, and in this case branching decisions may be made automatically based upon the consequences of play.
Possible structures that an interactive narrative may have (summarised from [6]) include:
 tree (most common in textbased works due to cost)
 exploratorium, a linear structure in which the player can pause to explore the surroundings [33]
 parallel plot structure, in which different versions of the story are told at the same time and the reader/viewer can switch between the different parallel versions (see [24])
 nodal, or deadend structure, typical for action/adventure games, involving numerous alternative paths and deadends, which may or may not be (but usually are) reversible, generally along a main sequence eventually leading from the beginning of the game to the end ([32], [23])
 modulated, or the dynamic labyrinth structure, provides constellations of interactive choices, but only allowing access to a new set of possible interactions after the player has experienced different parts of the story [24]. Game levels function in this way.
 an open structure in which sets of story elements are associated with different physical places; links between places are open, so the player can wander around discovering different elements of the story [33]. This is the form typical of early adventure games.
 an open structure in which there is no story arc. This is the form typical of simulationbased games, strategy games and open worldbased games, like massivelymultiplayer online roleplaying games (MMORPGs) [23].
Looking at these models from the perspective of computing science, it is possible to see that they manifest three levels of structure that can be modelled in terms of formal graph theory:
1. an atomic graph level providing the components for defining the graph structure and behaviour representing the interactive structure of the narrative. The atomic graph level includes the following elements:
 nodes (also called vertices)
 links between nodes (also called edges or arcs)
 constraints upon links. These may include:
 links may be directed or not (directed means only oneway travel along the link)
 links may be conditionally available (eg. if a key is found, a plot point has been discovered, or the level boss is killed). While Murray [24] has referred to these as dynamic links, here they are referred to as conditional links, since each of these links exists at all times, with a fixed source and a fixed destination, in this sense being static but having conditions that must be satisfied before they can be traversed. Conditions upon links may include disjunctive conditions (one of A or B or … is satisfied) and conjunctive conditions (all of A and B and … must be satisfied), where the terms may be further arbitrarily decomposed into disjunctive and conjunctive conditions
 directed links exiting a node may be exclusively available (ie. only one can be chosen), inclusively available (any subset may be chosen), or may have dynamic availability (choosing one link enables and disables others exiting the same node)
 nodes may be restricted to having only one entering link, or may have multiple entering links
2. a high level topology, giving an author the overall shape of the interactive narrative. The graph topology from an abstract perspective is independent of how it is used in relation to a model of story form. The decision of how to map story form onto network structure is a design and authorship issue. Graph theory provides a number of specific concepts for describing the form and properties of graphs based upon the nature of their links and the topology of link connections. Some of these are:
 a complete graph is one in which every node is connected with every other node
 a multigraph is a graph with multiple links between the same nodes
 a walk is a series of links connecting one node to another via an arbitrary number of intermediate nodes (possibly none); a path is a walk having no recurring nodes; a trail is a walk having no recurring links; a cycle is a walk that returns to the starting node
 a graph is connected if it has at least one node and there is a walk connecting every node within the graph
 a digraph is a graph having directed links
 the degree of a node is the number of links connecting to it; for a digraph this includes the indegree, or number of links entering the node, and the outdegree, or number of links leaving the node
 a forest is a graph that is acyclic, ie. has no cyclic nodes, while a tree is a directed acyclic graph, or an acyclic digraph
3. a node substructure, constituting what the nodes contain. Since a node can in principle contain any kind of interactive narrative structure, interactive narrative structures may be arbitrarily nested, using either the same or different structures within the content of what is a node at a higher level. For example, the nodal or deadend structure described above could be modelled as a linear sequence of nodes in which each node represents a game level; the interactive story possibilities within each node could then be represented as smaller scale networks.
In addition to graph theory, it is also useful to look at classical or naive set theory as an additional source of concepts for describing interactive narrative structure. Some relevant concepts include:
 a set is defined as a well described collection of objects, referred to as elements or members of the set
 a totally ordered set is a linear sequence, having a specific ordering of its members
 a partially ordered set, or poset, is formally defined as a set that is reflexive, antisymmetric and transitive, but here can be regarded informally as a sequence that has branches that diverge and/or converge. Graphs can be used to illustrate the order of posets.
The earlier mentioned models of interactive narrative structures can now be described in these more specific terms:
 an exploratorium is a sequence having nodes that are sets of narrative components; if the accessibility of components within each node is to be modelled as a graph, then it is a complete graph, ie. every object within a node is connected to every other object within that node
 a parallel plot structure consists of parallel sequences with links between those sequences, constituting a digraph
 nodal, or deadend, structures are connected graphs, and may be more specific depending upon their particular form
 modulated, or dynamic labyrinth, structures are also generic graphs, but with conditional access to subgraphs
 an open structure maybe either the same as an exploratorium, except that the high level structure is a branching graph rather than a sequence, or a complete graph
More importantly, the kinds of graph and settheoretical concepts described above provide a language for specifying a much greater variety of interactive narrative models that any of the small number of specific models described here.
Some further points about these methods of specifying interactive narrative structure:
 while a graph model may be used, with node contents being recursively specified by graphs, this recursive decomposition stops with either graphs having nodes, or sets having members, corresponding with story components. In interactive 3D games those components are things such as plot points presented in cut scenes, associated state changes, level advances, items or benefits lost or gained, and specific game challenges including individual opponents to be killed, puzzles to be solved, quest goals to be achieved, and quest goals actually achieved. Interactive movies will have components such as video sequences and hypertexts will have text chunks, perhaps with static 2D graphics.
 terms from graph theory can provide more precise descriptions of interactive narrative patterns than terms like “parallel plot structure” or “deadend structure”. However, the latter terms may be more meaningful in terms of how it feels as a player to move through those structures. Hence it may be useful to use both informal descriptions and more formal descriptions, where the informal descriptions address the mapping of narrative function onto the graph model and the more formal description is more precise in how the graph functions and is traversed.
 for framing narratives, branching structures can be used to allow game play decisions to have an impact on the high level story, perhaps enhancing the feeling of the narrative significance of performing game moves for the player. However, the higher the level of narrative structure, the more expensive it will be to produce any kinds of branches. This is a strong incentive against using exclusive branch patterns (ie. branches that are exclusive alternatives) in high level narrative models, unless the underlying content is cheap to produce. Most graphically rich computer games that use a high level narrative framing for game play either 1. use inclusive branching, all players being intended to traverse all or most of the branches (eg. adventure games), or 2. use a highly linear framing narrative, so that once again all players access most of the same narrative material. Otherwise, if exclusive narrative branches are used, for any single player there is far more material in the game than that player will experience (without repeat playing through a whole game arc); this is generally regarded as an unnecessary and expensive redundancy of game content. This is why exclusive branching patterns are more commonly found in hypertexts, where the story content is relatively cheap to produce.
 the graphbased model of interactive narrative structure is a representation of causal dependencies between and among game actions and states. It is not necessary to use any such representation. If it is used, it can be used for textual/graphical representation of narrative structure during game design. Ideally this should be supported by tools that map those representations directly into game scripts for implementation, or game scripting languages should have the ability to directly express those graph structures and their associated features and constraints.
In stating that it is not necessary to use a graphbased model of narrative structure, there are many benefits in doing so. However, considering the example of games in which the player’s moves map onto low level ingame player character actions, it becomes completely impractical to map out all of the possible story alternatives at a low level. The transition point is the boundary between higher level designed story patterns and lowerlevel designed potential for the emergence of story material. The boundary will not exist if either:
 the “game” is produced as a branching narrative structure over noninteractive story components. Game play will then be a matter of resolving the conditions required for progress within the branching narrative structure in the manner of a classical “pointandclick” hypertext or adventure game
 no predefined narrative structure is used, the designers focussing exclusively upon low level action generation; if story content is still of interest the designers in this case must design story potential into the system, with higher level story structures emerging as a consequence of player actions.
High level inclusive branching or sequential linear designs are often used for level design. This is not necessarily for the sake of creating a sense of story, other than the weak story of increasing character capacity through increasing levels of difficulty, or adding incidental interest to game play by thematic variation of game space topology, style and decoration in different levels (eg. the first level is the Town, then the Wilderness, the Underground Complex, the Caverns, then the Forest, the Castle, etc.). This is also very different from using told story material in the form of cut scenes to present a framing narrative context. Changing settings can reinforce changing narrative functions of game subspaces (the journey starts in the town, within the underground complex the hero must search within her soul, the villain lives in the castle, etc.) but are not in themselves intrinsically narrative.
