Graal Forums - AI Behavior Trees

Graal Forums (https://forums.graalonline.com/forums/index.php)

- Code Gallery (https://forums.graalonline.com/forums/forumdisplay.php?f=179)

- - AI Behavior Trees (https://forums.graalonline.com/forums/showthread.php?t=134258419)

AI Behavior Trees

Warning: Please only use this if you know what it is about, it can easily kill your server. Stefan

Warning: This post is a little lengthy, but definitely worth the read. I summarized it as much as I could and have placed several links that can explain the concept better at the end of this post. I will continue working on improving my explanation of it's use.

Reasoning
Currently on Graal AI is made by either placing an old style NPC in the level editor or doing custom scripting a baddy, both of which have problems. The first option is outdated and should be deprecated; it's written in GS1 and does not work well. The second option would be writing a long script that's hard to debug and almost always winds up with more bugs than the built in baddies and is rarely any more advanced.

Over time I've done some studying into techniques used in the professional game development world and come across one being used more and more often, coming to the forefront after the release of Halo2. Behavior Trees.

Explanation
Behavior Trees are a method of creating AI Behaviors (how it acts and responds to the world around it) that is intended to allow the user to create them quickly and with a lot of control. This is done by allowing the user to essentially piece together reusable blocks of code. Essentially, all the actions an AI can do are split up into smaller, specific functions, and Behavior Trees are used to control the flow and execution of these functions. Also, when I say AI I mean Artificial Intelligence. This would be baddies, but can also be other NPCs such as ally characters.

The concept is simple; an AIs overall behavior is split up into nodes connected in a tree, much like a tree graph:
http://conkerjo.files.wordpress.com/...ng?w=244&h=244
Think of every circle, called nodes, in this image as a function. The white nodes are functions that call their children (nodes below them that they are linked to, as shown by a line here), orange nodes have no children and do the actual work. The white nodes are called composite nodes, and the orange nodes are called leaf nodes. For more information on tree structures you can read the wikipedia page.

Composite nodes are nodes that do not do any real work and are used to navigate down the tree. There are two types of composite nodes included: Sequences, which will execute all of their children in order until one fails (returns false); and Selectors which execute their children until one succeeds (returns true). All nodes must return true or false, this is one of the main concepts needed to navigate the tree.

http://files.aigamedev.com/i/2007/07/sequence.png
http://files.aigamedev.com/i/2007/07/selector.png

There are also Node Decorators, a concept similar to Function Decorators in languages like Python. Since the idea is that you should be able to create behaviors by piecing together reusable blocks of code, you may need to add slightly different behavior to a node without rewriting or changing the node functions code. This is done with Node Decorators. These are functions that alter the way a node is executed, such as a decorator that makes a node loop, or filters it's execution based on the value of a certain variable.

Example

PHP Code:


		
			
this.behavior = new TStaticVar();
this.behavior.join("ai-behaviortree");
// Initialize the tree, where the root (first) node is a Selector. It can also be a Sequence
this.behavior.rootSelector()
  // Search state
  .leaf("search", this)
    // Only execute this node if this.state == "idle"
    .decorator("filter", {this, "state", "idle"})
    .getParent() // Get the parent node, in this case the root node
  // Chase state
  .sequence()
    .decorator("filter", {this, "state", "chase"})
    // Find a path to the target, this.target
    .leaf("findPath", this.target).getParent()
    // Move to the target
    .leaf("move", this)
      // Loop this action through each point in the path (see some of the threads about A* Pathfinding)
      .decorator("loop", {this.path.size()})
      .getParent()
    .getParent()
  // Attack state
  .sequence()
    .decorator("filter", {this, "state", "attack"})
    .leaf("attack", this)
    // Macro for sleep(0.5)
    .macro("pause", 0.5)
    .getparent()
  // Dead state
  .sequence()
    .decorator("filter", {this, "state", "dead"})
    // Macro for setCharAni("dead", NULL)
    .macro("setCharAni", "dead")
    .getParent()
  ;

/*
 * This will execute the tree
 * Ideally this will be done in a timeout loop.
 * This is acceptable because the tree will keep executing until it's done
 * with the current action.
 */
this.behavior.behave();

This is a rather simple example but shows the basic syntax and usage (in reality, nodes should be broken up into more basic actions, though not too basic). Node functions should return true upon success and false upon failure. Ideally, node functions should be made before hand and collected into other classes to be joined to AI that need their use in their Behavior Tree. Over time I will release classes containing useful node functions.

Composite nodes, Leaf nodes, and Macros (macro for a built in function like echo() or ones built into the behavior tree implementation) all take exactly one argument. Because functions used in Behavior Trees are a special case it is acceptable because you can use an array for multiple arguments.

Further Info
These links can explain the concept of Behavior Trees and their use better than I can (also in case my post was tl;dr):

http://aigamedev.com/open/articles/bt-overview/
http://aigamedev.com/open/articles/sequence/
http://aigamedev.com/open/articles/selector/
http://aigamedev.com/open/articles/decorator/
http://www.gamasutra.com/gdc2005/fea.../isla_01.shtml
Three part video slideshow with audio commentary (most useful imo):

Included in this post is the 'ai-behaviortree' class and a class it relies upon: 'util_dict' which is a class for associative arrays.

Cool use of trees. Admittedly, I didn't really follow your post very well, but I am wondering if the efficiency could be improved by using other algorithms similar to Adelson-Velskii Landis trees (which automatically balance themselves to make sure one side of the tree is not longer than the opposite side of it), which would make searching for behaviors much faster. Do you know if that would be applicable in this situation? I'm sure there is some way it could be worked over to behave correctly.

Extending It's Usage
You may want to create new Node Decorators for your behavior trees. This is a bit more complicated than the rest of the behavior tree usage due to the fact that node decorators have to be dynamically nested while allowing an argument.

There are two important things you need to know. First off, decorator functions take one argument: the next function to be called. The actual argument to a node decorator (as specified in it's declaration, such as how many times to loop, what variable to filter, etc) is held in a dict (associative array) called this.decorators. To get this argument you use 'this.decorators.get("functionName");'. Second, in order to continue execution (calling either the next node decorator or the node function) you need to call 'callInner(func);' where func is the function argument to the decorator.

Here is an example (from the default loop function):

PHP Code:


		
			
function loop(func)

{

  // Get the loop arguments

  temp.args = this.decorators.get("loop");

  // Loop execution based on the argument

  for (temp.i=0; i<args[0]; i++)

  {

    // Call the node, and quit looping if it fails (returns false)

    if (!callInner(func))

      return false;

  }

  return true;

}

Quote:

Originally Posted by Tigairius (Post 1563258)

Behavior Trees by nature will most likely have unbalanced sides, and are not binary trees. Overall, searching down the tree is actually very simple, so it isn't slow at all.

I know my explanation isn't very good, I'm trying to make revisions to simplify it. :( I encourage people to look at some of the pages I linked to, especially the first four, as they are the simplest.

My brain, oh my god.

i wish i could understand this, but i'm just going to assume it's great work! Good Job Abjorn.

I improved the explanation in the original post and added a much better example script. I'm working on a prototype NPC to better show it's usage.

I am also planning a graphical editor for creating trees without making any actual code to further improve productivity for users. A lot of professional game developers use graphical designers for Behavior Trees so why not us? :)

I know it may be a difficult read, but I've done all I can to make it clear, especially with the additional links. But I believe learning to use this is well worth it. Think of it this way: you should be able to create more advanced baddies easier and more quickly, and custom tailor your baddies easily to whatever situation you need.

Interesting.

Would be cool if you also made an XML format + XSLT*, so you can convert it into the desired code, generating placeholders for functions that'll you'll have to write would be cool too but not needed.

Quote:

Originally Posted by fowlplay4 (Post 1563454)

XML format + XLST

brb, killing self

Quote:

Originally Posted by WhiteDragon (Post 1563455)

brb, killing self

How come? I found it pretty easy to use and think it would be easier to understand than functions and dot notation but to each his own I guess.

studying this stuff yet i dont understand a single thing u_u

Quote:

Originally Posted by WhiteDragon (Post 1563455)

brb, killing self

lmao I'd have to agree

Nah I was thinking of making a simple text format kinda similar to graals formats for levels and ganis to use with the editor.

Quote:

Originally Posted by coreys (Post 1563496)

lmao I'd have to agree

Nah I was thinking of making a simple text format kinda similar to graals formats for levels and ganis to use with the editor.

Well at the end day, if it has a GUI Editor type dealy, it'll be ace in my book :P

Quote:

Originally Posted by fowlplay4 (Post 1563513)

Well at the end day, if it has a GUI Editor type dealy, it'll be ace in my book :P

It actually should be very easy with GuiTreeViewCtrl. My first task is to update behavior trees to load from file, then I'll do that. :)

Quote:

Originally Posted by fowlplay4 (Post 1563460)

How come? I found it pretty easy to use and think it would be easier to understand than functions and dot notation but to each his own I guess.

XML is a format which took SGML and reused its syntax to make, basically, the most verbose format possible for document encoding. XML is near impossible to view by the human eye, and is misused and misappropriated and the majority of cases. As a format that "handles anything", it handles nothing particularly well.

To quote Jeff Atwood:

You could do worse than XML. It's a reasonable choice, and if you're going to use XML, then at least learn to use it correctly. But consider:
Should XML be the default choice?

Is XML the simplest possible thing that can work for your intended use?

Do you know what the XML alternatives are? (YAML, JSON, etc.)

Wouldn't it be nice to have easily readable, understandable data and configuration files, without all those sharp, pointy angle brackets jabbing you directly in your ever-lovin' eyeballs?

Then, you go on to mention XSLT, which is a meta-syntax for this, in my opinion, extremely verbose and overused syntax of XML. So, you suggest to take a format which should never be viewed by the eye, and convert it to another format which should still never be viewed by the eye... in order to construct a simple tree?

Furthermore, you say this combination would trump the built-in GS2 grammar of functions and function calls. I think that is just about as ridiculous a claim someone can make regarding clarity.

I have to agree with WD here 100%. (Also, I prefer JSON but still haven't gotten around to finishing a JSON parser for GS2...)

Anyways, new release!

Behavior Tree Version 1.1
I have added the ability to load behavior trees from a simple file format.

PHP Code:


		
			
this.behavior = new TStaticVar();
this.behavior.join("ai-behaviortree");
this.behavior.loadFromFile("behavior_tree_name", this);

This will load a behavior tree from a "behaviors/behavior_tree_name.txt" dynamically. Make sure that your npc-server has rights to this. The comments in the script should explain the further details.

Here's what the example script in the first post looks like in file format:

PHP Code:


		
			
rootSelector
  leaf search %this
    decorator filter %this,state,idle
    getParent
  sequence
    decorator filter %this,state,chase
    leaf findPath %target
      getParent
    leaf move %this
      decorator loop %path_size
      getParent
    getParent
  sequence
    decorator filter %this,state,attack
    leaf attack %this
      getParent
    macro pause 0.5
    getParent
  sequence
    decorator filter %this,state,dead
    macro setCharAni, dead
    getParent

You may note that what was once this.path.size() is now %path_size. Unfortunately, I don't have any real way to allow calling a function of an object like that, so for situations like that you'll have to save info like that elsewhere, in this case a variable called path_size.

The next step is a Behavior Tree editor, so you won't have to mess with any of this! :)

Like the format, but the getParent lines seem like it's redundant.

Alright, I'll probably never suggest XML again. Thanks for that little explanation.

lol, Damn man. Just wanna say people this was fun to watch coreys work on. You wouldn't believe the RC spam it caused from the updates on it but it was very nice to see what came out of it. I think this could be a very nice advancement towards making gameplay better and efficient with the right people working with it. Definitely not me because I don't understand a lick of what this all does except for making baddies run more efficiently and probably allow more options to the creatures and such you create. Good job bro. +Rep

Can you post a real example or two to prove that it works?

Quote:

Originally Posted by DrakilorP2P (Post 1563571)

Can you post a real example or two to prove that it works?

It's in the works! :) I've also gotten a lot done on a graphical behavior editor for these.

Your dedication is admirable!

I'm sorry for this huge delay in getting this out (just been so busy) but I finally have a graphical Behavior Editor! (As well as a new shiny update to the behavior trees) My next task is a fully working example AI.

Behavior Editor Version 1.0
http://coreymedia.com/graal/behavior-editor-example.png
This simple to use GUI will allow you to quickly and easily create and edit AI Behaviors on the fly. To fire up this GUI simple use the command "/behavioredit".

All behaviors are saved as behavior files in the "behaviors/" directory, so be sure to give your NPC-Server access to this directory.

As stated in the last update, you can load a behavior file as such:

PHP Code:


		
			
this.behavior = new TStaticVar();
this.behavior.join("ai-behaviortree");
this.behavior.loadFromFile("behavior_tree_name", this);

Behavior Trees Version 1.2.1
Several updates here.

All root nodes are selectors now, which is initialized with just "root".
Because all roots are now selectors, the behavior file syntax no longer needs the root function (so no "rootSelector" or "rootSequence").
Selectors now cache the last child node that succeeded (returned true) and tries that node first.
The loop function will now loop until a node returns false if the loop number argument is -1.
Added security to the loadFromFile function so that allow certain function names.

Download
The full set, along with it's dependencies, can be downloaded here.

Looks like the interface is stupid easy to follow, Only issue is figuring how it all works. Great job man.

When I was in school, I did a lot of research projects in robotics, but never had the chance to get into AI behavior trees too much. So, this was definitely interesting for me to look at. If I ever get back into the Graal coding trenches, this is one thing I'm sure to play around with. Great job!

The only suggestion I have is: attach your code! Heaven forbid, coreymedia goes down and poor little Billy can't tinker with your behavior editing goodness.

Haha, well I intend to have that site up for some time, so if it goes down I'll know to do that. :)