Scripting, Part 6: Behaviour Tree Builder - Interpreter

In the last post, I designed a simple markup language for behaviour trees, outlining all available commands. In this post, we're implementing an interpreter for that language.

Behaviour trees in code

Behaviour trees are the kind of thing lots of libraries are programmed for, but I'd rather not make this post implementation dependent, so I'll assume a simple, generic API: All types of nodes are subclasses of BehaviourTreeNode, and their constructors either take an integer as an argument (leaf nodes), a single BehaviourTreeNode, or an IEnumerable<BehaviouTreeNode> collection, depending on the type of node.

The respective classes are Action, RunBehaviour, Sequence, Selector, Inverter, Succeeder, Repeater and RepeatUntilFail.

I'm not making any other assumptions about how they are all implemented, but I don't have to, since a script is only supposed to create a behaviour tree, not use one.

The interpreter

To build the interpreter, we subclass the BaseInterpreter class we developed in the previous posts (as a reminder, the source code can be found here). To do that, we need to implement the abstract method InitInsn, which initializes the instruction set, i.e. the two arrays of delegates. We can't actually do that yet - we haven't programmed any methods to add to the instruction set yet - so let's see what else needs to be done.
As explained in the previous post, we need to add a stack of BehaviourTreeNode to keep track of previously defined nodes. For convenience, we'll also add a method Run that executes the entire byte code passed to it and returns the generated behaviour tree:

 Stack<BehaviouTreeNode> defined;  
 bool running = false;  
 
 public BehaviourTreeNode Run(byte[] code)  
 {  
   InitScript();  
   running = true;  
   while (running)  
     NextCommand();  
   return defined.Pop();  
 }

Now we need a way to break out of this loop. Let's implement the End command first:

 private void Cmd00_End()  
 {  
   running = false;
 }  
   
 private string Cmd00_Decompile()  
 {  
   return "End";
 }

With that, we can get to the more interesting commands. Let's start with the Action command:

 private void Cmd01_Action()  
 {  
   defined.Push(new Action(DataBus.ReadInt32()));
 }  
   
 private string Cmd01_Decompile()  
 {  
   int id = DataBus.ReadInt32();
   return String.Format("Action {0}", id);
 }

The RunBehaviour command, of course, is analogous to that. To create the internal nodes, we need to pop values off the stack:

 private void Cmd03_Inverter()  
 {  
   defined.Push(new Inverter(defined.Pop()));
 }
 
 // ...
 
 private void Cmd07_Sequence()
 {
   BehaviourTreeNode[] children = new BehaviourTreeNode[DataBus.ReadInt32()];
   for (int i = children.Length; i >= 0; i--)
     children[i] = defined.Pop();
   defined.Push(new Sequence(children));
 }

Note that, in the second method, the nodes are added to the temporary array in reverse order. This is necessary because, when a tree is converted to postfix notation (like our script code), nodes appear left-to-right, but when popped off the stack appear right-to-left.

With all commands implemented, we can now initialize the instruction set:

 public void InitInsn()  
 {  
   Execute = new Action[] {
     Cmd00_End, Cmd01_Action, Cmd02_RunBehaviour,
     Cmd03_Inverter, Cmd04_Succeeder, Cmd05_Repeater,
     Cmd06_RepeatUntilFail, Cmd07_Sequence, Cmd08_Selector };
   Decompile = new Func<string>[] {
     Cmd00_Decompile, Cmd01_Decompile, Cmd02_Decompile,
     Cmd03_Decompile, Cmd04_Decompile, Cmd05_Decompile,
     Cmd06_Decompile, Cmd07_Decompile, Cmd08_Decompile };
 }  

And that's it! As you can see, I left out some of the necessary methods, but they just mirror the ones I explained here. If you want to see all the code for this part, see this paste.

I hope having an example of a concrete interpreter at hand makes the whole process of designing and implementing a language more accessible. In the next post, I'll finally talk about compilers - how they work, when you should or should not use one, and what alternatives there are.