Keywords

1 Introduction

Procedural Content Generation (PCG) is an umbrella term containing both level generation and narrative generation techniques; yet the union between these two has been rarely explored. In this paper, we explore the union between these two PCG areas, and how the union enables indexical storytelling—a sibling to environmental storytelling.

PCG often—in academics—describes processes that help designers save time and have more resources for development. Cook [1], however, proposes another way to describe PCG, stating: “A better justification for PCG is that it enables new kinds of game design, by changing the player’s relationship with the game’s systems, or allowing the developers to work at a scale that would be otherwise impractical.” Cook furthers this view by demonstrating how PCG gives players a different experience due to the PCG-oriented gameplay design [2]. Games such as Caves of Qud [3], Dwarf Fortress [4], or Ultima Ratio Regum [5] are exemplars of how PCG allows for a scale of gameplay that would not be achievable otherwise.

This type of PCG viewpoint described by Cook also captures emergent narrative as described by Ryan [6], where world’s simulation creates a narrative, but only in the retelling of the events does it become a story; Ryan calls his approach a curatorial approach to simulated story worlds. Ryan continues by saying that this curation can be done procedurally as well, which has led to systems focused on sifting through the simulated worlds, looking for emergent narrative, such as Winnow [7] and Felt [8]. These systems often focus on characters and character actions, but there is an additional layer of believability that pertains to space, as these characters must exist within a virtual environment, and how characters act within that space reveals more information about them that can help convince the player that these characters are believable. Take for example a man dressed in armor standing in front of a medieval gate with others dressed similarly, all at attention.

While there was no mention of a “city guard,” it is not too difficult to make the leap that the character described is a city guard, protecting the gate with their fellow guardsFootnote 1. While much of the example has the character doing an action, it’s only within the context of the world around them does the belief of, “this character is a guard,” get further grounded. Yet, this isn’t the only function that space has as it can help tell the player what type of experience the virtual world holds for them; an eerie abandoned town has a much different character than a vibrant thriving city. The story world can help to improve the audience’s believability of character action by the way the world is presented to the player. This presentation of the story world and how the player experiences, is to us, environmental storytelling; where the story world conveys information about the story through the world. This, we believe, is at the core of environmental storytelling, which Carson states in his piece on environmental storytelling [9]: “One of the trade secrets behind the design of entertaining themed environments is that the story element is infused into the physical space a guest walks or rides through.”

While Carson at the time was describing theme parks, suffusing places with the story element for visitors to traverse, his description of environmental storytelling has been seen within games. Game worlds often attempt to enrich the story through its design, like in Bioshock Infinite’s city design of Columbia—the location that the majority of the game’s story takes place in. Totten [10]—in his book, Architect’s Approach To Level Design—describes portions of Columbia as: “buildings and islands form large-scale rhythms that draw players from one climactic battle to another. However, players who explore individual structures will find richly developed reward spaces and embedded narrative spaces.” Levels—and the world for that matter—offer a chance to convey a narrative through their construction, props, and visuals, much like Carson’s environmental storytelling; but adhering to Carson’s approach might be a pitfall for a game developer as it does not capture the entire experience; it fails to capture how players interact with space. Instead, Fernández-Vara [11] argues that games should adopt an indexical style to environmental story telling.

Indexical storytelling allows players to discover a narrative by ordering what they find in the game world, like exploring the streets of Columbia, or collecting pieces of information for a murder mystery. Here the player can construct their own narrative, one which isn’t reliant on visiting a place first. Instead, they may pursue the goal in whichever manner they deem fit. We believe that the combination of different PCG systems and areas, such as narrative and level generators, can make indexical storytelling possible.

In this paper, we contribute an exploration of the combination of narrative and level generators. First, we describe both PCG algorithms that focus on generating levels, then we describe narrative generation techniques. We then describe the benefits of combining both narrative generation and level generation algorithms together, which come from a system that we are currently developing but have yet to test. We also give possible ways to evaluate this approach.

2 Related Work

Kybartas [12] conducted a survey on narrative generation techniques that touches on story world generation, but the description given differs from the world generation we discuss in this paper when discussing level-oriented PCG. Instead, Kybartas describes space as the world in which the narrative happens, whereas level and world generators prioritize creating game worlds care more for game mechanics than story constraints. Games such as Spelunky [13] or Dead Cells [14] exemplify this viewpoint by generating levels solely for gameplay. Yet, an example of space being used for story telling would be more akin to how drama managers often use space. Façade [15], a short interactive drama, has its characters (Trip and Grace) interact objects within their apartment, using these objects as conversation with the player.

As for level generators, their focus is often on generating intractable game worlds that are conducive to gameplay. Often level generators are search-based approaches, grammars, rules, and others, which have all been well-documented in Procedural Content Generation in Games [16]. Other techniques that have become well known are constraint solvers like WaveFunctionCollapse (WFC) [17], which allows for constraint satisfaction and statistical learning to generate levels. In this approach, we use WFC as it shares a knowledge representation abstraction that is cohesive to how narrative generators represent story beats and WFC has been used to generate non-gameplay constraints such as genre [18] or aesthetics [19]. We still list out other algorithms as they are still valid candidates for combining with narrative generators.

As for narrative generators, these include planners—such as Sabre [20] and Glaive [21], which causal planning to ensure narrative coherency—storylet systems such as Lume [22], and story sifters like Winnow [7] and Felt [8]. There are many other approaches, as described in Kybartas’s survey, but for our use case we have found these three are a solid foundation for our integrated framework. While there has been much work on narrative planners, their usual graph-based knowledge representation seemed the most appealing for our approach. Storylet systems, on the other hand, treat narrative beats as composable units to generate coherent narratives. They often require story history to use as a world fact to then input as preconditions to each narrative beat; they will then choose an appropriate narrative beat that fills the story requirements. These systems require a critical mass of generative material before the systems generate believable narratives [22]. Story sifters, such as Winnow and Felt, look for interesting narrative locations while the world is being created. The output of these systems could then be connected to other approaches/systems for narrative generation.

Interesting, the closest system that treats indexical storytelling generation comes from Dormans’s work, which looks at space and tries to generate it with a cohesive “feel” such as generating a temple within the game [23]. Other related work that attempts to tackle indexing the world comes from the Liquid Narrative Lab has research on indexing the world for better understanding of narrative constraints [24] that is similar to the indexical storytelling that is discussed in this paper. The closest related work we have been able to find is Bidarra’s work on generating narrative worlds that use a story as it’s starting position [25]. We differentiate ourselves by using the world generation as input for the story—as in not constraining our generative process with an already generated story. We instead approach this more with a curatorial view of emergent narrative.

3 Emergent Story World Generation

“Another example of "cause and effect” is the use of what I call “Following Saknussemm.” Derived from the story Journey to the Center of the Earth by Jules Verne. In Verne’s story the main characters follow a trail of symbols scratched into subterranean walls by their adventuring predecessor, a sixteenth century Icelandic scientist, Arne Saknussemm. In this way, the game player is pulled through the story by following “bread crumbs” left behind by a fictitious proceeding game character. Whether you create notes scattered throughout your environments, or have the game player follow the destructive path of some dangerous creature, “cause and effect” elements will only heighten the drama of the story you are trying to tell!” – Carson [9]

The above quote is effectively what we wish to achieve with this approach; a world in which the characters can modify the world—and thus the story world as wellFootnote 2. Often, however, the issue with this embedding of “bread crumbs” is that a designer placed them in the world—there was not a character who performed the act procedurally. This designed story often means the audience will only have one way to discover story, which Fernández-Vara would argue as environmental storytelling and not indexical storytelling. Fernández-Vara states that game spaces should not have this singular way through them, but allow the player to piece together information, indexing the world as they wish. By indexing the space, the player creates a narrative that is unique to their play trace, giving the player a more memorable experience that can then be recounted to others. Fernández-Vara’s version of storytelling is our goal, to create indexed environmental stories for players to create their own stories by interacting with the environment.

In terms of achieving indexical storytelling, we suggest that there needs a common knowledge representation that both the narrative system and world/level generator share. As in, with a graph-based approach, such as a narrative planner and WaveFunctionCollapse (which can be considered a constraint graph solver); these two systems have the same type of knowledge representation of graphsFootnote 3. The issue then is connecting the two systems through this shared representation.

Currently, our approach focuses on the knowledge representation that both narrative generation and level generation share. We do so by using a graph-based representation between level generation (through WFC) and a narrative planner. For our narrative planner, we use space generation as a pre-condition for narrative nodes. As for a location beat to occur, the location must exist for that beat to occur, and it must occur in that location. As in if the narrative system’s beat generation requires a temple (akin to one as described in Dormans’s Theory of The Place [23]) then there must be a temple that is generated within the world. As for this type of generation, currently we are generating all locations as we test the connection between narrative planner and level generator.

We are experimenting with the inverse, as in if the level/world generator generates a larger structure (like a temple) that the narrative planner may not know about—as in the level generator understands this higher order patternFootnote 4 (like a port, or a highway, or some landmark) that the narrative planner does not contain—then then this information should be passed into the narrative generator, allowing the planner to take this new landmark and possibly generate stories for that location.

Another solution would be to give both the narrative and level generation an intermediate representation (IR), much like how compilers create and IR structure from source code. By having an intermediate symbol set, any system can target this approach, assuming the other system has implemented a similar symbol set representation. This approach is similar to how EM-Glue [26] connects system together, but we are describing is more akin to a Language Server Protocol approachFootnote 5.

If the IR approach was taken, then other systems could be introduced to the generative process such as including character AI systems to flavor the generative process by using character traits to help decorate NPC interiorsFootnote 6. Examples of character AI systems are Fatima Modular [27] or PsychSim [28], which could drive both the character’s decision making, but also inform the generation systems through the symbol set that a character would like to move from their home to another, which could then be generated for the characters. This generation step could even be constrained by social rules through a system like Comme Il Faut [29]. By including this step, our system explores questions such as how does one map personality to place, or social implications into levels. While we think this approach would be more extendable, we are placing this IR approach as future work as we do not know what the IR structure would look like until we build one possible system and evaluate it.

As for evaluations, we are still determining the best approach, as our approach is still being iterated on. Since this approach combines both narrative and level generation techniques, currently we are considering using both level generation evaluations, such as those proposed by Smith [30]. We also believe this system should be evaluated according to the believable character dimension, mostly due to our simulation/curatorial approach. Currently we are deciding between Jhala’s description of believable character metrics [31] and those described by Aljammaz [32].

Currently we are leaning towards Jhala’s as there is more one-to-one correspondence between Totten’s level design book. Still though, there is another dimension of evaluation akin to an expressive range analysis of narrative worlds, much like the work of Kybartas [33]. Yet, unlike Kybartas’s analysis where conflict of character states is the evaluation metric, the world’s total narrative conflict potential could be used as a metric. As for which evaluation would be the best, we are still deciding as we continue to work on our approach, however, we are almost certain that a suite of metrics will be needed.

Thus, the goal of this integrated system is to bridge the gap between narrative and world generation and create an appropriate evaluation for the system. We also aim to create some more generalized language for this system so other AI systems can be included in the generation process. Currently, we are still understanding and exploring this space through our approach. By combining these two areas of content generation, we hope to create more believable worlds on the scale that PCG can provide, while maintaining narrative coherency given the player’s actions.

4 Conclusion

In this paper, we describe the differences between level generation and narrative generation and the gap between these two research areas. Next, we describe environmental storytelling, then indexical storytelling, and how our system aims to approach a procedural indexing system. We then describe a framework for using WFC and a narrative planner to create an integrated system. We then describe a series of evaluations that could be used to determine if the system’s output is credible. This connection between narrative and level generators, we believe, will expose new potential spaces and scale of play and story that can only be possible through PCG.