Conversation Trees
A conversation tree is a commonly used game mechanic in PC role-playing games. It involves nagivating a space of player and NPC responses. Underneath, they're really Finite State Machines. Such trees are most interesting when the choices made can affect the game state and are not just false choices, provided for flavor or information.
Simple Example
On the first mission in Deus Ex, when you confront the terrorist commander at the top of the Statue of Liberty, you are under orders to take him alive as he is wanted for questioning about the disposition of a shipment of vaccine. After a few lines of dialogue, the terrorist commander says "You're too late, it's on its way back to the people and you can't do a damn thing about it." The player is then presented with two options:
- Except send YOU back to the people -- in a body bag.
- Tell me about the shipment and I'll order the troops to pick you up as a prisoner, instead of a corpse.
Picking the first option takes you down a branch of the tree that results in violence. Picking the second option provides you with information and a less violent resolution.
Deeper Examples
The above example is fairly simple. There is only one choice, so the tree isn't very interesting. Conversation trees can have much more depth.
- Fallout had some of the most interesting conversation trees of any game I've played. In-game abilities affected what options were available in conversation, and there was even an ability, empathy, that would provide information about where the conversation might lead if you were to choose a particular branch. The conversations were a key part of that game - it was possible to accomplish a large number of goals just by talking to people properly.
- Star Control 2 also used these effectively. It was possible to change the fate of entire races by navigating conversation trees.
- Ultima Underworld, the first game in which I recall encountering conversation trees, used them to affect whether other people were hostile or friendly. Hostiles gave worse deals when bartering and were inclined towards violence. If you started to notice that you were angering an NPC with your responses you usually had time to placate them with future answers.
Vs. Keyword-Driven Conversations
With conversation trees, there is often little mystery as to the scope of the possibility space. It takes much more work to add a branch than it does for a player to try out that branch, so interested players can generally fully explore the entire tree. With keyword-style conversation systems, the player always has to consider the possibility that not every keyword has been tried. On the other hand, players know what they can and cannot express. They are not left wondering whether the NPC isn't responding because that NPC doesn't have anything to say on a particular subject or because the player isn't using the right keyword.
Notes:
"Conversation Tree" is something of a misnomer, since a tree generally implies a directed acyclic graph. Although most are acyclic, there are a few that aren't. "Conversation Tree" is the generally accepted term, however, so we're stuck with it. It sounds better than "Conversation FSM" anyway. | 
