How to handle multiple story threads in a RPG game?

Question

I designed an RPG game that has multiple story threads, meaning that, depending on the user's choice some things may or may not happen, you can achieve the same thing in several ways, the ending can be different and so on.

I implemented a simple decision engine, which works fine but has one huge flaw, in the moment you take a decision the story is influenced immediately by your decision, which means that you can't take a decision that will affect you in the far future. This is because the story unfolds like a branch in a tree structure, and it always needs to know which node is next. Under the hood, the decisions are implemented using a queue: each node knows about the previous node and the next node (or if it's a decision node it waits for user input to set the next node)

I saw lots of games that have complex decision engines, and I wonder, how are they made? Is there a special design that makes the things really easy? Did anyone did something similar and can give me a hint on how to tackle this?

UPDATE 1:

An important aspect is to manage to somehow keep the story code independent, so that it can be manipulated from an external file. I plan to use this as an engine so even the possible choices have to come from an external file. The code has to be totally abstract.

Also, I'm interested in a design solution, a nice way to do it, how others do it or did it.

Answer 1

You could also generalize the queue into a directed acyclic graph (DAG). You can read about these on Wikipedia. Basically, each node can have one or more parent nodes that it "depends on". Cycles aren't allowed, i.e. if A depends on B, B can't depend on A (directly or via any indirect chain of other nodes).

Each node is in an "active" or "inactive" state, and is only allowed to become active if all its parents are already active. The structure of the graph (what nodes are there and how are they connected) is part of the game data, but the active/inactive state is part of the player's save data.

That way, you can model things like: when you plant a tree, you mark a task "plantedTree" as active; then, later on in the game, another task "treeGrown" names both "plantedTree" and some other node (part of the story) as its parents. Then, "treeGrown" only comes active when the player gets to that point in the story, and also "plantedTree" is active.

You can include other features such as nodes that activate if any one of their parents activates, or nodes that are activated by one parent and deactivated by another, and so on. It's a pretty general framework for creating stories with multiple, interdependent threads.

Answer 2

From what I understand, what you want is not just a decision engine, but a rule engine as well. For each decision you execute a subset of rules defined by that decision. The execution of those rules is often dependent on the state of certain entities like your tree example.

Basically, when your player makes a decision you search for that decision, execute the rules, and then provide the next set of available decisions like normal. However, your rules are dynamic in that some of them will only execute based upon other rules that have already executed.

Some more on Wikipedia.

From their When To Use Rule Engines subheading (emphasis is mine):

• The problem is just too complex for traditional code.
• The problem may not be complex, but you can't see a robust way of building it.
• The problem is beyond any obvious algorithm based solution.
• It is a complex problem to solve. There are no obvious traditional solutions or the problem isn't fully understood.
• The logic changes often
• The logic itself may be simple but the rules change quite often. In many organizations software releases are rare and rules can help provide the "agility" that is needed and expected in a reasonably safe way.
• Domain experts and business analysts are readily available, but are nontechnical.
• Domain experts are often a wealth of knowledge about business rules and processes. They typically are nontechnical, but can be very logical. Rules can allow them to express the logic in their own terms. Of course, they still have to think critically and be capable of logical thinking. Many people in nontechnical positions do not have training in formal logic, so be careful and work with them. By codifying business knowledge in rules, you will often expose holes in the way the business rules and processes are currently understood.

One thing to note is that occasionally a rules engine is best implemented using a simplified domain specific "language", or something like YAML. I would not suggest XML.

Answer 3

You have to consider that an event is not purely based on user decision. As you noted some event has to append if when a set of decisions sequences are taken and then something else appends (like two day after).

What I think you need is a way to model events and way to trigger it. While the first is more bounded to your specific case, the latter can be modeled by an hierarchical state machine (HSM) that directly or indirectly triggers your events.

Keep in mind that a state machine suffers of the Curse of dimensionality that is only mitigated by an hierarchical structure. Soon you will understand that you need to model the complex meaning of status using a HMS but also provide a way to query it.

In this scenario you have basic events (user decisions, time, change in weather and so on) that are processed by both the HSM and by basic event callbacks. The HSM provide a model for the "memory" and the callbacks provide a way to describe how that memory has to be used to compute the consequences of a sequences of decisions/external events.

You may also end up in using a dictonary (or some other collection structure) of HMS, one for each "aspect" of status you have to compute. An example may be to use an HMS event related and one for the decisions that callbacks take in order to trigger events.

All this infrastructure serves the purpose to mimic the behavior of a human Dungeon Master: he generally takes a mental record of the current situation (HMS["external"]) due to player decisions and environmental conditions; when something appends it can take decisions using its mental record and record some internal strategy status too (HSM["internal"]) in order to avoid to react in a similar way if the some situation appends for example.