Procedural content generation (PCG) has seen relative widespread adoption in games and game development. While PCG methods are gaining traction in commercial games, there are comparatively fewer cases where PCG has been used to generate the game world, characters, and the narrative for a single game. We present our research, collaborating with a small independent game studio, on the design of a game engine designed to generate a world, characters, supporting quests and overarching narrative content for their upcoming game. We discuss our choice of game artificial intelligence algorithms, decisions made in designing our system, and our progress and implementation under the constraints and requirements given to us. We posit our system will generate a rich game world with an explainable world history for players to explore and quests to complete. We believe that our engine will meet their requirements increasing the replayability of the game, reducing the authorship burden, while providing the authors with significant c ontrol over q uest a nd narrative structure.
As commercial video games grow more complex and
business models such as free-to-play (F2P) become more
common, there is a need for tools and methodologies that can
help generate the growing amount of content the games
require (Hendrikx et al. 2013). A class of AI algorithms
termed as Procedural content generation (PCG) algorithms
is one solution to this problem. PCG algorithms can generate
game content such as levels, terrain, and other objects during
game development or run-time. PCG has aided a wide
variety of use-cases, from generating individual quests for the
player, to generating non-player characters (NPCs) with
motives and emotions, or generating the terrain of entire game
worlds (Hendrikx et al. 2013; Smith et al. 2011). They can
reduce the authoring burden on game designers, increase
the replayability (Smith et al. 2011) of games by
continually generating new content during runtime, or even produce
unexpected content that human designers may not have
conceived of
Within the games industry, these benefits o f P CG have
been realized especially for world generation, with
examples including games such as Minecraft, the Diablo series,
and Dwarf Fortress, all of which employ PCG to create
their terrain and dungeons
We collaborated with Blast Bit Enterprises, a small, independent game development studio, to design a mobile game. Their game needed to have high replayability. They required a “game and story engine,” a system capable of procedurally generating both the world, quests and narratives that guide the player’s gameplay experience. Such a system could also afford players more agency than a manually-authored story by allowing the player to shape the narrative through their actions. As this story engine would define the player’s gameplay experience, its design constitutes a crucial part of Blast Bit’s game.
We describe our approach toward solving this problem by proposing a system design for Blast Bit’s game and narrative engine and providing an implementation of part of the proposed system. We discuss our software design process and selection of procedural content generation algorithms and procedures working around the constraints given to us by the studio resulting in the development of their PCG Engine.
In this section, we overview the prior use of context-free grammars (CFGs), logic programming and story systems in research and describe how they connect to our system design.
Context-Free Grammars (CFGs)
In the domain of level generation,
Logic programming is another promising approach,
defining the world or its objects as predicates and
implications
Narrative systems such as Versu
Caves of Qud employs a novel method of generating
unique worlds and quests, in which the world and story both
are generated in stages: the first, a generic story, at the world
construction, and the second when the player first enters a
specific region, to finalize the details of the environment and
associated story or quest
Finally, prior work has been done on using PetriNets, a
graph based structure for narrative mediation, player choice
enumeration and planning
This section gives the reader an overview of the game being developed by our industry collaborators, Blast Bit. We also describe the existing game engine and the goal and requirements of the project. The game (working title “Lance a Lot”) is designed for the mobile market. The game is a third-person role-playing game where the player is taken on a lighthearted journey through a fantasy world that does not take itself all too seriously. The game is created for players who enjoy exploration, interaction with hilarious characters, finding magical items and a good sword-fight. Through the journey, the player will interact with human and non-human NPCs, complete quests, fight enemies, and maybe even make choices that shape how the story unfolds.
The game world is divided into several separate, procedurally generated areas. Each area has its environment type, physical features, NPC characters, and associated quests. Upon entering a new area, the story engine defines the contents of that area – including characters, interactive objects, and quests – then sends this information to the world generator, which creates the physical layout of the world and populates it with the requested features.
The current game engine uses placeholder example terrain and quests. The generated information about the world state is stored in a knowledge base. Blast Bit’s ontological knowledge base includes the following categories and features described below as facts about the world. We also include a few examples from each category • Biomes: Snow, Water bodies, Quarries, Mountains, Desert (depicted in Fig. 2) • Locative Points of Interest: Settlements, Buildings, Vegetation, Boats, Chests • Resources: Ore, Berries, Water • Virtual Characters: – By Profession - Smithy, Cooks, Kings, Knights – By Species - Humans, Birds, Monsters, Dragons,
Wolves – By Relationships - Parent, Child, Spousal – By Physical Appearance - Arm length, head size, torso width, etc. • Events: Earthquakes, Invasions, Siege, Theft
The knowledge base informs the game’s procedural generation by putting constraints on the generation. For example, if the knowledge base states that a dragon lives near Area0, then the world generation knows it must create a dragon’s den in an area adjacent to Area0. This allows for thematic consistency across areas and for information about the game’s plot to be maintained, enabling larger, multi-area storylines.
The designed story engine is responsible for defining the physical features and elements contained in each area, and so also constitutes a large part of world generation. Additional responsibilities for the story engine include generating historical information about the game world and populating the game world with characters. Therefore, the story engine has been divided into multiple distinct generators.
To assist in explaining the functionality of our system, we use the running example of generating a quest involving the player fighting a dragon that has been terrorizing nearby villages. We walk through the creation of this region and the selection of the quest across generators from the ground up.
We use an iterative world-story generation system. First, a terrain is generated (e.g. a mountain), with some high level history (e.g. a mountain village). Next, a story is selected to fit the world (e.g. the selection of a dragon quest). This selected story then adds further constraints on future world or terrain generation (e.g., a dragon’s cave must be generated by the terrain generator, or homes in the region must be burnt down). This iterative world-story generation was chosen due in part to the vision of creating emergent stories from a simulation of the game world and its characters.
The separate generators by task, namely, the area and terrain generation, world history generation, and narrative and quest generation, have been illustrated in Fig. 3. Character generation is done by the quest and history generators. The generators work together to create each new game area, feeding information from one part of the system to the next to generate different aspects of the area. The flow of knowledge and information can be seen in Fig. 3. The triggers for the generators have been depicted as edge labels on the diagram. This section presents the current implementation of the terrain generator and describes in further detail the system design and intent of each of the generators introduced above.
When the player enters a new area, our system runs to define the area; this begins with terrain generation. The terrain generator outputs predicate-form definitions of the area’s biome, natural landscape features, preliminary information about connecting areas, and any other high-level terrain definition information required.
isArea(Area0); hasBiome(Area0, forest); hasFeature(Area0, trees); hasFeature(Area0, lake); hasFeature(Area0, boulders); isArea(Area1); hasBiome(Area1, mountain); isUndefined(Area1); isConnected(Area0, Area1); isArea(Area2); hasBiome(Area2, quarry); isUndefined(Area2); isConnected(Area0, Area2); Code 1: Example output of the terrain generator grammar. The forest biome, region Area0, was generated adjacent to the mountain region, Area1, and a quarry biome, Area2, which our grammar deems as valid neighbouring biomes.
The Terrain Generator utilizes Tracery
Our generator first defines a biome that constitutes a general flora and fauna type – for instance, a forest or a mountainous region. Biomes are used to ensure that diverse environments can be generated and that consistency between adjacent areas is maintained. When defining a region, the generator either begins with a biome at random (if it is defining the first region in the world) or a predefined biome type (if it is defining a region adjacent to or following one that is already defined). Our grammar controls the adjacency rules between biomes ensuring that biomes generated adjacent to the region are realistic. For instance, a desert may not generate next to an ocean. Code 1 shows an example of the terrain generator’s output.
Further, we use the Generate-and-Test methodology
"grasslands", "quarry" ] ...} Code 2: Code snippet from terrain-generation grammar resulting in the output shown in Code 1
In the output from our system in Code Snippet 1, the generator randomly assigned a forest biome to Area0. From there, the grammar expands a list of features available in forest biomes to choose which features can be found in Area0. In this case: trees, a lake, and boulders. This functionality will be expanded in the future to define resources available in the area, such as water, timber, and berries. Next, the terrain generator defines the biomes for adjacent regions. In Code 1, a mountain and a quarry were defined as adjacent regions to the forest. These adjacent regions are marked as “undefined” to let the system know that they must be generated further once the player leaves the current region and moves to the next. This allows us to further constrain our generation based on what the player discovers in the forest. Finally, the predicates output from the terrain generator is passed to the high-level history generator. Additionally, the predicates are taken as input by the game engine, that generates the geometric layout of the area and the locations of features within it.
The high-level history generator is similar to the terrain generator but defines human-made structures rather than landscape features. Examples of definitions created in this generative step include those for settlements, buildings, societal histories such as war and trade, individual characters, and specific occupational and personal information about the generated characters.
While a CFG-based approach may have met many of the High-Level History Generator’s requirements, many of the predicates it would generate are dependent on multiple existing predicates. For example, for a fisherman to generate, there must exist a town, and that town must trade in fish. Authoring a CFG that encodes these requirements may quickly become overly-complex and unwieldy. Other design considerations included simulating historical events and resource movement between settlements, though that level of detail was considered unnecessary for our purposes. Therefore, we decided on a design that reasons over existing predicates to generate the new predicates that describing these humanmade features in the game world.
In our running example, the current area has been defined as a forest containing trees, a lake, and boulders. Because this area contains a source of water and is a temperate region, the high-level history generator reasons that a settlement here is likely and creates the new predicates isSettlement(T own0) and contains(Area0; T own0). From here, the generator continues to define additional, more specific information about the settlement such as the resources it trades in, the individual buildings that exist in it, and who the occupants of those buildings are. In our example, one of the buildings created is occupied by a fisherman, as the town trades in fish and is near a lake. This generation will continue until the area is sufficiently defined or until no more inferences can be made. A partial example output of this generative step can be seen in Code 3. isSettlement(Town0); contains(Area0, Town0); tradesIn(Town0, timber); tradesIn(Town0, fish); isBuilding(House0); contains(Town0, House0); species(Person0, human); profession(Person0, fisherman); livesIn(Person0, House0); ...
Code 3: Example output of the high-level history generator
Once a history of the area and definitions of its inhabitants have been created, a preliminary model of the area’s contents exists and the Narrative Generator can select a story for the area.
The narrative generator uses the predicates generated by the previously-discussed generators (shown in Code 1 and Code 3) to generate a quest for the player. The generator can ensure that the selected quest fits with the overarching story arc the player is currently participating in.
The Narrative Generator generates a story for the new area by manipulating “plot threads”. When a plot thread is requested for a region, the generator either chooses from a list of existing, open plot threads from previous regions or creates a new plot thread that suits the given region. Each new plot thread is instantiated from a list of designer-authored quest templates.
While authoring the quest template, the designer must
include preconditions (in the form of predicates) that must be
met in the current world state for events in the world to
occur. We define our quest template to be a tree-structure
representation of a quest. Nodes in the tree are events that can
occur in the region given the preconditions for the same have
been met. This activation of template nodes is similar to
narrative research done by
The predicates of the quest template are generic (for instance, it defines that a house must exist to be on fire but doesn’t specify which house). An example of such a quest template has been depicted in Fig. 4. Once an event occurs, the player may choose to influence the outcomes and future events of the story; expected interactions are represented by forks in the quest template’s tree.
Events in the quest templates are partially ordered, for instance, the player will not encounter the dragon without first being warned of it in a prior region. This has been depicted in Fig. 4 where the player first encounters a burning home, then speaks to townspeople and hears of a dragon. Eventually, the player may traverse to an adjacent region with a dragon’s den, where the dragon can be fought. These partially-ordered constraints are also returned to the terrain and high-level history generator. For instance, the history generator now knows that one of the regions connecting to Area0 in the future could generate townspeople that have been tormented by the dragon and communicate the same to the player. Additionally, the terrain generator knows that in the future, once other preconditions have been met, a dragon’s den must be generated high in the mountains. This further restricts the generation in future unexplored regions. hasFeature(Area, lake) adjacent(Area, adjacentArea) hasBiome(adjacentArea, mountain) contains(Area, town) isSettlement(town) contains(town, house) isBuilding(house) Code 4: An example of the prerequisites for the first event in the quest template depicted in Fig. 4
In our example, Area0 is the first area created, and there are no existing plot threads that can be applied. Therefore, a new plot thread must be created. To select the quest template that will be used to create the new plot thread, the Narrative Generator searches through a list of available authored quest templates whose preconditions are met by the current world definition. From this list, the Narrative Generator randomly selects a quest template, favouring those which have not recently been used to create a previous plot thread. In this case, it begins the hero’s journey by selecting the dragon quest. It should be noted, that the narrative generator may choose to start another quest template even if an earlier one is incomplete. This may be seen as necessary, for instance, if the predicates of the world do not currently support an existing quest. Thus, the player may be partaking in more than one quest at a time.
From the perspective of the human designer, a single event, in this case, that of the house burning down, may be used in several quest templates. In one quest, the player may find out that the bandits in the area are responsible, in another, it could be the dragon. In the future, we will attempt to design an authoring tool that will allow for events to be tagged with a variety of quests, and accordingly, procedurally generate the characters or locations involved.
Low-level history generation is the final step in the story engine’s generation of the area. The purpose of low-level history generation is to modify the area to better fit the plot thread selected by the story generator. This generator works backwards to create explanations for why those objects exist in the world and how they affect it. Since the selected plot has defined events that will happen and objects that must exist, the generator will add those objects to the world generated so far. This chain of reasoning continues until the area definition makes sense in the context of the objects that were added during story selection.
The low-level history generator also serves the purpose of generating history on-demand to flesh out an existing world. This is useful for satisfying Blast Bit’s goal of allowing the player to ask NPCs questions about the world’s history.
To continue with the dragon quest example, since a dragon exists, the generator will reason that a nearby village fears it. If a village fears something, it may build fortifications. These fortifications are added to the region. Additionally, NPCs living within a range of the dragon on the map will start to mention their fear of the dragon to the player, giving the player breadcrumbs as to what to expect. Once this history has been generated, the player can then ask NPCs of the region questions regarding why a house was destroyed, or how fortifications were broken down, improving the explainability of the generators.
For this generation, we intend to use an in-house lockand-key logic programming language developed by Blast Bit. The predicates of the world are described as symbols that can be defined as a combination of keys. The preconditions in the story states are represented as locks and fulfilling these preconditions unlock new keys affecting the availability of our graph and change in story state.
We are excited about the capability of this generator to
add to the explainability
We were asked to design a system where the game environments, characters, and overarching story could be procedurally generated for increased replayability. Given these requirements, we were able to model a system architecture that was able to meet their needs.
The terrain generator component of the system was developed using a Generate and Test constrained, CFG-based approach based on Tracery’s grammar system. For the HighLevel History Generation and the Story Selection system a logic programming approach was selected. For the Narrative Generator an authoring language, using the plot thread approach described earlier is being developed. This will allow for the design quest templates by human designers and authors, allowing them to communicate their goals to the Drama Manager.
For the Low-Level History generation, we will be continuing development using the in-house logic programming language developed by BlastBit. This generator works backwards to add explainability to the world, describing reasons for the existence of objects, or events added to the world by the PCG generators. This approach, when fully implemented will satisfy the organization’s goal of allowing the player to converse with NPCs, asking questions or reasoning about the state of the world.
A limitation of the world-first model we have designed is that the story generator focuses on modifying or fitting each story template to the generated world. Flipping this model to a story-first design, where a narrative is first generated then a world is created to fit the story, may allow the authors and game designers more freedom to focus on pacing and narrative design in the story generator.