Version:	1.0.0
Type:		Artificial Intelligence
Author:		Benjamin D. Richards for Kiwi.js Team
Website:	www.kiwijs.org
Kiwi.js		Version Last Tested: 1.1.1

1.0.0

• Initial Release.

src/		The source files for the plugin. Get your core files here.
docs/		API documentation generated by yuidocs.
examples/	Examples of the plugin in action.
README.md	This readme file.

The AI Tree plugin allows you to build powerful, intuitive control structures for your KiwiJS games. It serves as a base for you to develop your own AI suite.

It can be hard to learn how AI trees work without some hands-on experience. We've included two examples in the examples folder.

This example is fairly simple. You click to drop barrels into the scene, and the guards will shoot them. It demonstrates simple checks and actions. Using code not much more complicated than this, you can create AI that can navigate platforms, jump gaps, and avoid pitfalls.

The example is located in examples/barrel-example. The custom Outer Nodes for this example are defined in examples/barrel-example/js/basic-patrol-ai.js. The AI tree for the guards is defined in examples/barrel-example/js/game-obects/soldier.js.

Exercise: Try changing the guard AI so that, instead of shooting barrels, they turn around and walk away.

This is a much more complex example. Several hundred "fliers" are trying to balance companionship, personal space, and hunger. Each has a brain consisting of 60 unique nodes. There are more than fifteen thousand nodes governing the behaviour of the swarm, making it arguably as complex as a single human neuron. We reckon this demonstrates how powerful and efficient an AI tree can be.

The example is located in examples/flocking-example. The custom Outer Nodes for this example are defined in examples/flocking-example/js/flocking-ai-plugin.js. The AI tree for the fliers is defined in examples/flocking-example/js/game-obects/flier.js.

Exercise: Try adding a new kind of flier that tries to ram into random fliers and doesn't care about personal space, disrupting the conventional flocks.

Acquire the full plugin, with examples and API documentation, from Github.

Obtain the latest version of the plugin from the src/ folder. Use the minified version when possible.

Include this in your html file after the Kiwi library:

<script src="libs/kiwi.js"></script>
<script src="libs/ai-tree-1.0.0.min.js"></script>

See below for the theory of nodes.

To create an AI tree and add it to an entity, use the following form:

// Create AI object
var ai = new Kiwi.Plugins.AiTree.Ai( targetEntity );

// Add as a component
targetEntity.components.add( ai );

// Register on the target entity for ease of access in future.
targetEntity.ai = ai;

// Add a root node to the AI object.
// This node will run when update is called.
ai.addChild( node );
// Or
ai.setRoot( node );
// Or
ai.root = node;

To update the tree once per frame, add this to your state's update function:

targetEntity.ai.update();

To create an Inner Node and build your tree, use the following form:

// Create a default node
var sequencerNode = new Kiwi.Plugins.AiTree.Sequencer( {} );

// Create a node with optional parameters
var selectorNode = new Kiwi.Plugins.AiTree.Selector( {
		name: "Optional name parameter"
	} );

// All nodes use a param object to simplify configuration.
// You can specify this externally...
var params = {
	name: "Optional name parameter",
	runsParent: true
};
var sequencerNode = new Kiwi.Plugins.AiTree.Sequencer( params );

// ... or leave it out altogether if you just want defaults.
var selectorNode = new Kiwi.Plugins.AiTree.Selector();

// All inner node types
var sequencerNode = new Kiwi.Plugins.AiTree.Sequencer( {} );

var selectorNode = new Kiwi.Plugins.AiTree.Selector( {} );

var untilSuccessNode = new Kiwi.Plugins.AiTree.UntilSuccess( {} );

var untilFailureNode = new Kiwi.Plugins.AiTree.UntilFailure( {} );

var timeLoopNode = new Kiwi.Plugins.AiTree.TimeLoop( {

		// Optional timer duration
		timerDuration: 10
	} );

var timeTrialNode = new Kiwi.Plugins.AiTree.TimeTrial( 

		// Optional timer duration
		timerDuration: 10
	} );

// Attaching nodes:
// (Always use addChild to add children. Other methods do not modify
// the tree data and may break the AI.)
sequencerNode.addChild( selectorNode );

To create an Outer Node, use the following form:

var successNode = new Kiwi.Plugins.AiTree.Success( {} );

var failureNode = new Kiwi.Plugins.AiTree.Failure( {} );

var counterNode = new Kiwi.Plugins.AiTree.Counter( {

		// Optional maximum count parameter
		max: 8
	} );

To get the most out of the AI Tree, you will need to code your own Outer Nodes. To do this, extend the Kiwi.Plugins.AiTree.OuterNode function as follows:

var TemplateNode = function( params ) {

	// Call template constructor
	Kiwi.Plugins.AiTree.OuterNode.call( params );

	// Perform custom constructor functions, such as reading extra params
};

// Perform prototype extension
Kiwi.extend( TemplateNode, Kiwi.Plugins.AiTree.OuterNode );

// You may define a default node name.
// This will itself default to "Untitled outer node".
TemplateNode.prototype.DEFAULT_NODE_NAME = "Optional default node name";

// Add custom functionality to the _run function.
// This is an empty function provided by the Outer Node template,
// and is automatically called when the node is traversed.
TemplateNode.prototype._run = function() {

	// Your code goes here

	// You must set the node status. This tells the tree how to traverse.
	// A node that checks some property should return success or failure.
	// A node that performs some action should always succeed.
	// Some nodes might take several updates to finish, and should use the
	// running status.
	// Valid statuses are defined on the Outer Node for easy access:
	// this.STATUS_SUCCESS
	// this.STATUS_FAILURE
	// this.STATUS_RUNNING
	// this.STATUS_ERROR
	this.status = this.STATUS_SUCCESS;
}

An AI Tree or Behavior Tree is a decision-making structure. It is powerful and easy to use, once you get your head around it.

The tree is a directed acyclic graph. Translated into plain language, it's a series of nodes linked together (a "graph"). Each link consists of a parent and a child (a "directed" graph). Although nodes can generally be connected freely, you cannot construct a graph in which a node becomes its own ancestor or descendant (which is a "cycle", and in its absence this is an "acyclic" graph); this prevents infinite loops.

To use the tree, we traverse its branches. Each node directs which link to follow. We might not always visit every node, but we are likely to come back to others frequently in a single traversal.

The nodes make decisions that govern the traversal. There are two main types of node: Inner Nodes and Outer Nodes. They communicate using status signals.

All nodes communicate exclusively through the use of status signals. There are five such signals:

• Kiwi.Plugins.AiTree.OuterNode.STATUS_SUCCESS - a node has succeeded in its task
• Kiwi.Plugins.AiTree.OuterNode.STATUS_FAILURE - a node has failed in its task
• Kiwi.Plugins.AiTree.OuterNode.STATUS_RUNNING - a node has not finished, and will continue later
• Kiwi.Plugins.AiTree.OuterNode.STATUS_READY - a node is ready to run
• Kiwi.Plugins.AiTree.OuterNode.STATUS_ERROR - a node has encountered an error

Of these, STATUS_SUCCESS and STATUS_FAILURE are the most common.

For the purpose of simplicity, we denote AI trees using a nested sequential structure. The children of a node are listed, indented, with their children, sequentially. This makes it fairly easy to see how a given AI tree is traversed.

For example, consider this tree:

• A
  • B
    • C
  • D

In this example, A is the "root" or top node. It has B and D as children. B in turn has C as a child. The tree attempts to traverse top to bottom, in order ABCD. (In practice, it's actually ABCBAD, because it returns to the parent for processing. However, we can safely ignore this.) The tree may also skip some elements, depending on the logic elements at play.

Inner nodes form the heart of the AI Tree. All inner nodes have an array of children, which may be inner or outer nodes. When you traverse an inner node, it will begin by sending you to its first child. Your traversal will eventually return to the inner node. At this point, the node will either send you to its next child, or back to its parent.

There are six types of inner node, and all have a valuable function. In practice you will probably use the Sequencer and Selector most frequently.

• Selector
• Sequencer
• UntilSuccess
• UntilFailure
• TimeLoop
• TimeTrial

This inner node wants to return to its parent. If it receives STATUS_SUCCESS from a child, it returns STATUS_SUCCESS to its parent immediately, and will not execute any other children. It will only fail if it gets to the end of its children and has no successes anywhere.

The Selector is equivalent to an OR operation on its children. If any child is successful, it returns success; if they all fail, it fails.

The Selector is useful for performing one task on a list, and no others.

For example, a simple Selector might decide which way to go:

• Selector
  • Go Left?
  • Go Right?

If the left option is successful, the Selector will immediately return, and never attempt to run the right option. This is logical - you can't go left and right at the same time.

This inner node wants to run its children. If it receives STATUS_SUCCESS from a child, it executes its next child. If it gets to the end of its children, it returns success. If if receives STATUS_FAILURE from a child, it immediately returns STATUS_FAILURE to its parent and will not execute any other children.

The Sequencer is equivalent to an AND operation on its children. If all children are successful, it returns success; if any fail, it fails.

The Sequencer is useful for performing a series of tasks. It is also useful for "if-then" style statements: place a check before an action, and the action will only be reached if the check succeeds.

For example, a simple Sequencer might deal with navigation:

• Sequencer
  • Walk Forward
  • Is there a Door?
  • Open Door

This will always walk forward. If it meets a door, it will attempt to open it. If there is no door, it will not bother with a nonexistent door handle.

This inner node is like a Selector, but it will not stop running at the end of its children. It will simply loop back to the beginning and run again, until it receives success.

This node should be used with caution. It can create an infinite loop and halt your game.

The UntilSuccess is useful for tasks that take many repetitions to complete.

For example, a very simple UntilSuccess might deal with selecting a room in a tavern:

• UntilSuccess
  • Discard Worst Room (and return failure if there is still more than one room)

This will repeatedly discard the worst room. Once there is only a single room left, it must be the best one.

This inner node is like a Sequencer, but it will not stop running at the end of its children either. It will loop over and over until it receives failure.

This node should be used with caution. It can create an infinite loop and halt your game.

The UntilFailure is useful for tasks that take many repetitions to complete.

For example a very simple UntilFailure might plot a route out of a labyrinth:

• UntilFailure
  • Go a random direction
  • Are we still in the labyrinth?

This isn't a very good way to escape a maze, but it might work... given a few years.

This inner node runs for a fixed duration, then stops. It doesn't care whether its children are succeeding or failing. It simply succeeds when it runs out of time.

The TimeLoop is useful for tasks that might never be perfect, but benefit from more time.

For example, a TimeLoop might play a game of chess:

• TimeLoop
  • Create random move
  • Is random move superior to cached move?
  • Replace cached move with random move

Because no current computer could ever calculate all the moves possible in chess, you can never get the perfect move. But you can certainly consider as many as possible, and hope that one is pretty good.

This inner node runs for a fixed duration, but if one of its children fails, it also fails. It succeeds when it runs out of time.

The TimeTrial is useful for tasks that might never be perfect, but also could finish quickly.

For example, a TimeTrial might play a slightly more sophisticated game of chess:

• TimeTrial
  • Create random move
  • Is random move superior to cached move?
  • Replace cached move with random move
  • Is the game out of checkmate?

This AI would consider moves much like the TimeLoop example, but in this case, if it finds a checkmate - a guaranteed win - it fails and ends the traversal early.

Outer nodes form the periphery of the AI tree. An outer node has only parents, never children. It does one task and then returns status to its parent. Think of an outer node as the interface between the brain of the tree and the world around it.

It may be useful to consider two broad informal types of outer node: checks and actions. A check answers a question using STATUS_SUCCESS or STATUS_FAILURE as yes or no. An action performs some task. Most actions will always return STATUS_SUCCESS. It is possible to combine checks and actions into a single node, but we advise you to keep them separate whenever possible - it's just simpler.

Most outer nodes must be user defined. There are simply too many things that they can do. We have included examples with this plugin, and encourage you to use them as templates and inspiration for your own AI constructs.

Outer nodes will usually be connected to a game object or actor, which we call an entity. This entity usually tracks persistent AI data itself, such as target identity, current mood, position, physics etc. The outer nodes can query and set these properties directly, sharing information without direct connections.

The AI Tree plugin includes three predefined outer nodes:

• Success
• Failure
• Counter

var success = new Kiwi.Plugins.AiTree.Success( {} );

// You can leave out the params object if you have no customisation:
success = new Kiwi.Plugins.AiTree.Success();

The Success node always returns STATUS_SUCCESS. This is useful for controlling tree traversal in large AIs.

Consider the following Sequencer:

• Consume Meal Sequencer
  • Drink Sequencer
    • Check for water
    • Drink water
  • Eat Sequencer
    • Check for food
    • Eat food

Ordinarily you would drink water then eat food. But there is a bug in this tree. It's not immediately apparent, but if you run out of water, you will immediately become unable to eat. Why is this?

Well, if your Check for water fails, so does the Drink Sequencer - and then so does your Consume Meal Sequencer.

To solve this, we use a "success wrapper". Consider the enhanced Sequencer:

• Consume Meal Sequencer
  • Drink Wrapper (a Selector)
    • Drink Sequencer
      • Check for water
      • Drink water
    • Success
  • Eat Sequencer
    • Check for food
    • Eat food

By placing the Drink Sequencer inside a Selector, we guarantee that it will not immediately return if it fails. By adding the Success node, we guarantee that the Selector will always return STATUS_SUCCESS, either from the Drink Sequencer or the Success node itself.

var failure = new Kiwi.Plugins.AiTree.Failure( {} );

// You can leave out the params object if you have no customisation:
failure = new Kiwi.Plugins.AiTree.Failure();

The Failure node always returns STATUS_FAILURE. This is useful for controlling tree traveral in large AIs.

var counter = new Kiwi.Plugins.AiTree.Counter( {
		max: 8,
		resetOnReady: true
	} );

The Counter node counts up from 0 every time it runs. It returns STATUS_FAILURE until it counts up to its maximum, at which point it returns STATUS_SUCCESS. This is useful for controlling an UntilSuccess or UntilFailure node, causing it to execute a certain number of repetitions then exit.

The default value of max is 1.

The count resets to 0 if the Counter reaches the maximum, or if the tree begins a new update. You can change this behavior by setting the optional parameter resetOnReady to false. If you do, the count will be persistent between updates. It will only reset to 0 when it reaches the maximum value.

Consider the following tree:

• UntilSuccess
  • Try to walk forward
  • Sequencer
    • Turn left
    • Failure
  • Counter (max 4)

This will cause an entity to attempt to move from where it stands. If it can't go ahead, it will turn left and try again. The counter is used to ensure that it turns a full circle, and doesn't stand in one place spinning forever. (In the worst case, this causes your browser to hang.)

Inner nodes usually execute their children in a fixed order. While this gives the impression of logical, methodical AI minds, sometimes we want to introduce some randomness.

You can specify an optional parameter on inner nodes to permit them to shuffle their children. If you enable this parameter, they will reorder their children on every traversal.

var node = new Kiwi.Plugins.AiTree.Sequencer( {
		shuffle = true;
	});

Shuffle is compatible with the STATUS_RUNNING node status. Even if the node is shuffled, it will still come back to the last running child, wherever it has arrived in sequence.

If you set the status of a node to STATUS_RUNNING, its parent will return STATUS_SUCCESS, then skip straight to it on the next traversal. This can be handy for tasks that take more than a single frame to complete.

For example, a character might want to walk to a door and open it. You might do it something like this:

• Movement Sequencer
  • Walk To Door (returns STATUS_RUNNING if it hasn't reached the door)
  • Open Door

Although it is a sequencer, the Movement Sequencer will not move on to Open Door until Walk To Door has completed its run.

By default, while outer nodes do set their parents to STATUS_RUNNING, inner nodes do not, and instead revert to STATUS_SUCCESS. This is by design. Imagine a tree which uses running to control a guard on patrol. The guard walks between several waypoints in sequence: each waypoint is an action node which returns STATUS_RUNNING when it is walking and STATUS_SUCCESS when it gets to the destination. So far so good. But what if we now add a branch that checks and chases intruders?

• Guard Behaviour Selector
  • Detect Intruder Sequencer
    • Is there an Intruder?
    • Chase Them
  • Patrol Sequencer
    • Waypoint1
    • Waypoint2
    • Waypoint3

If an intruder appears while the guard is walking between waypoints, we want the guard to immediately abandon their route and give chase. If the Patrol Sequencer were set to STATUS_RUNNING, the guard's AI would immediately run it, skipping past the Detect Intruder Sequencer. This means the guard would only be able to see intruders when they reach Waypoint 3 and the Patrol Sequencer finally succeeded, freeing the tree for a single update.

This is undesirable, so we disable inheritance of STATUS_RUNNING in inner nodes.

However, sometimes you want that inheritance to occur. For example, consider the AI of a deadly assassin robot:

• Termination Protocol Selector
  • Logistics Sequencer
    • Are we out of milk?
    • Go to shop (running)
    • Pick up some milk (running)
    • Come home (running)
  • PsyOps Sequencer
    • Is it Saturday night?
    • Go to the club (running)
    • Boogie (running)
    • Come home (running)
  • Read a book (running)

If our assassin robot is in the middle of a funky funky boogie, we do not want to suddenly trigger a milk shopping expedition. That is socially bogus. So we want the Logistics Sequencer and PsyOps Sequencer to signal the Termination Protocol Selector that they are also running if their children are running. But how?

You can reactivate STATUS_RUNNING inheritance by creating nodes with the runsParent parameter or property:

var node = new Kiwi.Plugins.AiTree.Sequencer( {
		runsParent: true
	} );

// You can also access the property directly
node.runsParent = false;

If runsParent is true, a node that receives STATUS_RUNNING will also become STATUS_RUNNING. This allows you to create a tree or tree segment that remembers its current position, even in complicated nested structures.

Note that outer nodes set runsParent to true by default. You can set this to false in the normal fashion. This will prevent them from using any running functionality whatsoever. Because you design your own outer nodes, this should not be necessary, but it is available.

Sometimes you want a check to start something, and sometimes you want that same check to prevent something. For example, consider this AI tree:

• Panic Sequencer
  • Is a zombie nearby?
  • Run screaming

This makes sense for a non-zombie. But what happens when you come to program the zombies, and realise that they get upset when they're not surrounded by other walking dead? You could always code a new node for Is a zombie not nearby?, but this is unnecessary duplication. You could also nest it inside a clever set of selectors so that the check breaks out of the sequencer instead of continuing it, but that's not very straightforward.

We provide an Inverter inner node to simplify these matters. Create an Inverter and add a child:

var inverter = new Kiwi.Plugins.AiTree.Inverter( {} );

inverter.addChild( isAZombieNearby );

Now we can create our zombie AI, which panics when it's alone:

• Panic Sequencer
  • Inverter
    • Is a zombie nearby?
  • Run screaming

Although the AI Tree plugin is a directed acyclic graph, it does not actually prohibit the reuse of nodes. So long as they do not become their own ancestor or descendant, they can be used in several places. This can save time coding.

Just be careful: if the nodes have internal references, make sure they're not being applied to different objects. In general, you should create new nodes for different entities in a scene.

The AI Tree plugin was based on an article by Bjorn Knafla. Although the article is no longer online, Knafla and Alex J. Champandard have a chapter in Algorithmic and Architectural Gaming Design at Safari Books.

Alex J. Champandard gives an introduction to behavior trees at AIGameDev.com. Be sure to follow the links - Champandard gives a succinct rundown of many possibilities for the various components of behavior trees.

Chris Simpson has written an informative article about constructing AI tree solutions for real games at Gamasutra.

The Barrel example was initially coded by Lachlan Reid.

Some of the nodes were designed by Ben Harding.

Some inspiration was taken from former work done by Vlad at Instinct Entertainment.