Behavior Tree Prototype: Part 2

Part Two: Who Is Your Daddy, And What Does He Do?
(part one here: )

Library here at GitHub

Who is your Dady?

So, we have this Behavior Tree (BT), but what the heck am I supposed to do with the dang thing? When you order the BT to "behave" you initiate a search through the tree with each node and leaf being evaluated until a specific behavior code is reached during the end result of the search (you do not define this search, the BT does it by itself). So, to use a BT all you want is a tree that will give you some evaluation as to whether it accomplished something or not. The meanings of Failure, Success, and Running, are very abstract and if anything are just a bubbled up measure of the overall tree's "evaluation state". What those return codes mean to YOU the developer is all dependent on what your BT ends up doing. Failure could mean it just didnt act this turn, or it could mean that your entity is dead, or many other things, same as success or running. One way to treat it is at a very high level over which your AI system decides, do I move on to the next AI construct, or not? You can also completely ignore it as well. Additionally, the tree will usually evaluate a single branch to a leaf in one evaluation cycle, starting with the "left-most" branch of the major branch selected first. The next evaluation will result in the next over, then the next, etc. Whether or not this is considered efficient, is not important at this point, but it is important that non-parallel branches will take several evaluation cycles to resolve while a parallel branch will resolve them all in one go. However, the modular structure of the BT could support even further incremental evaluations with a couple modifications to further break up the evaluation if you wanted to.

What does he do?

OK, so that is how the basic BT operates, now what can it do currently? Like i said in Part 1, it implements the following basic constructs:

• Behavior Return Codes (currently an enumerator, will likely change to a short constant, but supports Success, Failure, and Running)
  
• A Behavior "Root"
  
• A Root Selector (selects between major branches on the behavior tree i.e., behavior states)
  
• Selector (OR behaviors)
  
• Sequence (AND behaviors)
  
• Random Selector
  
• ParallelSequence (AND behavior in one tree evaluation)
  
• Inverter
  
• Conditional
  
• Action

Composites:

Sequence is a BehaviorComponent (BC) that wants all their behaviors to return true, or they say they are running or they say they have failed since one of their behaviors returned failure. ParallelSequence is a special case which attempts to resolve its evaluation during one behavior call.

NOTE: this code is in c#, so it is important to note that things like pointers are done behind the scenes. Following code samples will be offered as links to GitHub.

public class Sequence : BehaviorComponent
	{
		protected BehaviorComponent[] s_Behaviors;
		private short sequence = 0;
		private short seqLength = 0;
	  
		/// <summary>
		/// Performs the given behavior components sequentially
		/// Performs an AND-Like behavior and will perform each successive component
		/// -Returns Success if all behavior components return Success
		/// -Returns Running if an individual behavior component returns Success or Running
		/// -Returns Failure if a behavior components returns Failure or an error is encountered
		/// </summary>
		/// <param name="behaviors">one to many behavior components</param>
		public Sequence(params BehaviorComponent[] behaviors)
		{
			s_Behaviors = behaviors;
			seqLength = (short) s_Behaviors.Length;
		}
		/// <summary>
		/// performs the given behavior
		/// </summary>
		/// <returns>the behaviors return code</returns>
		public override BehaviorReturnCode Behave()
		{
			//while you can go through them, do so
			while (sequence < seqLength)
			{
				try
				{
					switch (s_Behaviors[sequence].Behave())
					{
						case BehaviorReturnCode.Failure:
							sequence = 0;
							ReturnCode = BehaviorReturnCode.Failure;
							return ReturnCode;
						case BehaviorReturnCode.Success:
							sequence++;
							ReturnCode = BehaviorReturnCode.Running;
							return ReturnCode;
						case BehaviorReturnCode.Running:
							ReturnCode = BehaviorReturnCode.Running;
							return ReturnCode;
					}
				}
				catch (Exception)
				{
					sequence = 0;
					ReturnCode = BehaviorReturnCode.Failure;
					return ReturnCode;
				}
			}
			sequence = 0;
			ReturnCode = BehaviorReturnCode.Success;
			return ReturnCode;
		}
	}

note: ReturnCode is an inherited property, so setting it allows a BehaviorComponent, or in this case Sequence, to remember which evaluation they had.

Ex) in this evaluation, it would attempt to perform the action of doThis, and if successful, it would attemp to perform action doThat, if it was successful, it would return succes. If either was failure, it would return failure. if doThis had failed initially, i would immediately return failure. if either returns running, it returns running.

Sequence seq = new Sequence(new BehaviorAction(doThis), new BehaviorAction(doThat));
seq.Behave();

Selector is a BC that wants one of their behaviors to return true, and evaluate each in turn "failing over" on Failure to the next and run them. Selectors are running the current one being evaluated is running and they fail if all return Failure. RootSelector is just a special case Selector designed only for the root so it can choose a major branch. if the one currently evaluated returns running, it returns running.

Code here.

Ex) in this evaluation, it would attempt do perform action doThis, and if successful, would return success. if it failed, it would attemp to perform doThat. If both failed, it would return failure.

Selector sel = new Selector(new BehaviorAction(doThis),new BehaviorAction(doThat));
sel.Behave();

RandomSelector, is just that, it is a BC that randomly selects one of its branches and evaluates it and returns the result. I can also forsee the want for something like a RandomSequence, in which it choses all the branches randomly untill it has evaluated them all, as well as parallel variations.

Code here.

Ex) in this example, random selector could do either doThis or doThat, but will chose one of them and report its success, failure, or running.

RandomSelector rSel = new RandomSelector (new BehaviorAction(doThis),new BehaviorAction(doThat));
rSel.Behave();

Decorators:

Decorators are BCs that encapsulate leaves or nodes to modify their return codes in a predictable way. They can be things like loops, counters, filters, inverters, etc. Currently I have only implemented the Inverter decorator. Inverters do just what their name implies, invert the return code they receive; making success a failure, failure a success, but leaving running untouched since it is neutral.

Code here.

Ex) in this example, inverter returns success if doThis was a failure and returns failure if doThis was a success. it returns running if doThis is running.

Inverter inv = new Inverter(new BehaviorAction(doThis));
inv.Behave();

Actions:

Actions are BCs that are on the leaf portions of BTs. Their job is to specifically perform some sort of action, and report whether it succeeded or not. Actions as defined in this library will execute any method with a BehaviorReturnCode return signature.

Code here.

Ex) in this example, behavior action returns the same thing that doThis does.

BehaviorAction act = new BehaviorAction(doThis);
act.Behave();

Conditionals:

Conditionals are a special type of Action, in which they will only execute a method with a boolean return signature. They also will NEVER return a running state.

Code here.

Ex) in this example, conditional returns the same thing that isThisTrueOrFalse reutnrs. it will never return running.

Conditional cond = new Conditional(isThisTrueOrFalse);
cond.Behave();

Root:

So, who the heck initiates this controlled chaos? The root node, thats who. The root node essentially kicks-off the evaluation chain. All the root cares about, all it is ever interested in, is the RootSelector. Additionally, it does not inherit from the BehaviorComponent class, so just like a highlander, There Can Be Only One! One per BT that is.

Code here.

Ex) in this example, shows the culmination of everything into a simple behavior tree. NOTE: the first argument to RootSelector must be an integer returning method which will return an integer representing 0-n where n = 0 to # of branches - 1. In this case 0 to 2.

//setup actions
BehaviorAction doThisAction = new BehaviorAction(doThis);
BehaviorAction doThatAction = new BehaviorAction(doThat);

//setup conditional
Conditional cond = new Conditional(isThisTrueOrFalse);

//setup inverter
Inverter invThisAction = new Inverter(doThisAction);
Inverter invCond = new Inverter(cond);

//setup sequnce and select
Sequence branchA = new Sequence(invCond,doThisAction,doThatAction);
Selector branchB = new Selector(cond,invThisAction,doThatAction);
RandomSelector branchC= new RandomSelector(doThisAction,doThatAction);

//setup root selector
RootSelector rootSel = new RootSelector(getState, branchA, branchB, branchC);

//setup root
Behavior behavior = new Behavior(rootSel);

//order root to behave
behavior.Behave();

public int getState()
{
	//return integer here
}

public BehaviorReturnCode doThis()
{
	//do this
}

public BehaviorReturnCode doThat()
{
//do that
}

public bool isThisTrueOrFalse()
{
	//return true or false
}

Anywho, that covers this journal entry. I'll make additional journal parts when I make further updates/progress in its evolution and use.

EDIT: added culmination example.
EDIT2: it would also be possible to inherit from components like BehaviorActions and Conditionals and implement a custome Behave method to remove the need for method delegates... i would suggest this as being more flexible and the desired usage.
EDIT3: had example text for sequence and selector reversed... fixed now