Smart terrain causality chains

An approach to adventure-game puzzle generation

(Co-written with Isaac Dart.)

A major criticism of the traditional adventure-game genre has been that once a player completes a game, there is little or no replayability. This is due to the progressive, story-driven nature of the genre, in which a player uncovers how to progress through an environment, solving puzzles and watching the story unfold along the way. Once the progression has been uncovered, there is minimal interest in uncovering the same thing again.

One approach to increasing replayability could be to make the story less linear and more dynamic. In recent years, some adventure games such as Heavy Rain have attempted to overcome the replayability issue by introducing branching storylines, where a player's choices influence which forks are taken. The motivation for branching stories is usually to increase agency—making the player feel that their decisions really impact the story—rather than specifically replayability. Nonetheless, branching stories in adventure games do add a certain kind of replayability, since the player can take a different fork the next time through, and experience a new portion of the story, which will contain new challenges not seen in the first playthrough.

A problem with branching stories is that considerable additional authoring and engineering effort is needed: each of those branches, and all the locations, characters, and art assets needed for them, must be created and tested. Procedurally generating those story branches is a possible medium- to long-term solution, but involves solving a mixture of content-generation problems, including the notoriously difficult problem of story generation.

We propose a different approach: replayability without high-level narrative variation, by procedurally generating puzzles that reuse existing locations and fit into the existing narrative progression. Despite retaining the same storyline and content, this will nonetheless produce new challenges when replayed; the player cannot just rush through doing exactly the same thing as on a previous playthrough.

We aim for a near-term, practical, "drop-in" solution to adding procedural variation within adventure games. We can observe a common pattern in adventure games where portions of the story have as a bottleneck an objective the player must reach to progress, and a puzzle they must solve to reach the objective, often by using several items. A simple example might be to open a treasure chest; the puzzle is finding and using the key. For our purposes, each challenge is made up of game props which, when used in the correct way, solve the challenge. It is at this level that we are able to introduce emergence and replayability into adventure games without requiring changes in the high-level content: by retaining the same objective of a particular challenge, but varying the available props and their usage, we can replace a puzzle with another one that serves an equivalent role in the story progression, but is not the same as on previous playthroughs.

Smart terrain causality chains

Items in an adventure game can be viewed from the perspective of "smart terrain", which characterises items by what problems they can solve for the player. The term was popularised by game designer Will Wright; in Wright's The Sims, "objects on the terrain broadcast what they offer to a Sim character... for example, a refrigerator might broadcast the fact that it can satisfy hunger" (quote from AI Game Programming Wisdom, p. 23). Pieces of smart terrain, like the related computer-graphics concept of "smart objects" [pdf], can be queried for a list of actions a particular object can perform, relative to some semantics of a given virtual world. Objects may also broadcast and react without direct player involvement; for example, an oven in The Sims offers the player a list of explicit actions the oven can be used for (e.g., bake another item), and also contains actions not shown to the player, such as catching on fire if an item is left too long.

In an adventure-game puzzle, what an item does for the player is one of two things. Either it solves the puzzle directly, allowing the player to reach the objective, or it produces an effect on another item, which will allow another item to (eventually) get the player to the objective. Therefore we can think of any puzzle solution as a sequence of items; this is the smart-terrain shorthand for viewing a puzzle solution as the sequence of actions that the player can take by using those items.

A smart terrain causality chain (STCC) is a directed graph specifying the causal dependencies between the smart terrain objects present in a scene and the objective of the puzzle. The figure at right shows an example causal chain, one that produces steam from starting items wood and ice (by burning the wood, which produces fire, which melts the ice, which is then evaporated by the fire).

In our experimental game Space Dust, many of the items provide the player with an "actions" menu when selected. These active actions could be compared to The Sims' oven in displaying a list of actions to the player. On the other hand, passive actions are those which occur without player input, such as a "heat" instance notifying nearby smart terrain to increase in temperature.

Smart terrain

Unlike in traditional adventure games, items do not have to play a single role. In a traditional adventure game, a piece of paper with a code on it might be used to convey to the player what code to enter when opening a vault. Once the vault door is open, the paper may have no other meaning or use in the game, if none was programmed for it. This narrow model can often be a source of frustration for the player when she believes that such an item could be used in other tasks which it wasn't programmed to do. For example the game may enforce a rule that she has to find some newspaper to light a fire, despite the fact she already has the code written on paper, which should also be burnable. To procedurally generate puzzles, a more flexible model is required that allows items to affect other items that they may not be aware of, or have not even been created at that point. This model is less concerned about particular object interaction, and more concerned about how a type of object affects the environment and how environmental forces affect that type.

Compared to the classic "hard coded" approach, where newspaper is programmed to burn when a lighter is used on it, smart terrain paper doesn't need to know anything about what item will make it burn; rather it simply knows that it should combust if its temperature reaches a certain point. In other words, smart terrain objects only need to know about their own behavior and reactions to other physical forces, rarely reacting to particular instances of other objects.

The interactions between smart terrain objects are implemented at two levels: a physics simulation in the game engine itself that implements the actual interactions, and a symbolic description of the possible interactions, which is used to procedurally generate causality chains. In both cases, objects are arranged into object hierarchies, so for example a newspaper is a kind of paper, and inherits the behaviors that all paper has (such as burning above a certain temperature).

Physics simulation

The physics simulation provides the "glue" that causes interaction between objects without each knowing about the other: a fire knows to emit heat into the world, and a paper knows to burn when heat passes a threshold. The physics engine is the medium in between the two that propagates the heat from the fire to the paper.

The physics engine for Space Dust is implemented in the Unity game engine. The root smart terrain objects are the three classical states of matter: solid, liquid, and gas. Objects can be modified by undergoing the familiar phase transitions—melting, freezing, evaporation, and condensation—as well as by undergoing custom transitions, such as crumbling a piece of paper or burning it. (The fourth phase of matter, plasma; and the direct solid/gas transitions, sublimation and deposition, are a bit too esoteric to be commonly used in adventure-game puzzle physics.)

Objects affect each other by direct collision or indirect energy. Object movement depends on the state: solids can fall via gravity, liquids not in a container disperse along flat and downwardly sloped surfaces, and gases not in a container diffuse through the air. If these movements cause two objects to collide, they may affect each other as a result. Alternatively, objects can emit several kinds of energy, which will affect objects in range that respond to that kind of energy. Energy can come in many forms, of which we've implemented four: thermal radiation, electrical current, radio transmission, and sound emission. Each of these travels in different ways; for example, thermal radiation expands in a gas-like cloud, whereas radio transmission instantly reaches everywhere in range.

Generating causality chains

To generate causality chains capturing a sequence of smart object interactions that can solve a puzzle, we need a qualitative version of this physics simulation rather than the full numerical one, capturing which interactions are possible when the simulation is actually run; for example, the facts that paper can burn, and water can short-circuit electronics. To keep it lightweight, we don't implement a full qualitative physics system, but instead maintain a discrete list of possible actions that can act on each smart-terrain object, together with the cause and the effect of each action. Doing so allows us to implement a simple, greedy backwards-chaining planner directly in Unity, with actions retrieved from an embedded SQLite database.

Each object is assigned an ID, and can appear one or more times in a table of actions, which has four fields:

• object_id: The object this action operates on
• action: A verb describing the action
• cause: A symbol specifying what triggers this action
• effect: A symbol specifying the outcome of the action

For example, consider two objects. A sprinkler can undergo action activate, when subjected to cause smoke, producing effect water. A paper can undergo action burn, when subjected to cause fire, producing effect smoke. From this example pair, the causal chaining possibilities should be clear: one possible way to produce water is to use fire (from another object, perhaps a lighter) to burn a paper, which produces smoke, which can activate a sprinkler, which produces water. If a cause is of the form object(object_name), it means that the action can be directly caused by a specific object. If an effect is of that form, it means that the action spawns the named object.

Smart terrain causality chains are procedurally generated by starting from a set of objectives for a scene, and backwards chaining until they ground out in causes that are all primitive smart-terrain objects that can be placed into the scene. A scene is simply the level of granularity at which we generate puzzles; the outcomes of a scene are used by the author to connect the generated puzzles into the larger story progression. Each scene can have one or more possible objectives, and achieving any of them is considered a puzzle solution. Each objective is a specific effect on a specific smart terrain object. For example, in Space Dust, the player escapes the prison cell whenever the effect turn_off happens on the smart terrain object electro_bars.

A simple backwards-chaining algorithm suffices to solve this problem. We first choose a random objective, and add the effect needed to satisfy that objective to our list of effects that we must cause. Now we look for an action that has that effect, and add it to the causality chain. This action in turn may need some causes, and we repeat, finding another action whose effect matches up with the needed cause. This process continues until it grounds out in the specially treated cause object(Player), indicating something the player can do directly.

This formulation can be seen as a subset of STRIPS planning, itself a simplification of logical planning in which the objective and all preconditions and postconditions of planning operators must be conjunctions of positive literals. A STRIPS operator corresponds to our actions, a precondition to our causes, and a postcondition to our effects. Since we have no logical operators, we trivially meet the STRIPS conditions, and as a result, simple backwards chaining rather than more complex theorem proving suffices.

To produce the puzzle, all smart-terrain objects referenced in the STCC are added to the scenario. By construction there will be one or more solutions to the puzzle as a result, taking advantage of the duality between puzzle solving and puzzle generation. In addition, all items placed in the puzzle will have some possible use for at least one of the solution paths, which is consistent with traditional adventure-game design, in which the player finding objects is typically used as a hint towards the solution, so having many objects with no purpose wouldn't be desired. However, if desired, the algorithm can be run multiple times and the runs combined, to produce puzzles with multiple solutions.

When adding smart-terrain objects to a puzzle, there are several additional cases. Objects at the leaves of the smart-terrain object hierarchy are concrete objects, and have graphical models associated with them, so they can be instantiated and placed in the world. Objects further up the hierarchy are abstract smart terrain, which can be referenced when building causality chains, but must be specialised to a specific object before the puzzle can actually be produced. By inheritance, however, any object beneath the abstract object in the hierarchy may be selected (we simply select randomly). Secondly, some objects may inherently depend on another object, for physical or conceptual reasons. We keep a second table of object dependencies, and add in any dependencies of the objects contained in an STCC, even if they aren't themselves part of the causal chain.

Finally, some objects may need to be included to make the puzzle a challenge at all; each scene includes a list of such mandatory objects. In our Space Dust puzzle, for example, there is one solution that involves the player exiting the room without turning off the electric bars blocking the doorway (instead, the player shrinks and exits through a small hole). Therefore, this solution's STCC doesn't include electro_bars in it, so they wouldn't need to be added to the scene as a required smart-terrain object for the puzzle solution. But if they aren't added, the player can simply walk out the unobstructed door! The bars are needed here even if the player doesn't use the solution that involves disabling them, because they serve the purpose of enforcing the challenge even for other solutions. This meshes with Joris Dormans's observation [pdf] that procedurally generated missions are insufficient for enforcing challenges unless coupled with world boundaries.

Space Dust

We built a prototype game, Space Dust, in which a single adventure-game level is replayed multiple times, as a core part of the gameplay (multiple playthroughs are intended to be necessary). The goal was both to test our puzzle-generation system, and to investigate the hypothesis that adventure games can have significant replayability added if the puzzles are varied, even when the general story progression isn't.

The player plays a character imprisoned on board a space ship adrift in deep space, attempting to escape from a prison cell. Each time the player gets caught, or passes out, they wake to find themselves back in the cell with a new puzzle to solve. The screenshot at right shows a first-person view, with the electric bars blocking the cell exit being shorted out by water from the fire sprinklers.

Once the player solves the main objective of escaping from the cell, they have a choice to go to the left or right corridor. To the right is certain death by way of a Killer Bot's stun gun, and to the left is an airlock. The airlock will eject the player into deep space where they have a short amount of time to find the airlock entrance to the bridge before passing out and waking, once again in prison with another procedurally generated puzzle. Since this involves a series of immediate replays, rather than generating puzzles purely randomly, we store generated puzzles and make sure that subsequent puzzles don't repeat any previous puzzle (until the game is completely restarted).

As intended, no playtester has won the game in their first ten attempts. The reason for this borderline abusive win condition was to guide the gameplay into presenting multiple scenarios to the player in order for them to experience, solve and hopefully enjoy the replay value of the game. One playtester enthusiastically described the experience as being similar to the movie Groundhog Day.

The player interface in Space Dust is a typical 3d adventure-game interface. The player can walk around using WASD controls and mouselook; players can also pick up, use and even throw Smart Terrain items, as well as interact with characters by selecting them and being presented with a context sensitive smart-terrain actions menu.

Example puzzles

Three example generated puzzles illustrate some of the range of variation:

Controlling difficulty

The difficulty level of a puzzle can be altered by changing the number of solutions which are procedurally generated in parallel. Players can have between one and three parallel causality chains generated at a time.

It is not immediately obvious if more solutions in a scene make the main objective easier or harder to complete. More solutions allow multiple routes to complete the objective, but also cause more objects to be placed in the scene. Because players often rely on the objects in a puzzle to guide their line of thinking, having many objects in the scene may confuse the player as a significant portion of objects will play no role in their final solution.

In order to determine whether more solutions increases or decreases the difficulty of solving a main objective, a playtest was performed, in which ten testers were given generated puzzles with between one and three parallel solutions, which they played twice each, before answering a survey which included questions on the difficulty in escaping from the prison cell.

The survey revealed that 70 percent of people found that more solutions were easier. A number of participants commented that it was easier because they could switch strategies and try another solution if they got stuck with a particular item. Several players did find that more objects caused more confusion, however.

Looking at variation within a single puzzle, players generally said that the longer the causality chain was, the more difficult it was to solve. One player commented that a puzzle made of two objects was "insultingly easy". On the other hand, only one person was able to solve the puzzle with the longest chain. Puzzle length is therefore another viable alternative for mapping against a difficulty setting.

* * *

In summary, smart terrain causality chains (STCCs) are a technique for procedurally generating adventure-game puzzles by generating adventure-game puzzle solutions from a set of smart-terrain objects, and then placing those objects into the scene. Smart-terrain objects are annotated with effects they can trigger or have triggered, but are not directly linked to other objects. In a classic adventure-game style, they can have multiple uses—the note on which a code is found can later be burned to produce smoke, for example, without this explicitly being programmed. STCC-based generation can produce multiple puzzles fitting into a common place in a larger story progression, by constraining a specific generated scene to end with a specific objective; this allows for increasing replayability by making puzzles procedurally generated without having to solve the full problem of story generation for adventure games.

Our experimental game Space Dust showcases this replayability in an admittedly somewhat extreme way, by designing a game where the typical player has to replay the same scenario approximately ten times before they're able to successfully beat it. Each replay has a newly generated puzzle with the same objective (escaping from the ship), and the player retries until they successfully escape. Our preliminary experiments showed that players found this engaging, despite it being the "same" puzzle played repeatedly, if viewed from the perspective of story progression. This opens up a new space of possible procedural-puzzle-based design tropes in adventure games, in addition to potentially increasing the replayability of more traditional, story-driven adventure games by varying the puzzles on subsequent playthroughs.

Space Dust is available for free download.