Godot Behavior Tree

The Behaviour Tree is a popular way to code AI (Artificial Intelligence) in a game such as how the NPC (Non Player Controlled) characters act. In this tutorial we will try to create classes in Godot that allow us to implement a Godot Behaviour Tree.

The Behaviour Tree is a tree of Nodes that propagate in a tree-like fashion down to leaves that finally implement functionality of the game.

The traversal of the tree happens on every tick of the game so in Godot it would be on every video frame.

We will base our code implementation on this Behavior Trees article.

Introduction

Our Behavior Tree will have an entry point to start it off (first Node) and it will poll the status of it’s child node on every frame of the game. The children will obediently report status back when asked.

An actual behaviour is comprised of a sequence of decision making based on external circumstances. Translated into programmer speak: there is an object in a context and it can traverse state based on various routes around a tree structure.

So there is: where we are now and what external influences are there to consider. NPC state and context.

The Task

We should start with a Base Class that every Node in the Behaviour Tree will Inherit from. This Task class will provide all of the essential functionality for the Leaf and Branch Nodes that may be extended upon or adopted as need be.

extends Node

class_name Task

# States
enum {
	FRESH,
	RUNNING,
	FAILED,
	SUCCEEDED,
	CANCELLED
}

var control = null
var tree = null
var guard = null
var status = FRESH

# Final methods
func running():
	status = RUNNING
	if control != null:
		control.child_running()

func success():
	status = SUCCEEDED
	if control != null:
		control.child_success()

func fail():
	status = FAILED
	if control != null:
		control.child_fail()

func cancel():
	if status == RUNNING:
		status = CANCELLED
		# Cancel child tasks
		for child in get_children():
			child.cancel()

# Abstract methods
func run():
	# Process the task and call running(), success(), or fail()
	pass

func child_success():
	pass

func child_fail():
	pass

func child_running():
	pass

# Non-final non-abstact methods
func start():
	status = FRESH
	for child in get_children():
		child.control = self
		child.tree = self.tree
		child.start()

func reset():
	cancel()
	status = FRESH

In the above code comments we are mentioning abstract and final . This is borrowed terminology from the Java coding world which means final (don’t change it) and abstract (put your own spin on it).

The Leaf Node

The Leaf Node is the action object - it does stuff according to it’s current state. Each Leaf Node will extend the Task class and call running(), success(), or fail(). It’s run() method will be called on every tick. A State Machine may be a good fit for it’s run code structure unless it is doing something trivial. Here is code for a most basic Leaf Node that simply reports success:

extends Task

class_name Leaf

func run():
	success()

For testing, we will create various Leaf Nodes such as this Counter:

extends Task

class_name Counter

var count = 0

const MAX = 100

func run():
  if status == RUNNING:
    count += 1
    if count <= MAX:
      tree.show_value("Count", count)
      running()
    else:
      count = 0
      success()

This does it’s work in the run() function and reports a running status until the count has reached 100 when it reports success.

The top-most Node of the Behaviour Tree is referenced by the tree property and may have custom methods that we may call such as show_value() in this example.

Decorator Nodes

A Decorator wraps it’s child class, modifying or selectively ignoring the child’s status reports.

We will initially implement these Decorators:

Example code for Always Fail:

extends Task

class_name AlwaysFail

func run():
  if get_child_count() > 0:
    get_child(0).run()
  fail()

# Ignore child success
func child_success():
  pass

# Ignore child failure
func child_fail():
  pass

A child Node is optional for this Node, but if it exists, we call it’s run() method.

Example code for Invert:

extends Task

class_name Invert

func run():
	get_child(0).run()
	running()

func child_success():
	fail()

func child_fail():
	success()

This must have a child Node that provides status updates.

Code for Repeat:

extends Task

# Repeats the child Task and reports Success after repeating unless it fails

class_name Repeat, "res://icons/repeat.png"

# Number of times to run or zero for infinite
export(int) var LIMIT = 5

var count = 0
var repeating = false

func run():
	if not repeating:
		repeating = true
		get_child(0).run()
	running()

func child_success():
	if LIMIT > 0:
		count += 1
		if count >= LIMIT:
			count = 0
			repeating = false
			success()
	if repeating:
		get_child(0).run()

func child_fail():
	repeating = false
	fail()

This code counts successful repetitions of the child Node until it stops repeating and reports success.

Further examples may be found in the code repository.

Composite Nodes

Composite tasks control how the branches of their children are handled such as in a sequence or in parallel.

We will implement these Composite Tasks:

Code for Sequence:

extends Task

# All children must run successfully

class_name Sequence

var current_child = 0

func run():
  get_child(current_child).run()
  running()

func child_success():
  current_child += 1
  if current_child >= get_child_count():
    current_child = 0
    success()

func child_fail():
  current_child = 0
  fail()

Here we run the child Nodes one by one until one fails or they all succeed. For Selector, we do the opposite, we run the child Nodes one by one until one passes or they all fail.

Code for Random Selector:

extends Task

# One randomly selected child must succeed

class_name RandomSelector

var sequence
var idx = 0

func _ready():
	set_sequence()

func set_sequence():
	idx = 0
	sequence = range(get_child_count())
	sequence.shuffle()

func run():
	get_child(sequence[idx]).run()
	running()

func child_success():
	set_sequence()
	success()

func child_fail():
	idx += 1
	if idx >= sequence.size():
		set_sequence()
		fail()

Here we shuffle the order of execution for each child Node.

Code for Parallel:

extends Task

# Run all child Tasks together in SEQUENCE or SELECTOR policy mode

class_name Parallel

enum { SEQUENCE, SELECTOR }

export(bool) var policy = SEQUENCE

var num_results = 0

func run():
	for child in get_children():
		child.run()
	running()

func child_success():
	num_results += 1
	if policy == bool(SEQUENCE):
		if num_results >= get_child_count():
			num_results = 0
			success()
	else:
		success()

func child_fail():
	num_results += 1
	if policy == bool(SELECTOR):
		if num_results >= get_child_count():
			num_results = 0
			fail()
	else:
		fail()

The Parallel Task needs an execution policy i.e. what determines success or failure.

Further examples may be found in the repository.

Entry Point

The Node at the head of the Behaviour Tree will be the entry point. It will extend the Task class as usual but will be customised for the application/game that it is used in. It will have start code and maybe emit signals. In fact it could be a Godot Behaviour Tree class that is Instanced in Scenes.

More solutions