\section{Introduction}



































\end{document}

\section{Introduction}

\begin{figure*}
    \centering
    \includegraphics[width=\textwidth]{figures/figure-1_extra3.png}
       \caption{Narrative structures of existing games (top row) created using TropeTwist and the set of available nodes, and Elites generated with MAP-Elites (bottom row) using as target the respective top.}
       \label{fig:teaserfig}
\end{figure*}

There exists a plethora of games\footnote{For instance, currently there are more than 50k games in steam \url{https://store.steampowered.com/search/?category1=998}.}, with diverse genres and each containing a different set of gameplay mechanics, audio, level, graphic, and narrative facets. The creation and combination of these facets make game development a hard task, commonly involving a diverse group of developers~\cite{Blow2004-gamesHard}. Likewise, the generation of these facets in conjunction has been categorized as one of the biggest and most challenging tasks within computational creativity~\cite{Liapis2014-gameCreativity,Liapis2019-OrchestratingGames}. However, games share common elements and underlying narratives, but it is non-trivial how to identify these, how to define and analyze these games structurally, or what type of common underlying structures exist; pointed out as well by~\cite{aarseth2018-ontologicalMeta,Vozaru2021-gameSituation}.

Among the different facets, narrative stands out in games as it helps to create meaning, make sense of situations, and make games [stories] recognizable~\cite{mateas2003-facade,Aarseth2012-Narrativetheory,kybartas2016survey,flodtol2020-WIPMakeSenseDungs}. Narrative structures can be used to describe how an experience or story is to be developed as argued by Barthes~\cite{Barthes75-introStructNarr}, and to create an abstract representation based on the narrative structure instead of a temporal and partially-ordered sequence of events~\cite{Szilas2003-structuralModelsIDtension}. Common narrative structures used in many domains are Aristotle's drama structure, which subdivides a story into \textit{exposition}, \textit{climax}, and \textit{resolution} or Propp's analysis on the morphology of folktale, which revealed a common narrative structure among them, denoted as Propp's 31 "narremes"~\cite{propp1975-morphology}.

This paper presents \emph{TropeTwist}, a system that uses Tropes~\cite{Thompson2018-usingTropesNarrativeEvents,tropesSimpsons} extracted from TvTropes~\cite{tvtropes,periodicTable} as patterns, and fundamental unit, which when combined can compose structures further representing other composed tropes. Common narrative structures can be identified and defined using \emph{TropeTwist}, defining generic aspects of a story, leading to the identification of events, roles, and narrative elements, and a novel way to create and generate narratives. As a proof-of-concept, we built, analyzed, and described structurally three game examples shown in figure~\ref{fig:teaserfig}, top row.

We propose graph grammars as indirect encoding of narrative graphs and the use of the Multi-dimensional Archive of Phenotypic Elites (MAP-Elites)~\cite{Mouret2015-MAPElites} to generate novel variations (shown in figure~\ref{fig:teaserfig}, bottom row) using the proof-of-concept examples as targets and roots. Simultaneously, we propose metrics to evaluate the coherence, cohesion, and interestingness of the resulting narrative graphs, which we use as comparison between hand-made and generated narrative graphs. Our preliminary results show that by using MAP-Elites, it is possible to vary the structure in such a way that more interesting structures appear while retaining coherence. 








\section{Related Work}





Propp~\cite{propp1975-morphology} analyzed Russian folktales identifying their fundamental structure in 31 steps. His work contributed to the identification of core elements, the proposal of actions and events as \emph{functions} and narrative atoms, and roles that are recurrent within the folktales. Propp emphasized that these 31~\emph{functions} and their arrangement were the structure and what gave meaning to the story discourse. Barthes~\cite{Barthes75-introStructNarr} proposed three intertwined and progressively integrated levels in narrative work: \emph{functions}, \emph{actions}, and \emph{narration}. His work is characterized by the proposal of fundamental narrative units in the~\emph{function} level to better assess and identify structures in a narrative. Furthermore, Baikadi and Cardona-Rivera~\cite{Baikadi2012-Narreme} further discuss these fundamental units as~\emph{narremes} encoding narrative state and how they could be combined to narrative structures. Their work, similar to TropeTwist, proposes a graph structure of interconnected~\emph{narremes}. However, they defined narrative axes like Barthes, where each connection between~\emph{narremes} means a change along a narrative axis. In games, the narrative is usually directed by quests, which Aarseth~\cite{aarseth2005hunt} discusses as a central element in games to make sense of other elements, and which are defined by Yu et al.~\cite{yu2020quest} as a form of structure, dividing the story into achievable rewards and partially ordered set of tasks~\cite{yu2020quest}.







Furthermore, the generation of narratives, stories, and quests using a variety of techniques such as planning algorithms~\cite{Riedl2006-StoryPlanningCreativity,young2013-plansNarrGen,Horswill2020-Generativetext}, grammars~\cite{hartsook2011-storyWorlds,Alvarez2021-questgram}, or machine learning~\cite{tambwekar2019-controllableNeuralStory,vanstegeren2021-gpt2quests}, is a growing and important field within games research and narrative research in general~\cite{Gervas2009-ComputationalStoryCreativity,kybartas2016survey,yu2020quest,Eladhari2014-storymakinggames}. One typical approach for the generation of content and stories is the use of patterns representing different elements such as level design patterns~\cite{Alvarez2020-ICMAPE,flodtol2020-WIPMakeSenseDungs}, quest patterns and common quests in games~\cite{Trenton2010-questpatterns,Doran2011-questsMMORPGs,Breault2021-CONANQuestGen,Alvarez2021-questgram}, or identifying fundamental units and assembling them based on various pre-conditions~\cite{Kreminski2018-SketchingStorylets,Garbe2019-StoryletsAssembler}. A particular type of pattern is tropes, which are concepts that are recurrently used in transmedia storytelling~\cite{tropesSimpsons,tvtropes}. Horswill~\cite{Horswill2016-DearLeaderTrope} focused on constructing an expressive language that could encode plot tropes as story fragments, composing a database of fragments combined sequentially with a planner. Similarly, Thompson et al.~\cite{Thompson2018-usingTropesNarrativeEvents} used the idea of tropes as story bits where a system would construct valid stories from users' defined story bits with pre-and post-conditions.







Moreover, to encode and generate narrative structures, we use graph grammars and grammar recipes. This approach is similar to how Dormans and Bakkes \cite{dormans2011generating} generate missions and space using a "key and lock" structural idea, which was later employed by Juliani et al.~\cite{Juliani2019-obstacleTower} to create levels targeted to reinforcement learning agents. Our approach uses MAP-Elites, a quality-diversity (QD) algorithm that uses behavioral dimensions that are orthogonal to the objective function to store diverse individuals in a grid~\cite{Mouret2015-MAPElites}. Evolutionary algorithms are a popular approach in procedural content generation to generate diverse type of content~\cite{Togelius2011}. MAP-Elites have been used to generate content different game facets such as levels~\cite{charity2020baba,Alvarez2020-ICMAPE}, mechanics~\cite{charity2020mech}, or enemy behavior~\cite{Khalifa2018}.


Assessing narratives is a complex and non-trivial task. The goal is to create a narrative that is both syntactically correct (e.g., coherent and consistent) and semantically rich (e.g., novel and interesting)~\cite{Rowe2009-STORYEVAL,Hargood2011-NarrativeCohesion,Castricato2021-FabulaStoryCoherenceMeasure}. Perez y Perez and Ortiz~\cite{Perez2013-AutomaticModelInterestingness} proposed a model to evaluate interestingness based on novelty and correct story recount, with emphasis on the story's opening, closure, and dramatic tensions. Szilas et al.~\cite{Szilas2016-QualQuantInterestingness} discuss interestingness as a paradox dramatic situation with obstacles and conflicts, albeit applicable to stories as successive events. Yet, to approach subjective measurements such as interestingness, most research turns towards having human evaluation~\cite{Kreminski2019-StorySifter,Lankoski2013-StoryConsistencyInteresting} or using such to form human models to be used as surrogate models~\cite{Sharna2007-PreferenceModelingStories,Li2010-plannerPlotAdapt}. 



\input{tables/table2}
\section{Building narrative structures with tropes}

In storytelling, a trope~\cite{tropesSimpsons} is a convention or figure of speech that the storyteller assumes to be easily recognizable by the audience. TV tropes is an online wiki and repository that compiles, curates, and describes several thousand tropes in many sorts of media~\cite{tvtropes}. As exemplified by \cite{periodicTable}, tropes could be interconnected in graph-like structures, called story molecules, to succinctly depict the structure behind a narrative. 

\subsection{TropeTwist}

TropeTwist elaborates on the concept of story molecule to represent narratives using graph-like structures of interconnected tropes, called narrative graphs (NG). NGs encode narrative structures in an abstract level that show and define the game's narrative structure and certain abstract properties such as key items, roles, relations, or main events. Table \ref{tab:tropes} shows all the included tropes to be used as nodes. Nodes are depicted (fig~\ref{fig:teaserfig}) with shapes specific to their trope type: heroes (rectangle), conflicts (diamond), enemies (hexagon), and plot devices (circle). 

Nodes in a narrative graph are necessarily interconnected by either unidirectional or bidirectional edges (with one or both arrowheads) or by entailment edges (with a single diamond head). Given nodes A and B, A $\diamondsuit$--- B, reads as "A entails B," whereas A $\rightarrow$ B denotes a relationship from A to B, and B $\rightarrow$ A the opposite. A $\leftrightarrow$ B denotes a reflexive relationship between A and B. As an example, HERO $\rightarrow$ CONFLICT $\rightarrow$ EMP denotes a hero who is in conflict against an empire-type enemy, whereas HERO $\leftrightarrow$ CONFLICT denotes a hero who is in conflict with themselves. EMP $\diamondsuit$--- DRA $\diamondsuit$--- NEO, denotes an empire that entails a dragon enemy that, once beaten, will lead to the appearance of a chosen one hero, creating some causal links. The system is ambiguous by design. We take advantage of the ambiguity for 1) the generation of new structures (fewer constraints), 2) removing the focus on details by designers to let them focus on the overarching picture, and 3) for other systems to define these abstract properties. 

Furthermore, interconnecting tropes can arise other tropes and patterns, which we describe in the following section. The nodes and their respective trope and pattern were chosen from a subset of tropes that could be in generic categories such as heroes or plot devices. These categories were inspired and chosen based on tropes from TVTropes, the division by James Harris~\cite{periodicTable}, and previous research such as Propp's morphology~\cite{propp1975-morphology} or Greimas' actantial model~\cite{Greimas84-structuralSemantics}. 

\subsection{Trope Patterns}

Tropes and interconnected tropes (i.e., subgraphs) arise different types of patterns. These patterns can be \textbf{micro-patterns} encapsulating a single trope node, \textbf{meso-patterns}, often composed by more than one micro-pattern with special meaning, and \textbf{auxiliary patterns}. These patterns were identified based on tropes, such as RevP, or as a functional combination of tropes and patterns such as DerP. We calculate the relative tropes and patterns' quality within an NG and use this to assess the general quality of the graph. When generating narrative graphs from a root (explained in section~\ref{sec:evolvingNarratives}), the quality of a narrative graph becomes relative to the root, henceforth, the "root graph" (RG). In the following descriptions, we will use \textbf{TG} referring to the "test graph" we are testing and calculating the pattern's quality, and \textbf{RG} to refer to the relative and root graph.

For most patterns, we calculate and use three general qualities (indicated when used) that add to the quality of the pattern. $G_{q}(pattern)$ relates to the \textit{Generic} quality of patterns in TG, which calculates the general occurrence of a pattern within TG compared to its occurrence in RG, calculated in eq.~\ref{eq:generic_qual}. $R_{q}(pattern)$ relates to the \textit{Repetition} quality of patterns, which calculates if a trope is unique in TG ($R_{q}(pattern) = 1$) or its ratio among the same pattern. Lastly, $I_{q}(pattern)$ relates to the \textit{Involvement} quality of patterns in TG, which calculates the amount of associations a pattern has with \textbf{structure patterns}. Involvement means that the pattern is either \textit{source} or \textit{target} in a structure and is calculated as the ratio of structure pattern involvement by the structure pattern count in TG.

\begin{equation}
\label{eq:generic_qual}
    G_{q}(pattern) = |RG_{pat} - TG_{pat}|/\max(RG_{pat}, RG_{pat})
\end{equation}






\subsubsection{Micro-Patterns}

Micro-patterns are the fundamental unit in the system, which aims at categorizing different sets of the individual patterns that are shown in table~\ref{tab:tropes}. Micro-patterns are the basic building block that, when interconnected, allows the detection of meso-patterns.

\emph{Structure Pattern (SP)} is any type of trope that would give some structural definition to a narrative, whether this being a conflict, specific act, or a part in a dramatic arc (e.g., climax). Currently, the only type of structure trope is the \textsc{conflict} (C) trope, which represents the most basic structural interaction. The quality $SP_{q}$ is calculated as the normalized linear combination of:

\begin{equation}
    SP_{q} = G_{q}(SP) + I_{q}(SP)
\end{equation}

\emph{Character Pattern (CP):} are identified as nodes within the narrative that could be either the player, possible ally or enemy NPCs, or simple enemies. In TropeTwist, it is distinguished between heroes and villain patterns, and these are commonly used as \textbf{sources} or \textbf{targets} (or both) of other patterns, and on a few special occasions to denote a relation to another character. The quality $CP_{q}$ is calculated per group (heroes and villains), and it is the normalized linear combination of:

\begin{equation}
    CP_{q} = G_{q}(CP) + R_{q}(CP) + I_{q}(CP)
\end{equation}

\emph{Plot Device Pattern (PDP):} is described as the element within the narrative that moves it forward, in the shape of a goal, object, or dramatic element to be used or encountered by any of the characters. The quality $PDP_{q}$ is calculated as the normalized linear combination of:

\begin{equation}
    PDP_{q} = G_{q}(PD) + R_{q}(PDP)
\end{equation}


\subsubsection{Meso-Patterns}

Meso-patterns~\cite{dahlskog2014-multimultilevel} are the features that emerge in the narrative from dynamically combining micro-patterns and, on some occasions, these with other meso-patterns. They are always composed of more than one pattern denoting some spatial, semantic, or usability relationship within the narrative graph. We identified a subset of Tropes (extracted from TVTropes~\cite{tvtropes}) that requires or works as the combination between more fundamental units. For instance, the \textit{reveal pattern} relates to the "Good all along" or "evil all along."

\emph{Conflict Pattern (ConfP)} is a type of structure pattern composed by a conflict node (Con), a source $s$ node, and a target $t$ node, which are both CPs and usually a hero and a villain or the same character as $s$ and $t$. For instance, the subgraph HERO $\rightarrow$ CONFLICT $\rightarrow$ EMP, indicates that a hero CP has a conflict with an enemy CP. A conflict node can be used indefinitely to define several ConfP. A ConfP is also either~\textsc{explicit} or~\textsc{implicit}. \textsc{Explicit} conflicts are explicitly encoded in the graph and directed from $s$ to $t$ passing through the conflict trope. On the other hand, \textsc{Implicit} conflicts relates to the conflicts from $t$ (or derivatives) to $s$ (or derivatives) that are not encoded in the graph. For instance, the previous example is an \textsc{explicit} conflict from HERO to EMP, and at the same, the EMP has an \textsc{implicit} conflict with the HERO. The quality $ConfP_{q}$ is calculated as the normalized linear combination of:

\begin{equation}
    ConfP_{q} = G_{q}(ConfP) + R_{q}(ConfP) + I_{q}(ConfP)
\end{equation}

\emph{Derivative Pattern (DerP)} defines a relationship between tropes connected by "entails" connections ($\diamondsuit$---). Therefore, a DerP contains a list of patterns connected by entails, named derivatives. DerP starts from a root micro-pattern and continue until no more "entail" connections are encountered, effectively establishing a hierarchy from the root derivative to the rest. By design, the patterns within a DerP have a local and temporal order and a causal relationship. For instance, in the subgraph EMP $\diamondsuit$--- DRA $\diamondsuit$--- NEO, engaging with the \emph{EMP}, entails both the conflict with \emph{DRA} and the appearance of \emph{NEO}. This means that only by overcoming the \emph{DRA}, \emph{NEO} will appear - as a new hero or the evolution of another. The quality $DerP_{q}$ is calculated (eq.~\ref{eq:derp}) based on its $G_{q}(DerP)$, the ratio and balance of derivatives within the pattern to the total amount of derivatives among all DerPs in TG ($bal\theta_{q}$), and the derivatives' diversity.

\begin{equation}
\label{eq:derp}
    DerP_{q} = G_{q}(DerP) + 
    bal\theta_{q} + 
    \frac{\sum_{i=0}^{|DerP_{der}|}i_{base}}{|DerP_{der}|}
\end{equation}

\emph{Reveal Pattern (RevP)} connects two independent CPs as one, meaning that character A was, in fact, always character B, and vice-versa. This pattern identifies confusion and surprise within an TG, as, for instance, a villain could have been, in fact, "Good All Along"\footnote{https://tvtropes.org/pmwiki/pmwiki.php/Main/GoodAllAlong}. In practice, a RevP is identified as a villain or hero connected with a unidirectional connection ($\rightarrow$) to another hero or villain. As a consequence, all existing conflicts between them would become \emph{fake}. $RevP_{q}$ is calculated based on its $G_{q}(RevP)$, the number of reveals in TG in relation to characters, and the number of fake conflicts given the specific reveal.

\begin{multline}
    RevP_{q} = G_{q}(RevP) + \frac{|ng_{RevP}|}{|ng_{CP}|} +  \\ \Bigg( 1.0 - \frac{\sum_{i=0}^{|ng_{conf}|}    \begin{cases}
        1,& \text{if } RevP \in x_{i}\\
        0,              & \text{otherwise}
    \end{cases}}{|ng_{conf}|} \Biggl)
\end{multline}

\emph{Active Plot Device Pattern (APD)} operationalize and integrate PDPs within a narrative since PDPs only describe an abstract goal or target. In practice, an \textit{APD} is identified as PDPs that have at least one incoming connection, and optionally, one single outgoing connection. These limitations are added to limit the effect of a PDP within a narrative. $APD_{q}$ is measured based on its $G_{q}(APD)$, and the APD's usability, calculated based on the sum of incoming and outgoing connections divided by half of the nodes in TG depicted as $bal\gamma_{q}$. Usability is calculated like this to penalize APDs that do not use as many connections as possible but neither be the only APD in place.

\begin{equation}
    APD_{q} = G_{q}(APD) + bal\gamma_{q}
\end{equation}

\emph{Plot Points (PP)} are key events within the TG, identified as discrete moments given some pattern. The derivatives within a \textit{DerP}, RevP's source, and PDPs that are \textit{APD} are considered as plot points. $PP_{q}$ is measured based on the number of PPs within RG ($ G_{q}(PP)$), and the number of PPs within TG in relation to the number nodes within it ($Balance_{q}(PP)$).

\begin{equation}
    PP_{q} = G_{q}(PP) + Balance_{q}(PP)
\end{equation}

\emph{Plot Twist (PT)} takes advantage of plot points to identify those that could have a bigger impact on the narrative. In practice, \emph{PTs} consider the source of \textit{RevP}, derivatives from \textit{DerP} that are a different micro-pattern than the root of the DerP, and \textit{APDs} that are connected to other \textit{APDs}. For instance, in the subgraph: EMP $\diamondsuit$--- DRA $\diamondsuit$--- NEO, given that NEO is a different micro-pattern than root EMP (Hero and Villain, respectively), NEO will be identified as a \textit{Plot Twist} as it alters the "natural" order in the DerP. $PT_{q}$ is based on the number of PTs within RG ($ G_{q}(PT)$), the PT's involvement in TG, and the balance of PTs based on the PPs in TG. When a PT is associated with a \textit{RevP}, involvement is calculated as how much the structure changes based on that (i.e., how many fake conflicts are created). When it is related to \textit{DerP}, involvement is calculated as how different the pattern is and its order within the derivatives. Finally, when it is related to \textit{APD}, involvement is based on how usable the \textit{APD} is within the narrative based on incoming and outgoing connections.

\begin{equation}
    PT_{q} = G_{q}(PT) + I_{q}(PT, assoc_{pat}) + \frac{|ng_{pt}|}{|ng_{pp}|}
\end{equation}

\subsubsection{Auxiliary Patterns}

Auxiliary patterns denote problems in the graph and sub-optimal or impractical nodes and connections within a graph. They are classified into \textit{Nothing}, which are nodes that are not identified or part of a meso-pattern; and \textit{Broken Link}, which are outgoing connections from a node that are not used or do not lead to any pattern.

\subsection{Proof-of-Concept}
\label{sec:PoC}

TropeTwist can be used to represent different narrative structures and parts of games. To test and show TropeTwist's expressiveness, we chose to form three different narrative graphs representing different games shown in figure~\ref{fig:teaserfig}, top row: \emph{Zelda: Ocarina of Time} (Zelda:OoT)~\cite{tloz:oot}, \emph{Zelda: A Link to the Past} (Zelda:LttP)~\cite{tloz:lttp} - eastern palace, and \emph{Super Mario Bros} (SMB)~\cite{mario}. They represent different games from different genres (fig.~\ref{fig:teaserfig}.a and \ref{fig:teaserfig}.b are adventure-dungeon games, and \ref{fig:teaserfig}.c is a platform), and represent different game's phases; in the case of fig.~\ref{fig:teaserfig}.a and \ref{fig:teaserfig}.c, both represent the main structure of the game, while \ref{fig:teaserfig}.b, represents a specific area and sequence of the game.

Figure~\ref{fig:teaserfig}.a represents a simplified overarching narrative structure from Zelda: OoT. The tri-force, which is the main item to collect in the game, is defined as a McGuffin (MCG) that, when collected by "young link," allows him to go forward in time to "adult link," the chosen one (NEO). This, in turn, enables explicit conflicts between hero and enemy characters, which represents the main loop of the game. The structure shows two factions, a set of heroes and the BAD opposing them. Pattern-wise, $HERO \rightarrow SH$ represents an \textbf{RevP}, which in turn, represents an \textbf{PT}; $HERO \leftarrow MCG \leftarrow NEO$ represents an \textbf{APD}, and the rest of elements are interconnected by \textbf{ConfP}.

Figure~\ref{fig:teaserfig}.b represents the structure and plot points from the eastern palace in Zelda: LttP. All palaces in \textit{A Link to the Past} follow a very similar structure and sequence. 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. The structure shows a causal and linear narrative that could be used to identify elements that need to appear before others, similar to the work by Dormans and Bakkes~\cite{dormans2011generating}. Pattern-wise, ENEMY $\diamondsuit$-- MHQ $\diamondsuit$-- BAD $\diamondsuit$-- MCG represent an \textbf{DerP}, and ENEMY $\diamondsuit$--- MHQ $\diamondsuit$-- BAD, BAD $\diamondsuit$-- MCG $\rightarrow$ HERO, and HERO $\diamondsuit$-- MHQ $\rightarrow$ HERO represent \textbf{APDs}.

Figure~\ref{fig:teaserfig}.c represents the overarching narrative structure of SMB. In SMB, the objective of Mario (HERO) is to rescue Peach (HERO) from Bowser (BAD). To do this, the player goes through a series of platform worlds that always end in a "Fake Bowser" (DRAKE). The player must continue until encountering the "Real Bowser" (BAD), which then would enable the player to get to their objective (MCG). Pattern-wise, the game represents a simple narrative structure, where EMP $\diamondsuit$-- DRAKE $\diamondsuit$-- BAD $\diamondsuit$-- MCG, denotes an \textbf{DerP} as a linear increase in difficulty, and HERO $\rightarrow$ MCG $\rightarrow$ HERO denotes an \textbf{APD}.
\section{Evolving Narratives with Graph Grammars} \label{sec:evolvingNarratives}

We use the Constrained MAP-Elites~\cite{Khalifa2018}, and adapt it to work with graph grammars, evolve production rules, and adapt the evolution towards a specific target similar to~\cite{Alvarez2020-ICMAPE}. An individual's phenotype is a narrative graph, and its encoding genotype is the production rules of a graph grammar. A graph grammar is a context-free grammar whose productions add, remove, and modify nodes and edges of a graph. Our implementation uses the tropes listed in Table \ref{tab:tropes} as nodes, and the three available connection types as edges ($\rightarrow$, $\leftrightarrow$, $\diamondsuit$--). Graph grammars do not apply rules sequentially; instead, every individual does a random sampling of the rules in their genotype to produce \emph{recipes} to generate a narrative graph. \emph{Recipes} describe the rules' order and repetition. \emph{Recipes} do not have repetitions within them, i.e., if rule 1 is added at step 2, subsequent addition would simply add to the number of times that rule will be applied at step 2. Figure~\ref{fig:gen2phen} shows a sample complete process from an individual's genotype (i.e., rules) to the phenotype (i.e., narrative graph).

The EA manages an infeasible and feasible population within each cell~\cite{Kimbrough2008}. Individuals move between the feasible and infeasible population depending on the feasibility constraint. NGs are deemed infeasible if the nodes are not fully connected or if there exists a conflict pattern with more than one self-conflict. Infeasible individuals are evaluated based on how close they are to be fully connected and not having any inadequate self-conflict. NGs that are deemed feasible are evaluated on their coherence (equation~\ref{eq:coherence_fitness}), which we use to assess how correct, coherent, and in general, syntactically correct the narrative graphs are. Coherence aims at maximizing an equally weighted sum between cohesion and consistency. Cohesion refers to the link between elements that hold together to form some group, and in our implementation, focuses on minimizing the number of auxiliary patterns (\textit{Nothing} and \textit{Broken Link}). A consistent NG should be regular and free of contradictions. Thus, we calculate $f(consistency)$  (eq.~\ref{eq:consistency_fitness}) as the collective quality of micro-patterns since they are the building blocks, and conflicts' goodness based on the number of fake conflicts. In effect, with consistency, we aim to maximize the quality of micro-patterns and minimize contradictions created by meso-patterns.

\begin{equation}
\label{eq:consistency_fitness}
f(consistency) = w_{0} \times \frac{\sum_{i=0}^{|ng_{micro}|} i_{qual}}{|ng_{micropat}|} +  \\ 
w_{1} \times \frac{|ng_{fakeConfP}|}{|ng_{confP}|} 
\end{equation}

\begin{equation}
\label{eq:coherence_fitness}
f(coherence) = w_{0} * f(consistency) + w_{1} * (1.0 - f(cohesion))
\end{equation}

Furthermore, a feature of MAP-Elites is that it uses behavioral dimensions in a grid shape to retain and foster diversity throughout generations. We use the following two dimensions to evaluate the diversity: 

\textbf{Step.} Step (eq.~\ref{eq:StepDim}) calculates the Levenshtein distance~\cite{Levenshtein96-editDistance} between two narrative graphs, taking into consideration the number and type of nodes and connections. Step is normalized using step threshold $\theta = 11$ determined through a process of experimentation, which does not consider steps farther than $\theta$, avoiding the generation of too dissimilar graphs.

\begin{equation}
\label{eq:StepDim}
D_{step} =  \min (lev_{TG,RG} (|TG|, |RG|), \theta)
\end{equation}

\textbf{Interestingness (int).} We aim at measuring the semantic quality of a narrative graph. A narrative graph can be syntactically correct and coherent yet do not have a good (or existent) semantic quality and do not evoke interest for designers or players. Therefore, we leverage \textbf{plot point}, \textbf{plot twist}, and \textbf{active plot device} patterns to measure the \emph{interestingness} of the NGs. The nature of \emph{interestingness} creates pressure on the fitness function since the incidence of the three meso-patterns could (if overused) "degenerate" the narrative; thus, decreasing its coherence. $D_{int}$ is calculated as the weighted sum ($w_{0}=0.4, w_{1}=0.2, w_{2}=0.4$) of the normalized cumulative quality of \textbf{APDs}, \textbf{PPs}, and \textbf{PTs} within an NG (eq.~\ref{eq:interesting_fitness}).

\begin{equation}
\label{eq:interesting_fitness}
D_{int} = w_{0} \times \frac{APD_{q}}{\#APD} + w_{1} \times \frac{\#PP_{q}}{\#PP} +  w_{2} \times \frac{PT_{q}}{\#PT}
\end{equation}

\subsection{Experiments}




\begin{table*}[t]
\caption{Comparative results between target graphs and generated elites.}
\label{tab:best-generated}
\setlength{\tabcolsep}{4pt}
\resizebox{\textwidth}{!}{%
\begin{tabular}{|l|cc|cc|cc|}
\hline
 &
  \multicolumn{1}{l}{RG (fig \ref{fig:teaserfig}.a1)} &
  \multicolumn{1}{l|}{Elite (fig \ref{fig:teaserfig}.a2)} &
  \multicolumn{1}{l}{RG (fig \ref{fig:teaserfig}.b1)} &
  \multicolumn{1}{l|}{Elite (fig \ref{fig:teaserfig}.b2)} &
  \multicolumn{1}{l}{RG (fig \ref{fig:teaserfig}.c1)} &
  \multicolumn{1}{l|}{Elite (fig \ref{fig:teaserfig}.c2)} \\ \hline
Cohesion        & 1.0  & 1.0  & 1.0  & 1.0  & 1.0  & 1.0  \\
Consistency     & 0.43 & 0.53 & 0.52 & 0.63 & 0.53 & 0.59 \\
Coherence       & 0.71 & 0.76 & 0.76 & 0.82 & 0.76 & 0.79 \\
Interestingness & 0.61 & 0.73 & 0.38 & 0.53 & 0.4  & 0.52 \\ \hline
\end{tabular}%
}
\end{table*}

We conducted a series of experiments to evaluate and analyze how the system could evolve NGs into quality-diverse and valid narrative structures. We evolved the three manually constructed narrative graphs shown in figure~\ref{fig:teaserfig}, top row. They were used as target graphs and axioms in the EA, and we used \textit{interestingness} and \textit{step} as behavioral dimensions. We did $5$ MAP-Elites runs per narrative graph, ran each for $500$ generations, and set the initial population to $1000$ randomly created individuals. Each individual is limited to test $10$ recipes regardless of the chromosome size. Offspring were produced either by selecting either the left-side or right-side of a random production rule and exchanging them or with a $50$\% mutation chance. If an offspring was generated by mutation, there was a $10$\% chance to add or remove a production rule and a $90$\% to modify in various ways existing production rules.

We calculated the \textit{coverage}: how much of the constrained search space is explored (i.e., constrained by the behavioral dimensions); the avg. fitness and the avg. interestingness of the population. All runs, regardless of the TG, performed similarly with an avg. of 21\% coverage, 0.68 avg. fitness, and 0.38 avg. interestingness. These results exemplify both the hard task of generating narrative graphs and exploring the possibility space, and the seemingly competing qualities of coherence (i.e., fitness) and interestingness. 

Furthermore, in figure~\ref{fig:teaserfig}, bottom row, it is shown three different example elite narrative graphs, generated from their respective target graph on the top row and with each individual evaluation shown in table~\ref{tab:best-generated}. The target graphs have a cohesion of 1.0 since none of them have unused nodes or connections and have similar mid consistency values because of using generic nodes (e.g., HERO or ENEMY), repeating them, and low involvement in structures by characters. In the case of fig \ref{fig:teaserfig}.a1, the \textbf{RevP} from HERO to SH creates some fake conflicts, which affect the consistency but also boost the interestingness value of the narrative graph. Both fig \ref{fig:teaserfig}.b1 and \ref{fig:teaserfig}.c1, are evaluated similarly with low interestingness; c1 involves a simplistic and linear structure, and b1, while in principle more complex, is also a relatively linear structure with no \textbf{PTs}.

Furthermore, all the generated elites have better \textit{consistency}, \textit{coherence}, and \textit{interestingness} than the respective target graph. In figure~\ref{fig:teaserfig}.a2, the graph has been reduced towards a bottleneck, \textbf{RevP} (HERO $\rightarrow$ SH) is removed, and MCG is added as the objective for SH, which could point towards competition or cooperation to enable NEO. Such a change gives more \textit{consistency} to the graph while seemingly reducing its \textit{interestingness}, but this relation and the $\diamondsuit$-- connection between MCG and NEO increase its \textit{interestingness}. In figure~\ref{fig:teaserfig}.b2, the narrative has more interaction between \textbf{Plot Devices}, and the BAD has a more active role. Particularly, the fact that now HERO $\rightarrow$ MCG $\diamondsuit$-- BAD and MHQ $\diamondsuit$-- CHK $\diamondsuit$-- BAD could enable and force the HERO towards two main objectives before overcoming the boss, which is reflected in the higher \textit{Interestingness}. Finally, in figure~\ref{fig:teaserfig}.c2, the narrative did not change much (only four steps away), yet the graph is seemingly better, and the narrative could be very different. The graph has broken the loop which connected DRAKE $\diamondsuit$-- BAD, and could could point towards a side objective. Further, the connection between BAD and MCG has been reversed; thus, the HERO does not need to face the BAD to get the MCG, rather reaching the MCG will have as a consequence the emergence of the BAD. Finally, BAD is no longer connected to EMP and DRAKE; thus, BAD could be its own enemy faction, in this case, complexifying the narrative and possibly creating more challenge.
\section{Conclusions and Future Work}


In this paper, we have presented \emph{TropeTwist}, a system that interconnects tropes and trope patterns to describe narrative structures. We demonstrated through three proof-of-concept structures the system's expressiveness to describe games with diverse genres and mechanics, and different game phases. Further, we illustrated how we could generate quality-diverse structures from the three proof-of-concept structures using MAP-Elites, improving them on our metrics. 

Tropes could be seem as something to avoid when exploring creativity, mainly due to the possibility of showing unoriginal views by definition. However, a set of combined tropes, patterns, and structures could arise novel combinations that express the wanted structure. Similarly, identifying, visualizing, and defining the tropes and patterns and doing "twists" with them; thus, transforming something typical into atypical is the goal with TropeTwist.

The narrative structures show essential aspects of how the story will develop and lead, and important components such as events, conflicts, or roles. However, to further operationalize these structures, it is necessary other systems that make use of them, such as quest~\cite{Alvarez2021-questgram,ammanabrolu2019-towardQuestGeneration} or plot~\cite{Ammanabrolu2020-PlotEventsSentences} generators. Another interesting future work would be to explore the multi-faceted nature of games~\cite{Liapis2019-OrchestratingGames} and combine this type of system with generators that focus on other facets such as level design~\cite{sarkar2021-dungeonPlatformer,alvarez2019empowering} or game mechanics~\cite{green2021-gamemechanicsAlignment,charity2020mech}.

Generating novel narrative structures resulted in interesting variations, but the system could not exploit all the advantages of MAP-Elites. Our results point towards difficulties exploring the space, possibly because \textit{coherence} and \textit{interestingness} are to some extent competing objectives. Therefore, we aim at extending TropeTwist towards a mixed-initiative co-creative system~\cite{yannakakis2014micc}, and with that, evaluate with human participants. Then, we could constantly adapt the content generation and have adaptive models, for instance, of interestingness, based on the user's creation similar to~\cite{alvarez2019empowering,Panagiotis2021-susketch}. 























