# How do dialog trees work?

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.

• I think it would be great to have dialog-tree tag. – user1306322 Oct 24 '12 at 4:35
• Asking for code samples isn't usually looked upon favorably. – MichaelHouse Oct 24 '12 at 4:57
• If there are some dialog tree 101 code samples that are worth sharing, it couldn't hurt. – user1306322 Oct 24 '12 at 5:08
• The problem is that this site is about getting correct answers to questions. It's not for collecting code samples. – MichaelHouse Oct 24 '12 at 5:13
• That's why the sentence begins with "if". But what I'm asking for is the explanation on how dialog lines connect to each other in a way that can be efficiently translated to code. After all I'm going to write it in C#. – user1306322 Oct 24 '12 at 5:15

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.

• +1 For mentioning rules and conditions on links, a simple directed graph is often not enough, and things can become complicated when you start needing those. – Laurent Couvidou Oct 24 '12 at 8:26
• +1 I like that structure better. Though, I wouldn't recommend it as a first pass. I'd start with something simpler. It's certainly a better target to shoot for. – MichaelHouse Oct 24 '12 at 22:36
• +1 For a very detailed answer. This might come in handy for me later. – Marton Oct 25 '12 at 7:19
• This image has been very helpful to me, but I have to wonder why is DialogueLine separate from the Link? Wouldn't each link have it's own response text? And where would the NPC's text go? Would it not make sense to have it in the node? – Kyle Baran May 5 '14 at 23:09
• @Danjen In this structure, a Link can have multiple DialogueLines, possibly from different characters, until the next dialogue choice appears. This is also where the NPC text goes. When the lines repeat, different Links can share DialogueLines, possibly reordering them in their list (Vector), replacing parts of them with different lines, adding interjections and so on. – Martin Sojka May 6 '14 at 11:08

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.

• I just can't figure out what to do in cases like "Newton-trouble" in this picture. Like how to set the order of those lines in code without repeating them. – user1306322 Oct 24 '12 at 5:12
• You'll often find that dialog can be repeated. It's usually just marked in some way so the user knows they already choose that dialog path. You can put a flag in your edges that indicate if they've been selected before. So it's up to you to either allow users to select it again (to refresh themselves) or not show it. – MichaelHouse Oct 24 '12 at 5:17
• It wouldn't normally be done with the ordering of lines of code, but via the references in the data structure. – Kylotan Oct 24 '12 at 16:37

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.

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...

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();
}


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)

• The question asks for C#. – Seth Battin Nov 28 '13 at 15:49
• D'oh - sorry about that. – Scott Wilson Nov 29 '13 at 16:00