Re-using Planning Trees for Interactive Dialogue

Let's say we have a computer-controlled hero who needs to save a princess from us, the bad guy.  We have a whole toolkit to create obstacles for him and have used it extensively.  His AI (artifical intelligence) uses a planning tree to circumvent the obstacles as he encounters them.  But what if we want to ask the hero what he's doing in order to support better characterization?  What if we want to ask him why he's, say, cutting the tail off his own donkey?  Well, a planning tree is useful here as well.  First let's have a quick refresher on what one is.

For most actions available to said characters, the system knows a few work-arounds in case of failure.  Each of those work-arounds is itself an action that may succeed or fail.  So when our annoyingly persistant hero fails at his latest attempt to assail our castle, the system whispers some new things to try, either as alternatives or as a prelude to re-trying.  Some of those new things may also run into difficulty, starting a new cycle.  The system keeps track of all this in a "tree" of actions.  The following picture and example should make this clearer.

Diagram of a Planning Tree in action

The story thus far:  he demanded our princess but we were unimpressed, so now he's working on getting past our dutiful guard, who apparently has no sense of humor.  Sneaking past in the dead of night failed because our moat glows in the dark, but this morning he's approaching the guard again, this time wearing a disguise created by using a donkey's tail as a fake moustache.  

If the picture of the tree didn't make sense before, it might now.  Each action in the tree has a status attached:  untried, in progress, failed, or successful.  (For legibility, each node in the picture is color-coded per its status.)  When an action fails, it may first become in progress if the system can find some workarounds to add to the tree.  Otherwise, failed it shall be.  The ultimate goal is at the top, and the tree grows downward as far as it needs to.  Also, if the hero's disguise works we might use a fifth status, moot, to indicate he'll never need to try Bribe or Attack.  And this ends the refresher on what a planning tree is.

What a planning tree is good for in interactive narrative is in answering questions like "how", "why", "could", "could have", and similar.   If the hero's sidekick asks, "how will you bypass the drawbridge guard?", the possible answers, gameplay-wise, are the child nodes of that Bypass node: "Well Pedro, although I could always best him in singular combat, I might instead win him over with stories of my great exploits, or maybe share some of this fine ale with him, or, since he doesn't look too bright, just sneak past him when he isn't looking."  Similarly, a "why" question gets the parent node: "And why are we trying to bypass him, again, señor?"  "The princess, Pedro.  We have a princess to save." 

Inspecting the various status reveals the progression of time.  Untried actions are in the future, in progress actions are in the present, failed and successful actions are in the past.  Moot remembers what could have been.  When answering questions, the hero (and hence, the programmer) can use this information to conjugate the answer correctly:  will sneak, is sneaking, snuck, couldn't sneak, and could have snuck.  Used in interactive dialogue, this is one more tool to help the game creator prove that the fictional character actually has an understanding of gameplay events and possibilities, as opposed to the character following a pre-written script like a tail-less donkey -- or the gameplay being railroaded just for the story's sake.  "As you see, Pedro, we could have bribed or bashed him, but brains wins over brawn and brandy everytime."  

Games may use planning trees as part of their AI fairly regularly nowadays, but once a branch is used it's usually erased to conserve memory.   But if saved, interactive dialogue could and should put that history to good use, especially when we, the player, are an antagonist disguised as a sidekick named Pedro.