How do dialog trees work?

Question

That is, what is connected to what and how to move between lines of speech when a sub-conversation ends?

If you have any examples of a basic dialog tree in C#, please post them.

Answer 1

The name "dialogue tree" is a bit misleading - they usually are simple directed graphs, not just trees. The basic data structure of such graphs usually consists of some kind of "data" for the nodes, which represent the points we are at in the conversation, and links from them to other nodes, which represent what is being said and done by the participants and optionally have conditions on them to limit their visibility or scripts to perform various additional actions. Usually one of the nodes is the default starting node (typical labels for that are "ROOT", "START" and "GREETING"), and nodes which have no valid links leading from them end the conversation.

In most cases, the graph is represented in-memory as a list of Node data structures, each having at least an ID and a list of 0..n Link data structures. The list can be local to the NPC or a global one; the second case is preferred if you have lots of generic NPCs which can be talked to for information, but offer no specific conversations on their own. The system itself finds the starting conversation node for the NPC, remembers its ID as the current conversation ID, presents the currently valid links for the player to chose from (or "[end conversation]" if there are no valid links) and waits for input. When the player chooses a link, the associated dialogue lines get displayed and any associated scripts run.

Instead of having complex rules and conditions on links, you can instead get by with a simple "valid" boolean variable, which can be then changed from either the scripts of other conversation links (including the default one from the starting node) or by outside mechanisms. In general, this approach is simpler but only suitable for games with very few such conversations, since it moves the logic of "When is this response possible?" away from the response data itself.

---

Note that the structure I describe here is slightly different from Byte56's in that the nodes don't need to have any dialogue lines; the links can have them all. In the most basic variant, this translates to the following structure.

Answer 2

Dialog trees are created with a directed graph structure.

The graph is traversed based on the dialog decisions the player makes. The dialog options provided to the user come from the edges that define the paths to other dialog nodes.

Directed graphs are a basic data structure. They can easily be implemented and you'll likely want to implement it yourself. Since you'll want to tailor the graph to your dialog needs.

Some of the nodes may need to have special conditions met in order to show up. For example, the player would require a skill in speech above X. Or the player needs to have completed mission Z before they can progress down one branch of dialog. Or they need to ask something 4 times before the NPC will discuss it with them. These features will be custom to your game. But are worth mentioning when you're implementing the node and edge traversal. Of course it's always best to start with the simplest form and build up from there.

Answer 3

I've built a simple dialogtree system: http://iki.fi/sol/d3/ the "engine" itself is currently plain c, but the data produced by the editor is pretty simple to use in any language. The tool outputs XML, JSON and a custom binary format.

The main concept is pretty simple:

Each node (which I call "card", as with the above analogue) of the dialog consists of question text and zero or more answers. Each of the answers leads to another card.

There's also a tag system where certain answers are shown to the user only if a tag is set (or a tag is not set). Entering a card sets (or unsets) specified tags.

This is pretty much everything one needs to do just about any kind of dialog in a game. The "question text" can be plain text, or it can be a script to drive animation or whatnot.

Answer 4

You can use TreeSharp and behaviour trees to model a dialogue system. TreeSharp is a library that provides a simple behaviour tree implementation. IA bots for wow are done with this, so it's mature... :)

My implementation has nodes that let choose between answers, and each answer can be joined to othe dialogue or an action, or a sequence of actions, or a node that lets going to another dialog... or what yo want...

I have used brainiac editor to make it visually... but at the end it produces c# code based on treesharp...

http://www.youtube.com/watch?v=6uGg6bUYyUU

Answer 5

You want a directed (possibly cyclic) graph.

You'd model the nodes as objects, and all the outgoing arrows in a graph's node are modeled as separate objects, too. The node has a list of outgoing arrows, and each "arrow" object has a text to display and a reference to the destination. Not sure, but I think in C# objects are always referenced, so you just create the objects first, and then when you create the arrow objects, plug the same object into two arrows' destination field. (In C++ you'd use a reference or pointer type, Node& or Node*)

For loading things like this from disk, one usually gives each node a unique ID number, then loads all nodes into an array where the index is that unique number. Then the arrows are serialized by writing the number, not the actual object out.

When you load an arrow, you use the array and ID to get a reference to the node it points to. If you wrote out the object twice, you'd get two separate objects that just look identical, which is probably not what you wanted.

Processing a dialog tree becomes very simple. You just put the root node in a currentNode variable, display the whole thing somehow, then when a choice is made, set rootNode to the arrow's destination. In pseudocode:

Node&    currentNode = dialogTree.node[0];
while( currentNode != END_CONVERSATION_PSEUDO_NODE )
{
    stage.displayNode( currentNode );
    currentNode = stage.waitForUserToChoose();
}

Answer 6

I recently had to develop something like this using Node, and opted for a very basic text file structure to represent a directed graph of conversation nodes.

You can see the resulting code and text format at:

https://github.com/scottbw/dialoguejs

It doesn't support conditions or event triggers (yet), but is probably simple enough to start with for many game devs.

(The code itself in GPL, btw)