Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question
1  
When the important decisions are made, just keep track of them in a globally accessible variable (an array of these variables will be easier to manage). These variables can then be referenced by later parts of your game program to act or display things as appropriate. For example, the player decides to plant a small tree, and later that tree appears very large -- if they didn't plant the tree, then that tree wouldn't be there at all at that same later point in the game. –  Randolf Richardson Sep 16 '11 at 22:39
    
Yeah, that's what I initially though to, however, I need this to be code independent. That means that, the story can be fully manipulated from an external file. So, I have to find a way to generalize what you've just said and to do it in such a way so that I don't loose control over the project (there are quite a few decisions). Will update the question. Thanks! –  Valentin Radu Sep 16 '11 at 22:46
    
So to be more specific, I can't check if (isTree) or keep an isTree global var because the story may or may not have that choice in it. Know what I mean? It's more like a choice engine that will serve multiple stories. –  Valentin Radu Sep 16 '11 at 22:56
    
Also this has another problem, let's say that if the user decides to plant a tree we set isTree=true however, later, he does something else, like, fighting a school mate, who in return goes and chops off his tree while the tree is still young because he got his ass kicked. Now, we have 2 variables that influence the existence of the tree isTree==true' and didFightBrat==false`. Know what I mean? And the chain can go on forever, the existence of the tree can be influenced by an unknown number of factors. Know what I mean? –  Valentin Radu Sep 16 '11 at 23:04
    
Then store that data in a file on disk. You'll need to create two subroutines to load and save the information, and then use those routines from each part of the code on an as-needed basis. –  Randolf Richardson Sep 16 '11 at 23:06
show 2 more comments

3 Answers

up vote 16 down vote accepted

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.

share|improve this answer
    
A very good answer, thank you. It actually solves other problems I have too, like saving the user progress. This is what I need. –  Valentin Radu Sep 17 '11 at 15:38
    
@NathanReed Why couldn't this be cyclical? Being acyclic is typically not a feature, but a byproduct of the graph design. I wouldn't create it with that intention. For example, imagine if you wanted your tree to recognize seasons. They are by nature cyclical, and your story arc could be identical depending on the choices available during one season. –  Brian Reindel Sep 19 '11 at 16:29
    
It has to be acyclic because if there is a cycle, you get into an infinite loop when trying to figure out whether a node on the cycle can be active, because you recursively check all its ancestors, which include the node itself. If you wanted to model something like the seasons, I wouldn't do that in the context of this graph. –  Nathan Reed Sep 19 '11 at 16:43
    
@NathanReed Ah, sorry, I missed the recursive part. –  Brian Reindel Sep 19 '11 at 17:05
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.