1 Replies - 812 Views - Last Post: 29 July 2010 - 05:22 PM Rate Topic: -----

#1 Emzee   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 16
  • Joined: 11-December 09

Traversing a tree based on user input

Posted 25 July 2010 - 09:35 PM

I've written a nifty program that will convert my XML documents to trees of objects (more specifically, each object is a dialog statement - yes, this is a conversation tree for a game). With the XML parsing done, I need a way for the program to move itself through the different nodes. I know what to do if I need to display the nodes all at once, but I need only one node at a time to be displayed, and the node displayed needs to be based on what the user selects.

I should explicitly point out that, unlike traditional traversal, not all nodes will be shown/used here. With nodes being "skipped" essentially, this confuses me a little.

Here is pseudo-code for the method:
Enter from the root node and traverse through the root's children
if the node is an 'NPC' node then display it's text on the screen
Display the strings of all the 'NPC' node's children (the 'PC' nodes)
whichever 'PC' node is selected, traverse through it and proceed to the next 'NPC' node that is a child of that 'PC' node.
if the node is an 'NPC' node then display it's text on the screen...



What's really that's stopping me is that I don't know whether to use recursion or basic iteration. That's something I need to know before I jump into coding. Sorry that pseudo-code is all I have right now, but I hope someone will be willing to point me in the right direction.

This post has been edited by Emzee: 25 July 2010 - 09:39 PM


Is This A Good Question/Topic? 0
  • +

Replies To: Traversing a tree based on user input

#2 Emzee   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 16
  • Joined: 11-December 09

Re: Traversing a tree based on user input

Posted 29 July 2010 - 05:22 PM

View PostEmzee, on 25 July 2010 - 08:35 PM, said:

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<ContentNode> 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 :P 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)

Can anyone help?

Revised post is attached (it's a shame that it had to come to our editing rights taken away, just cause of some selfish members .. :( )

This post has been edited by Emzee: 29 July 2010 - 05:22 PM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1