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:
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.
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):
Included in this post is the 'ai-behaviortree' class and a class it relies upon: 'util_dict' which is a class for associative arrays.
03-17-2010, 11:02 PM
I encourage people to look at some of the pages I linked to, especially the first four, as they are the simplest.
Linear Mode
