AI Behavior Trees for Torque

Behavior trees offer a fast and scalable solution when dealing with game AI. This resource is a parser that lets you parse behavior trees created in XML and assign them to any object exposed to TorqueScript.

Recently I've been working on malfunctioning AI scripts in our game, and most of my frustration stemmed from logic and code not being separated. I really did not want to have to rewrite scripts and code and debug whenever I wanted to change the behavior of an AI agent.

After watching Alex J. Champanard's excellent presentation Behavior Trees For Next-Gen Game AI I decided to give this approach a try and to first of all create a simple parser that will be able to handle calling AI functions and evaluate results according to the rules explained by Alex.

The basic idea is simple. Consider the following XML file:

<?xml version="1.0" encoding="UTF-8"?>

<deceptiveai id="default">

	<sequence id="main">

		<assert condition="!%this.dcIsDead()" />
		<assert condition="!%this.dcIsOutOfScope()" />
		<assert condition="!%this.dcIsStunned()" />

		<selector id="actions">

			<!-- FLEE -->
			<selector id="flee">
				<assert condition="%this.dcMustFlee()" />
				<assert condition="!%this.dcMoveDestinationSet()" />
				<task call="%this.dcFlee()" />
			</selector>
			
			<!-- NEED HEALING -->
			<selector id="needheal">
				<assert condition="%this.dcMustHeal()" />
				<selector id="healself">
					<sequence id="healself-action">
						<assert condition="%this.dcHasHealthReplenisher()" />
						<task call="%this.dcHealSelf()" />
						<task call="%this.dcPlayAnimation('cast', 'attack')" />
					</sequence>
					<sequence id="askforhealing">
						<assert condition="%this.dcCanCollaborate()" />
						<task call="%this.dcRequestAllyHeal()" />
						<task call="%this.dcPlayAnimation('cast', 'attack')" />
					</sequence>
				</selector>
			</selector>

			<!-- ALLY REQUESTS HEALING -->
			<selector id="healally">
				<assert condition="%this.dcCanCollaborate()" />
				<assert condition="%this.dcCanHealAllies()" />
				<assert condition="%this.dcIsAllyHealRequested()" />
				<selector id="healally-action">
					<task call="%this.dcHealAlly()" />
					<sequence id="manageHealDistance">
						<task call="%this.dcManageHealDistance()" />
					</sequence>
				</selector>
			</selector>

			<!-- ATTACK -->
			<selector id="attack">
				<assert condition="%this.dcIsEnemyVisible()" />
				<selector id="attack-action">
					<sequence id="useWeaponOrSkill">
						<task call="%this.dcUseWeaponOrSkill()" />
					</sequence>
					<selector id="manageTargetDistance">
						<sequence id="targetTooClose">
							<assert condition="%this.dcIsTargetTooClose()" />
							<task call="%this.dcMoveAwayFromTarget()" />
						</sequence>
						<sequence id="targetTooFar">
							<assert condition="%this.dcIsTargetTooFar()" />
							<sequence id="targetFleeing">
								<assert condition="!%this.dcIsTargetFleeing()" />
								<task call="%this.dcMoveCloserToTarget()" />
							</sequence>
						</sequence>
					</selector>
				</selector>
			</selector>

			<!-- PATROL -->
			<sequence id="patrol">
				<assert condition="!%this.dcMoveDestinationSet()" />
				<task call="%this.dcFindRandomDestination()" />
			</sequence>

		</selector>

	</sequence>

</deceptiveai>

Ok, that might not seem that simple at first, but take a look at it anyway. Not so much at the example functions it has, but more at the structure.

What this resource does is it parses such an AI behavior XML file and executes the right commands according to the file structure and the results received from the function calls. It does not actually have any of the AI functions, because they are way too game-specific, but it gives you the option to not have to write logic - more like "design" it instead.

A test run of this behavior XML would produce the following output in our game:

DECEPTIVE?

I named this Deceptive in hopes of being able to further refine this resource in the future and maybe share or sell complex ai behaviors and supporting functions. Still even without those, I believe that having logic separated from code is a win by itself.

Deceptive has 4 basic node types that can be used to create a behavior tree. All files should have a "deceptiveai" root node which encapsulates all other nodes. Execution begins with a direct child node of the "deceptiveai" node called ("id" attribute) "main". So this is where your execution begins. This MAIN node can either be a selector or a sequence. But here is the complete list of possible node types that can be the children of the Main node:

SEQUENCE

A holder of tasks, selectors and sequences in order of priority executed one after the other in succession. All children are evaluated until a child fails or all children are successful (success).

SELECTOR

A holder of tasks, selectors and sequences in order of priority executed one after the other in succession. All children are evaluated until a child succeeds (success) or all children fail (failure).

ASSERT

A task that returns success if its condition is met. Asserts are a lightweight and quick way to bail out of a sequence early on if its conditions are not met. When an assert fails, the parent instantly stops executing its children and reports failure regardless of the node type (sequence or selector) the parent is.
PARAMS: * condition (required) The condition that is asserted. if the condition evaluates to true then the assert succeeds, otherwise it fails and also fails its parent.

TASK

An action that calls a function when the task is executed. The return value of the function will be used to evaluate the return value of the parent of the node.
PARAMS: * call (required) The function call that this task must execute.

Now to get this working for you, you must first make a few changes to your console/SimXMLDocument.cpp and SimXMLDocument.h files. These are Torque 3D 1.1 directory and file names - other Torque products might have different names for these files, but as far as I know, this class is in every Torque product.

Torque uses tinyxml to create and parse XML documents. SimXMLDocument exposes a few of the possibilities that tinyxml provides, but not enough. We'll fix that:

Replace the following two console methods with these:

DefineEngineMethod( SimXMLDocument, pushFirstChildElement, bool, ( const char* name ), (""),
   "@brief Push the first child Element with the given name onto the stack, making it the current Element.nn"

   "@param name Optional. String containing name of the child Element.n"
   "@return True if the Element was found and made the current one.n"

   "@tsexamplen"
   "// Using the following test.xml file as an example:n"
   "// <?xml version="1.0" encoding="utf-8" standalone="yes" ?>n"
   "// <NewElement>Some text</NewElement>nn"

   "// Load in the filen"
   "%x = new SimXMLDocument();n"
   "%x.loadFile("test.xml");nn"

   "// Make the first Element the current onen"
   "%x.pushFirstChildElement("NewElement");nn"

   "// Store the current Element's text ('Some text' in this example)n"
   "// into 'result'n"
   "%result = %x.getText();n"
   "echo( %result );n"
   "@endtsexamplenn")
{
   String strName(name);
   if (strName == String::EmptyString)
      return object->pushFirstChildElement();
   return object->pushFirstChildElement( name );
}

DefineEngineMethod( SimXMLDocument, nextSiblingElement, bool, ( const char* name ), (""),
   "@brief Put the next sibling Element with the given name on the stack, making it the current one.nn"
   "@param name String containing name of the next sibling."
   "@return True if the Element was found and made the current one.n")
{
   String strName(name);
   if (strName == String::EmptyString)
      return object->nextSiblingElement();
   return object->nextSiblingElement( name );
}

Now these allow us to not have to pass a node name as a parameter in which case any node will be found as the first child and next sibling.

Now add the following at the end of console/SimXMLDocument.cpp:

// -----------------------------------------------------------------------------
// Empties the node stack to move the element pointer to the init position
// -----------------------------------------------------------------------------
void SimXMLDocument::top(void)
{
   m_paNode.clear();
   m_CurrentAttribute = 0;
}

DefineEngineMethod( SimXMLDocument, top, void, (),,
   "@brief Set the node pointer to its initial state.nn"
   
   "Repositions the current element pointer to the top of the documentnn")
{
   object->top();
}

// -----------------------------------------------------------------------------
// Get true if first child element was successfully pushed onto stack.
// -----------------------------------------------------------------------------
bool SimXMLDocument::pushFirstChildElement()
{
   // Clear the current attribute pointer
   m_CurrentAttribute = 0;

   // Push the first element found under the current element of the given name
   TiXmlElement* pElement;
   if(!m_paNode.empty())
   {
      const int iLastElement = m_paNode.size() - 1;
      TiXmlElement* pNode = m_paNode[iLastElement];
      if(!pNode)
      {
         return false;
      }
      pElement = pNode->FirstChildElement();
   }
   else
   {
      if(!m_qDocument)
      {
         return false;
      }
      pElement = m_qDocument->FirstChildElement();
   }

   if(!pElement)
   {
      return false;
   }
   m_paNode.push_back(pElement);
   return true;
}

// -----------------------------------------------------------------------------
// Convert top stack element into its next sibling element.
// -----------------------------------------------------------------------------
bool SimXMLDocument::nextSiblingElement()
{
   // Clear the current attribute pointer
   m_CurrentAttribute = 0;

   // Attempt to find the next sibling element
   if(m_paNode.empty())
   {
      return false;
   }
   const int iLastElement = m_paNode.size() - 1;
   TiXmlElement*& pElement = m_paNode[iLastElement];
   if(!pElement)
   {
      return false;
   }

   pElement = pElement->NextSiblingElement();
   if(!pElement)
   {
      return false;
   }

   return true;
}

// -----------------------------------------------------------------------------
// Get the node name
// -----------------------------------------------------------------------------
const char* SimXMLDocument::getNodeName()
{
   if(m_paNode.empty())
   {
      return StringTable->insert("");
   }
   const int iLastElement = m_paNode.size() - 1;
   TiXmlElement* pNode = m_paNode[iLastElement];
   if(!pNode)
   {
      return StringTable->insert("");
   }

   return pNode->Value();
}

DefineEngineMethod( SimXMLDocument, getNodeName, const char*, ( ),,
   "@brief Get the node name from the current Element on the stack.nn"
   "@return The node name if found.  Otherwise returns an empty string.n")
{
   return object->getNodeName();
}

Now on to console/SimXMLDocument.h - add these as public methods:

void top(void);
      bool pushFirstChildElement();
      bool nextSiblingElement();
      const char* getNodeName();

That should be all the engine changes.

Now, get the script files from http://pub.bitgap.com/code/deceptive_aibehaviortree.zip and extract the contents into, scripts/server/ai/deceptive. If you put it some place else, change $DeceptiveAI::BehaviorXmlDir in main.cs.

Be sure to exec main.cs in your scriptExec.cs - it should take care of exec'ing other files.

Check out test.cs to see a really simple example on how to execute a tree defined in behaviors/default.xml (not present in this example, you'll need to write your own xmls). The fun part is - it gets executed for a ScriptObject in the example. See, behavior trees can't only be used for AIPlayers or vehicles. You could use them in place of very complex game logic anywhere.

If you check my example XML above, you'll see that I'm doing calls such as %this.dcMustHeal()... That %this is the object that the DeceptiveAI class is assigned to. To assign the parsing ability and to parse a behavior xml tree, all you need to do is the following:

%ai = new AIPlayer() {
      class = "DeceptiveAI";
   };
   %ai.dcThink("default");

But as I said, that "AIPlayer" can be any class you want. That class assignment / inheritance is one beauty of TorqueScript. :)
I didn't write "of the few"! :)

Finally I'd like to say thanks to Daniel Buckmaster and his blog Behaviours grow on trees which I found a fascinating read and got me thinking about behavior trees in the first place.

I hope you will be able to make use of this resource, and as always, comments are more than welcome!
Thanks for reading,

--Konrad
www.bitgap.com

@konradkiss
KonradKiss @ GitHub
konradkiss.com