They have created a system for representing "narrative structures" as a set of connected nodes. The nodes are story elements ("tropes") like Hero, MacGuffin, etc., which they have taken from https://tvtropes.org. The connections represent the relationships between the elements, so that their diagram 1b represents:
> The HERO’s goal is to get the “Pendant of Courage” (MCG). However, the MCG derives from ENEMY and BAD, so the HERO must overcome them to achieve his
goal.
This is the "narrative structure" (they say) of the Eastern Palace in Legend of Zelda: Link to the Past. The CAPS words are tropes that you can look up in the paper.
Having established this graph representation of narrative structure, they create a set of rules for deriving other graphs, and so other possible narrative structures, from it (a "production grammar" for graphs, if you know the term).
They then use an algorithm called MAP-Elites[1] to evaluate the variations for fitness in various aspects such as "interestingness" and "coherence", with the aim of creating a system which can generate narrative structure corresponding to satisfying stories.
The structures thus produced don't unambiguously define one linear sequential narrative (because there is no direct temporal sequence given, only the temporal order implied by the node-to-node relationships which are causal in nature.) "The system is ambiguous by design" they say, and later: "the generated graphs could equally describe different stories".
They leave the subsequent "interpretation" or realization of the structure graphs as concrete stories to other systems (to be developed) or to human interpreters.
...at least this appears to be a first cut at defining a vocabulary for the storytelling aspect of the problem.
They refer also to other "Key + Door == Progress" aspects of procedural content generation (ie: make a zone, place a [locked] door to another zone, place a key within the original zone and then recurse).
> The HERO’s goal is to get the “Pendant of Courage” (MCG). However, the MCG derives from ENEMY and BAD, so the HERO must overcome them to achieve his goal.
This is the "narrative structure" (they say) of the Eastern Palace in Legend of Zelda: Link to the Past. The CAPS words are tropes that you can look up in the paper.
Having established this graph representation of narrative structure, they create a set of rules for deriving other graphs, and so other possible narrative structures, from it (a "production grammar" for graphs, if you know the term).
They then use an algorithm called MAP-Elites[1] to evaluate the variations for fitness in various aspects such as "interestingness" and "coherence", with the aim of creating a system which can generate narrative structure corresponding to satisfying stories.
The structures thus produced don't unambiguously define one linear sequential narrative (because there is no direct temporal sequence given, only the temporal order implied by the node-to-node relationships which are causal in nature.) "The system is ambiguous by design" they say, and later: "the generated graphs could equally describe different stories".
They leave the subsequent "interpretation" or realization of the structure graphs as concrete stories to other systems (to be developed) or to human interpreters.
1: https://arxiv.org/abs/1504.04909