How can I implement dialog trees into my game?

What is the best way to implement a dialog tree system into my game where a NPC would talk to the Player and give them different sets of responses, some which may only appear when the Player has an item or a previous event has occurred.

From game development Bryan Denny

• I would look into a embedding a scripting language like lua or ruby and coding dialog interactions in that.

  Thus a dialog script could look like:

  switch showDialog "Why don't you just leave me along!", "Okay", "But I found your dog!"
      case 1:
          showDialog "And stay gone!"
      case 2:
          if playerHasObject "dog"
              showDialog "Thank you!"
          else
              showDialog "Liar!"
  

  This also works well for coding AI and other simple things that are useful to tweak during run time. You can even add an editor built into your application that can be invoked when running in debug (or as an Easter Egg).

  Iain : I prefer this to straight XML as you can add logic. But I would say the text itself should probably be in XML rather than in the code. (easier to edit, localise to other languages etc).

  Nailer : if you need localization/easier edit you can wrap the text in a function that writes the enclosed text to a separate file like the tr(QString) function/macro in Qt. http://pepper.troll.no/s60prereleases/doc/linguist-hellotr.html

  lathomas64 : whats to stop you from using attributes or extra tags in the xml to simulate the logic here?
  From BarrettJ

• You can take a look at the Dlgedit tool of the Open Source RPG engine Adonthell. It's very advanced and should contain everything you need (including sources ;))

  From Koonsolo

• Data drive your characters with LUA scripts or even XML files. When you interact with an NPC, grab the file that is attached to it, read it in, adjust for any game variables that may have been triggered, and product the valid response.

  The biggest gain from doing it this way is you can easily go in and manipulate the dialog, add new characters, etc. You also avoid mucking up your code base with special logic in handling each and every case.

  RCIX : It's Lua, not LUA. :)

  David McGraw : I did it just for you, man. ;)
  From David McGraw

• Dialog Trees should be done using XML. You store the conditions for the responses and the response in nested trees with a reference to a script file if you need to do something more complex.

  You should keep the scripts and dialog separate especially if you are putting together an RPG which has a metric ton worth of conversations. You can then use a library like simpleXML to read the XML file.

  There's a similar question over on SO with an example: http://stackoverflow.com/questions/372915/game-logic-in-xml-files

  AttackingHobo : +1 for XML. Much better than embedding in the code itself, allows for changes without recompiling the code, and is a standard format that can be read by some powerful editors.

  Ricket : +1 for the link to the excellent SO question that I hadn't seen before. I love the example in that question!

  Ipsquiggle : XML is just a format (and, IMO, a bad one). Really what this answer says is, "Create a small domain language that contains basic logic and flows, but primarily consists of your dialogue, and parse it." In that general way, I agree with this answer.

  GamingHorror : Exactly, XML is just the container, you can just as well (and definetely more humand-readable and human-editable) implement this using Lua or other scripting languages.

  BigSandwich : XML is expensive to parse and takes up A LOT of memory. It's fine to use it as a storage format, but I'd write utility that converts the dialog trees to a binary format that is used at runtime. If your on a PC and don't care about your memory usage it might be fine, but on any other platform the memory cost will hose you.

  Lo'oris : -1 for XML. I agree with @Ipsquiggle and @BigSandwich

  Firas Assaad : The main idea is to separate dialogue data from game code, and using some [DSL](http://en.wikipedia.org/wiki/Domain-specific_language) or XML files are both valid approaches. When I asked that question on SO I wanted to make a GUI dialogue editor, and its easier to generate XML files than code. Additionally, I have a fairly complex dialogue system based on priorities, conditions, perquisite knowledge, and other factors that map nicely to attribute representation, but other games might have much simpler dialogue trees where XML is an overkill.
  From Fox

• In the game Stendhal we use a finite state machine to implement NPCs.

  The following diagram shows a little example from the how to write quests tutorial.

  

  At the beginning the NPC is in state IDEL and may be walking around. A player can start a conversation by saying "hi" and the NPC will go to state ATTENDING. In this state it answers to questions about his "job" and offers some game "help". The player might ask for a quest and the NPC will go to state QUEST_OFFERED waiting for the player to accept ("yes") or decline ("no") it.

  We have defined a set of conditions that can be attached to transitions. For example completing a quest may only be possible if a PlayerHasItemWithHimCondition is met.

  After a transition was executed the NPC may say some text and/or execute an action. Similar to the conditions we have defined a reusable set of actions like EquipItemAction which is used to give a quest reward to a player.

  Multiple conditions can be combined using AndCondition, OrCondition and NotCondition. Usually there is a number of actions to be done on quest completion, so there is a MultipleActions class as well.

  While the actual implementation in Stendhal suffers from not being translatable in other (human) languages easily, I think the general concept is good.

  From nhnb

• If you use XML, make sure you build a small tool to edit the XML file. You'll go crazy otherwise.

  Lo'oris : If there already isn't a tool to edit it, then it is pointless to use it in the first place: create your own format as well!
  From zooropa

• If your dialogs are of any complexity, the most important thing you'll need for dialog implementation is a way to understand the complexity of your interaction. I recommend a Node editor of some kind to visualize this, though I don't have any good open systems to recommend.

  From Aaron Brady

• I think , that You use your own script language for directing these type of game(if not, You should).Then expand your script for dialogs handling too.
  You can work with other game variables during creation of dialogs logic. Game engines are like Lego. You programmed only bricks and script uses them. It does not matter if You make some script interpreter or compiler. But script is always useful.

  From samboush

• I think for adding in translations, you could still use XML for the logic as stated above. When you're getting into that type of complexity you should write your own dialogue tool. Your dialogue text would get stored as a key to a database that you could swap out depending on the language you'd want to display.

  For example you could have:

  <dialogue id="101" condition="!npc.carsFixed">
    <message>Localize.FixMyCar</message>
    <choices>
      <choice condition="hero.carFixingSkill > 5" priority="7" id="Localize.Sure">
        <command>hero.carFixingSkills += 1</command>
        <command>npc.carFixed = true</command>
        <command>hero.playSmokeAnimation()</command>
        <command>nextDialogue = 104</command>
      </choice>
      <choice condition="hero.carFixingSkill <= 5" id="Localize.CantFix">
        <command>nextDialogue = 105</command>
      </choice>
      <choice id="Localize.FixYourself">
        <command>npc.likesHero -= 1</command>
      </choice>
    </choices>
  </dialogue>
  

  You would then have the quest text renderer replace "Localize.FixMyCar" with the appropriately translated text.

  Your tool would display what the player would see in a selectable language alongside the editable raw XML.

  Similarly you could use something like this from the example you referenced:

  npc.add(ConversationStates.ATTENDING,
          ConversationPhrases.QUEST_MESSAGES, 
          null,
          ConversationStates.QUEST_OFFERED, 
          Localization[ "BringMeABeer" ],
          null);
  

  If your keys are descriptive enough not having the complete text shouldn't be an issue.

  Something like this could be useful as well:

  Localization[ "<Location>.<NPC_name>.<Dialogue_text_key>" ];
  

  From toddw