[SOLVED]Traversing a Dialog tree

Unity Engine
1

I’m now stuck in the middle of nowhere, and I need some directions!

I have a script that will parse and convert an XML file to a class with several subnodes. I’m now trying to come up with an algorithm that will display the messages in the correct sequences.

Not as easy as it sounds.

This being a dialog/conversation tree, the “traversal path” can go anywhere, and I would hate to have to hard-code which lines are said. Plus, that would defeat the purpose of the XML file, which is set up in a “tree” fashion.

Here’s an example XML file that I will be trying to convert into a conversation (though it’s not complete). These are the actual lines planned to be used in my upcoming game (thus, it makes more sense in context):

<?xml version="1.0" encoding="utf-8" ?>
<Conversation>
  <subNodes>
    <ContentNode id="1" orderNum="1" linkTo="0" type="npc" name="Cleric">
      <text>Hello! We welcome you to our humble worship grounds!</text>
    </ContentNode>
    <subNodes>
      <ContentNode id="2" orderNum="1" linkTo="0" type="pc" name="">
        <text>Continue</text>
      </ContentNode>
      <subNodes>
        <ContentNode id="3" orderNum="1" linkTo="0" type="npc" name="Cleric">
          <text>How may we help you?</text>
        </ContentNode>
        <subNodes>
          <ContentNode id="4" orderNum="4" linkTo="0" type="pc" name="">
            <text>What is the denomination of this church?</text>
          </ContentNode>
          <ContentNode id="5" orderNum="3" linkTo="0" type="pc" name="">
            <text>Who are generally members of this church?</text>
          </ContentNode>
          <ContentNode id="6" orderNum="2" linkTo="0" type="pc" name="">
            <text>I'm looking for a weapon that is stored here</text>
          </ContentNode>
          <ContentNode id="7" orderNum="1" linkTo="0" type="pc" name="">
            <text>Just checking out the place. Good-bye.</text>
            <subNodes>
              <ContentNode id="8" orderNum="1" linkTo="0" type="npc" name="Cleric">
                <text>May the Sapphire's glow lie within you!</text>
              </ContentNode>
            </subNodes>
          </ContentNode>
        </subNodes>
      </subNodes>
    </subNodes>
  </subNodes>
</Conversation>

Now to spell it out:

Conversation doesn’t really have a purpose right now, but it will if I ever decide to have 2 or more conversations in the same XML file.

Each conversation is an object of type ContentNode. It looks like this:

public class ContentNode
{
    public NodeType type;
    public string text, name;
    public int idNum, orderNum, linkTo;
    public List<ContentNode> subNodes;
    public ContentNode()
    {
        subNodes = new List<ContentNode>();
        text = "";
        name = "";
    }
}

As you can see, the subNodes elements correspond with the List objects. You’ll also see that there are many attributes for the ContentNode element. The id is just a number to keep track of all the lines, and the orderNum is supposed to help my code decide how many response choices the player has. All the elements that are type ‘pc’ appear only in the buttons below my message box, while the NPC’s lines appear in the message box itself.

Another reason why I’m trying to find an algorithm for this is that, depending on the size of these conversations, I could end up with displaying strings that look like this:

conversation.subNodes[0].subNodes[4]. … .subNodes[3].text;

Really long, yes. So can anyone help? It looks like I’m asking for code… and in some ways I am :stuck_out_tongue: but I’d appreciate any pointers on writing a good algorithm that will help me solve this problem, be it other online resources that I haven’t found or just your experience (if you’ve made an XML dialog tree before)

2

I think maybe there’s a better way to organize this data. NPC/PC dialogs are best structured as a collection of nodes where the NPC is talking and then with 1 or more possible player responses. The player response has a string that the player “says” but the important part is the response - typically a jump to a different Node.

These arn’t hierarchical as such - all the nodes can be stored flat in your resource file with some kind of tag indicating the starting node for the conversation.

(not in any particular language)

class PlayerResponseNode
{
    string PlayerText;
    int JumpTo;
    // other action tags as needed
}

class DialogNode
{
    int JumpTag;

    // This allows more than one NPC to 
    // participate in the dialog. 
    string SpeakingNPC; 
    string NPCText;
    PlayerResponseNode[] Responses;
}

// This is what you parse from the data file
class Dialog
{
    DialogNode StartNode;
    Dictionary(JumpTag, DialogNode);
}

Its really not that different from the design you have there. The key difference is flattening it out and navigating exclusively by the Jump Tags.

3

I think I understand now. By using the tag, I can just bring up each message with its respective responses. Is there a way to iterate through all the message and responses through a for or while loop, or do I need to manually code in each message with responses?

4

Can you clarify that? I’m not sure what you mean.

5

Basically, here is what I’d like to avoid:

Display message(tag)
if (Response1 is chosen)
{
  Display NEW message(tag)
  if (NEW Response1 is chosen)
  {
    Display NEW new message(tag)
    if (NEW new Response1 is chosen)
    {
      Display NEW new new message(tag)
      etc...
    }
    if (NEW new Response2 is chosen)
    {
      etc...
    }
    if (NEW new Response3 is chosen)
    {
      etc...
    }
  }
}

if (Response3 is chosen)
{
  etc.
}

if (Response4 is chosen)
{
  etc.
}

if (Response5 is chosen)
{
  etc.
}

Instead, I want something streamlined and iterative, which was the purpose of using XML in the first place.

6

I solved it. By adding more “tags” to the Attributes in the XML file, I can give my XML Parser more information, and it will be able to easily take the messages and responses it needs to show.

To put it more clearly, I put the possible responses (up to 4) in an array, and each button matches to the index in the responses array. The index is what holds the tag for the next message.

Observe:

if (MessageBoxScript.getCont() >= 0  !speaking)
        {
            id = responses[MessageBoxScript.getCont()];
            MessageBoxScript.ResetButton();
            speaking = true;
        }

id is the message tag, responses[ ] is the array, and MessageBoxScript.getCont() returns a number between 0 and 3 [inclusive]. The next message is the one that has that tag. Simple as that.

Solution for anyone else who has this problem: Add as much info to your XML file as possible. It’ll make arranging your messages much easier.

Thanks for your help.