Story engine

From Post-Apocalyptic RPG wiki

Jump to: navigation, search

Deprecated code proposal.png This article features a deprecated code proposal.

Deprecated Proposals are no longer considered for implementation. This does not necessarily mean that they are completely rejected but for now have been set aside.

This article is a proposal for a means to provide interactive story content in PARPG.

Contents

Specification

Sources

The two basic documents that this is drawn up from are

Goals

  • Provide a flexible means for telling stories in an RPG.
  • Avoid "programming" stories, or mixing with game mechanics.
  • Support separate concurrent stories, and stories at multiple levels of detail.
  • Support for all story parts, both dialog and non-dialog.

Non-goals

  • Support for stories of arbitrary computational complexity.
  • Support for generated content.
  • Tight integration with the PARPG game code.

Design

Overview

This design centres around the "story events" which make up any given narrative. The game mechanics and engine are responsible for knowing where a character is, how they move around, how they perform combat, their proficiencies and inventory and so forth. Story events are those things which will vary between different scenarios or locations, whereas game mechanics are those things which are consistently applied throughout.

Each story event can only occur when some set of preconditions is met. At any given time, a number of story events might be ready to occur. For example, a character might be ready to say any one of a number of different lines to different people; which she says will change the story. Each line is a story event; something that might happen in the continuation of the story.

The function of the story engine is to offer the game a set of story events that may occur. The game may or may not select one, in which case it notifies the story engine of its choice. This degree of flexibility is needed to make sure the human is able to influence the outcome of the story: when a set of choices involve the player character(s), the game can pass that choice to the human by presenting a list of options. When the set of choices only involves non-player characters, the game must choose by other means (e.g. randomly).

A story writer creates a set of story events, either initially as a text file, or later in an editor, which the game reads and acts upon.

Interface

This page concerns the game from a developer's point of view. See Story Format for more detail on the user interface.

Internals

The story engine is required to do the following:

  • Parse a story into some internal representation.
  • Examine the game state to see If any events can happen, and if so which.
  • Perform events as requested by the game.

The major challenge is in making the game state check fast enough so that the story engine can be called at rapid intervals. This rapid polling allows much more control of interactions with NPCs (in effect, the story engine is the AI).

Basic Structure

The steps in processing are described in the next few sections. A rule is the combined beforehand sections of an event (there can be more than one).

  1. A rule may contain property requests ("John"s "horse", "name" of "villain"). Each of these is an attribute request. We make no assumptions about what can be looked up. The game is called back with a request for a string result: string get(string,string), e.g. get("John", "horse") could return "Binky".
  2. There are two parts.
    1. A rule may contain predicates ("John" is alive, "Bob" is hungry) which have an associated callback function defined for them. These have the form bool predicate(list<string>), e.g. is_alive(("John")) could return True.
    2. A rule may contain story predicates ("princess has been rescued", "plot to kill king" has begun).
  3. Predicates may be joined together by logical operators, and, or, not and xor.
  4. An event depends on the result of these joins.
Rete is a standard algorithm to tackle these kinds of systems; an example of the particular class of rete we're working with is shown on the right
Rete structure
. The parts correspond closely to the parts outlined above:
  1. G nodes perform attribute resolution (G for getattr). They can also represent literal names. They stand for a string value.
  2. P nodes perform external predicate calls (P for predicate!); they take G node inputs and come up with a boolean value.
  3. K nodes perform internal predicate calls (K for knowledge); things like assertions about available story knowledge are encoded in K (events that have occurred, remembered states).
  4. B nodes perform logical operations; joins (B for boolean) - and, or and xor, and negation not.
  5. E nodes represent an event; if the B node they depend on is true, the event is available, otherwise it is not.

Processing at G nodes

Each G node has a left hand side and a right hand side. These may be other G nodes, they may be literal names, or they may be variables. Variables complicate things considerably.

Example G node structure.
  • The example used throughout this section is (person).inventory.[(lockitem).key].weight. The variables are (person) and (lockitem), [] denotes a nested expression. For example if (person) binds to john and (lockitem) binds to magicdoor then this will be john.inventory.[magicdoor.key].weight. If magicdoor.key is runekey, then this is john.inventory.runekey.weight. The process by which we work such things out is described here. We'll assume a set of top level ids of [John, Fred, magicdoor].
  • Start at node 1. This has a variable (person) on the left hand side which indicates a selection from the top level of entities (things in the root name space - in a.b.c, only a is in the root name space). G node 1 must consider every option, so it builds a list of lhs bindings. [John:{person: John}, Fred:{person: Fred}, magicdoor:{person: magicdoor}]. On the right hand side is a literal "inventory".
    • Each binding is a possible outcome, so John:{person: John} is one outcome, it says the value of the lhs could be "John" (the first bit) if the variable (person) took the value "John" (second bit). The above has a list of three such bindings.
  • G node 1 resolves all possible outcomes. So it first combines every lhs with every rhs, keeping track of what assumptions each outcome relies on. So we have [John.inventory{person: John}, Fred.inventory{person: Fred}, magicdoor.inventory{person: magicdoor}].
  • Before it finishes though it needs to actually do the lookups its responsible for. So its result set is the result of performing the lookup (each lookup results in a new string identifier, we'll assume we picked a simple naming scheme like inventory_fred, inventory_john to name the inventories that belong to the different characters; the story engine knows nothing of our naming conventions, it just sees strings). We'll assume a magicdoor doesn't have an inventory. In which case this lookup fails, and the G node discards the possibility. Our result set then is [inventory_john{person:John}, inventory_fred{person: Fred}].
  • Now consider node 2. This has the left hand side (lockitem) and the right hand side "key". The process is very similar to that for node 1. The initial merge gives [John.key{lockitem: John}, Fred.key{lockitem: Fred}, magicdoor.key{lockitem: magicdoor}]. We'll assume John and Fred don't have a "key" property, so the result set will be just [runekey{lockitem: magicdoor}].
  • Now we've handled both the dependencies for node 3, we can process it. It has G nodes on both the lhs and the rhs. These give it a set of possibilities to examine by combining all the options pairwise. The initial merge will give us [inventory_john.runekey{person: john, lockitem: magicdoor}, inventory_fred.runekey{person: fred, lockitem: magicdoor}]. For the sake of brevity, lets assume Fred doesn't have a rune key, but John does. In which case this resolves to runekey_inventory_john{person: john, lockitem: magicdoor} (the same naming scheme as before; its the name of the runekey in John's inventory. Remember these are properties, an inventory might more naturally be a list but this doesn't handle that directly, this code handles maps).
  • Finally we've handled all the dependencies for node 4. It has a lhs of a G node (node 3), and a literal on the rhs "weight". The merge is as you would expect, we take every possibility on the lhs and combine with every possibility on the rhs. There's only one of each so we get runekey_inventory_john.weight{person: John, lockitem: magicdoor}. This resolves (lets say: a key has a weight), and we end up with the result of the expression along with the variables required to make it true e.g. ["15" {person: John, lockitem: magicdoor}].
  • There's no reason this necessarily terminates in a list of length 1, it could 0..n (there might be no matches for what is asked for, or there might be many).
  • The example doesn't have a variable on the rhs, but in that case we can't look up the potential variable values in the global table (that would defeat the point) we need to ask each entity on the lhs what rhses it has keys defined for. The lookup in this case is specific to the lhs, and we do one per lhs.
  • This doesn't talk about caching. It's possible we need a buffer between the Rete and the game which can know a set of variables are slowly changing and not pester the game for information about those variables. When we know things aren't changing structurally, whole sections of the Rete can be marked unchanged and no processing done on them. This will require further analysis.
  • Offering a structured namespaces will solve most of our problems e.g. people. trees. buildings. items., so that only very very rarely are any unifications attempted across all instances. We'll need to be able to represent this in the story format using another kind predicate, for example ("guard", a person). This is compile time only so we don't add runtime complexity.

Processing at P nodes

A P node represents a predicate, which may have any number of arguments (including none). Each argument is a string, and the task of the P node is to collect them together and call the user supplied callback function for the predicate. Variables complicate things.

  • The example we consider here is ("someone") is more than 5 years old. The game supplied predicate string is "%% is more than %% years old", and the corresponding function is age_more_than(entity, age).
  • The P node examines its arguments in order. Its first argument is a direct variable, which means it binds directly to the predicate (in contrast, in '("someone")s "horse" is more than 5 years old' the variable is resolved by preceding G node. When we have direct variables, it is the job of the P node to find out what could go in that slot.
  • The P node calls a user-supplied function asking "what could go in argument 1 of this predicate", and gets a list of strings back, for example "John", "Barney", "Binky", "Fido"; the reason for this is because the predicate will sometimes have a much better idea of what might go in that slot than could be achieved by full search through the same table as the G nodes (e.g. "%% was clicked" is a trivial problem for a callback, but extremely time consuming if we must test every element in the top level namespace for a click).
  • The P node now forms a set of partial argument lists and contexts [("John", ):{someone: John}, ("Barney", ):{someone: Barney} ("Binky", ):{someone: Binky}, ("Fido",):{someone: Fido}].
  • It processes its next argument, here "5". Since this is literal, the argument lists can be simply extended with it. This forms [("John", "5"){someone: John}, ("Barney", "5"){someone: Barney}, ("Binky", 5):{someone: Binky}, ("Fido", 5):{someone: Fido}].
  • The P node now has all the information it needs, and it calls the user supplied callback on each argument list. age_more_than("John", "5"), age_more_than("Barney", "5"), etc. Every time the callback returns true, it adds the set of bindings and the result to its result set (false returns can be ignored). if John is 30, Barney is 20, Binky is 5 and Fido is 3, then the result set is [true:{someone: John}, true:{someone: Barney}].
  • Processing is complete for this node.
  • There's no mention of caching, but for slow changing predicates, it will probably be worth storing their results and only updating as needed.

Processing at K nodes

K nodes are statically set to available or unavailable (true or false) by E-nodes and the runtime, in the course of executing events. They do no processing, and in particular never need updating during regular queries.

Processing at B nodes

A B node represents a boolean operation, one of and, or, not and xor. B nodes are internal, they don't need to make callouts to the game, and they don't need to resolve variables. This makes them much simpler than P or G nodes.

  • A not node takes a set of variable bindings and inverts the bindings. This scheme was quite complicated to work out, but if previously we had "true provided x=10", we now have "true provided x!=10", and the converse.
  • An or node takes a pair of sets of variable bindings and joins them. If "true provided x=10" is on the left hand side, and "true provided x=11" is on the right hand side, the result is a list of both options.
  • An and node takes a pair of sets of variable bindings and returns every consistent union of an element of the lhs with an element of the rhs. This is a full product, so every binding on the lhs is tested against every binding on the rhs for consistency. Consistency means they agree on all variables they specify. Particularly important is that x!=10 and x!=11 are not consistent by this definition, because they are not necessarily both satisfied at the same time.
  • An xor node takes a pair of sets of variable bindings and returns every element of either side which cannot be placed in a consistent union with any element of the other side. The reasoning is that if an element had a consistent union with an element of the other side, its bindings could lead to both sides being valid.

Processing at E nodes

The story engine runtime

The runtime collects together all the different types of node and is responsible for asking them to update. Updates must occur in dependency order (if node P1 relies on node G2, we must update G2 before we update P1). This is handled by maintaining a dependency ordered list of nodes, and executing the list in order. This is more efficient for large networks, and avoids the risk of stack overflow associated with many nested function calls.

The runtime is also responsible for identifying which E node is responsible for a requested event, and for passing the execution request on. Since almost every story event involves the alteration of K nodes, when an event is executed, a static reachability update is performed.
Updating the graph based on static information

The update is based on the observation that K nodes are known to be true or false statically in between event executions. We can define the property of being statically determined. All Ks are statically determined. Any E node depending directly on a statically determined node is statically determined in the same way. A B and node with a statically false input is statically determined to be false. A B or node with a statically true input is statically determined to be true. A B not node is always statically determined if its input is statically determined. An xor B node can only be statically determined if both its inputs are statically determined.

The second properly is irrelevance. In (x and y), if x is statically determined to be false, we know the result of the clause without evaluating y; this is the logical short circuit operator && in C/C++. A similar property holds for or: (x or y), with x statically true corresponds to || in C/C++. A node is irrelevant if all its dependents mark it as an irrelevant branch; this in turn makes all of its links irrelevant.

Statically determined nodes and irrelevant nodes do not need to be evaluated at runtime to determine their outputs. This results in pruning a significant part of the node graph. The image shows a simple example in which there are two K nodes, one true (black) and one false (white). These lead to the results of two and nodes being known to be false (both white). This in turn leads a P node (marked grey) to be found irrelevant (it has no bearing on the available events).

Software elements

A library which can:

  • read a set of story events from a file.
  • be queried efficiently about what events can occur at this time.
  • enact consequences of selected events.

A debug shell which supplies a simple environment to test stories in:

  • manually supply the necessary knowledge that the game would otherwise provide.
  • clearly see which events are available and why.

An editor to allow easy creation of stories:

  • graphical layout of story events.
  • automation of some details of story arcs and so forth.
  • Note that this may be hard and very time consuming to develop.

FAQ

Do we really need another layer?

The bottom line is yes. Virtually every game with content (levels, scenarios whatever) has a distinction between the game itself and that content, rather than having the content hard-coded in. Even though our game uses an engine, it still has game code (mechanics, visibility, menus, and so forth). This is distinct from the actual content that's written: the dialog, the plot, the maps, the characters and so forth.

Why not just use python scripts?

Maybe we could avoid having this complicated component and another input format if writers just write a big python script for each campaign? This is a bad idea. A large campaign is complicated and has a great deal of interrelated content. It's quite difficult to manage all of this cleanly even for a trained software engineer. Do we really want to limit our writers to trained engineers? This input system takes care of many many details, including:

  • doing all the necessary tests fast enough
  • handling generic cases (e.g. the first soldier you see says xyz)
  • tracking what has been said and what hasn't
  • building dialog trees adaptively from a wide range of sources

Why not just use SQL? SQL can do anything!

Let's think about what you'd do in SQL. You'd have an event table, and perhaps a precondition table, and you'd perform joins between the valid preconditions and the event table. You'd also need some table of post conditions to perform. I'm not sure this is possible. If it is I don't know how to do it. If someone wants to implement it and show its as efficient as Rete in this case, please do so. You lose points for rolling your own parsers into SQL strings.

Personal tools