Behaviour Tree

Hey everyone,
I’ve been very interested in reading about behaviour trees of late.
Here’s a sample tree in Python


from itertools import islice




class Enum(type):
    '''Metaclass for Enums in Python'''
    def __new__(cls, name, parents, attrs):
        # Get settings
        bits = attrs.get('bits', False)
        reverse = attrs['reverse'] = {}
        # Set the new values
        for index, key in enumerate(attrs["values"]):
            value = index if not bits else (2 ** index)
            attrs[key] = value
            reverse[value] = key


        # Return new class
        return super().__new__(cls, name, parents, attrs)


    def __getitem__(self, value):
        # Add ability to lookup name
        return self.reverse[value]


    def __contains__(self, index):
        return 0 <= index < max(self.reverse.keys())


    def __repr__(self):
        return "[Enum: {}]
{}
".format(self.__name__,
                                 '
'.join("<{}: {}>".format(n, v)
                                   for v, n in self.reverse.items()))




class EvaluationState(metaclass=Enum):
    values = "success", "failure", "running", "error", "ready"




class LeafNode:


    def __init__(self):
        super().__init__()


        self.state = EvaluationState.ready
        self.name = ""


    def evaluate(self):
        pass


    def on_enter(self):
        pass


    def on_exit(self):
        pass


    def update(self):
        if self.state != EvaluationState.running:
            self.state = EvaluationState.running
            self.on_enter()


        new_state = self.evaluate()


        if new_state is not None:
            self.state = new_state


        if self.state != EvaluationState.running:
            self.on_exit()


    def reset(self):
        self.state = EvaluationState.ready
        self.on_exit()


    def print_tree(self, index=0):
        print('   ' * index, '->', index, self)


    def __repr__(self):
        return "[{} {}] : {}".format(self.__class__.__name__,
                                    self.name,
                                    EvaluationState[self.state])




class InnerNode(LeafNode):


    def __init__(self, *children):
        self._children = []


        for child in children:
            self.add_child(child)


        super().__init__()


    @property
    def children(self):
        return self._children


    def add_child(self, child, index=None):
        if index is None:
            self._children.append(child)


        else:
            self._children.insert(index, child)


    def print_tree(self, index=0):
        super().print_tree(index)
        for child in self.children:


            child.print_tree(index + 1)


        if index == 0:
            print()


    def remove_child(self, child):
        self._children.remove(child)


    def reset(self):
        super().reset()


        for child in self._children:
            child.reset()




class ResumableNode(InnerNode):


    def __init__(self, *args, **kwargs):
        super().__init__(*args, **kwargs)


        self._resume_index = 0
        self.should_restart = False


    @property
    def resume_index(self):
        return self._resume_index


    @resume_index.setter
    def resume_index(self, value):
        self._resume_index = value


    def on_exit(self):
        self.resume_index = 0




class SelectorNode(ResumableNode):


    def __init__(self, *args, **kwargs):
        super().__init__(*args, **kwargs)


    def evaluate(self):
        start = 0 if self.should_restart else self.resume_index
        remembered_resume = False


        for index, child in enumerate(islice(self.children, start, None)):
            child.update()


            if child.state == EvaluationState.running:
                self.resume_index = index + start
                remembered_resume = True
                break


            if child.state == EvaluationState.success:
                break


        else:
            return EvaluationState.failure


        # Copy child's state
        if remembered_resume:
            child = self.children[self.resume_index]


        return child.state




class ConcurrentNode(ResumableNode):


    def __init__(self, *args, **kwargs):
        super().__init__(*args, **kwargs)


        self._failure_limit = 1


    @property
    def failure_limit(self):
        return self._failure_limit


    def on_exit(self):
        self.resume_index = 0


    def evaluate(self):
        failed = 0
        start = 0 if self.should_restart else self.resume_index
        remembered_resume = False


        for index, child in enumerate(islice(self.children, start, None)):
            child.update()


            # Increment failure count (anything that isn't a success)
            if child.state != EvaluationState.success:
                failed += 1


            # Remember the first child that needed completion
            if (child.state == EvaluationState.running
                            and not remembered_resume):
                remembered_resume = True
                self.resume_index = start + index


            # At the limit we then return the last/ last running child's status
            if failed == self.failure_limit:
                if remembered_resume:
                    return self.children[self.resume_index].state


                else:
                    return child.state


        return EvaluationState.success




class SequenceNode(ConcurrentNode):


    @property
    def failure_limit(self):
        return 1




class LoopNode(SequenceNode):


    def evaluate(self):
        while self.state not in (EvaluationState.failure,
                            EvaluationState.error):
            super().evaluate()




class ConditionNode(LeafNode):


    @property
    def condition(self):
        return False


    def evaluate(self):
        return (EvaluationState.success if self.condition
                else EvaluationState.failure)




root = SelectorNode(
                    SequenceNode(
                        ConditionNode(),
                        ConditionNode(),
                    ),
                        ConditionNode(),
                    )
root.evaluate()
root.print_tree()

Selectors exit when something succeeds or is running.
Sequences exit when something fails or is running (according to certain criteria).

Concurrent nodes are types of Sequences which permit a fixed number of “failures” to occur.
Loop nodes are types of Sequences which will continue cycling through until the sequence “fails”.

The included selectors and sequences are “resumable” by default. This means that if a child node causes an exit because its state was “running”, the next evaluation of the parent will resume from that node. This can be disabled with “parent.should_restart = True”.

Condition and Action nodes, unlike the inner nodes of Selectors and Sequences, are leaf nodes. This means that they do not have children.

Conditions are designed to determine whether sibling nodes are invoked (and ultimately, siblings of the parent node) depending upon the semantics of the parent. This is because the state of the node execution bubbles back upwards from the child node.

Example usage:


def attack_behaviour():
   can_attack_or_move = SelectorNode(
                                    WithinAttackRange(),
                                    MoveToActorOrPoint(),
                                )
    can_attack_or_move.should_restart = True


    group = SequenceNode(
                         HasPawn(),
                         HasCamera(),
                         HasWeapon(),
                         SelectorNode(
                                      HasActorTarget(),
                                      FindVisibleTarget(),
                                      ),
                         SequenceNode(
                                      can_attack_or_move,
                                      AimAtActor(),
                                      SelectorNode(
                                               HasAmmo(),
                                               Reload()
                                               ),
                                      SequenceNode(FailedAsRunning(
                                                               CheckTimer()
                                                               ),
                                               FireWeapon(),
                                               SetTimer()
                                               ),
                                      )
                                      )
                        )


    group.should_restart = True


    return group

1 Like

In this example, the following logic takes place:

  • First, a number of conditions are checked, to ensure that any following actions have the correct resources to run. If any of these returns a failure, we exit out of the sequence node, which also returns a failure.
  • The first SelectorNode will return the first node that succeeds (or is running). If the condition node HasActorTarget() succeeds, then the SelectorNode returns Success, which is seen as an accepted return type by its parent; the SequenceNode. This allows the following nodes to be evaluated. However, if the condition fails, we run the FindVisibleTarget action. This returns Success if it finds a target in the camera of the player, or Failure indicating that it couldn’t find one. In the latter case, the parent SequenceNode cannot continue, and the behaviour stops evaluating, returning with a Failure (Just as in (1)).
  • We now enter another SequenceNode. The first node in the sequence is Selector node. This tests if it is in attack range, otherwise it moves closer to the target. The latter node returns Running until we get there, meaning that the SequenceNode we just entered will exit with Running unless we are in attack range. (Hence stopping behaviour, as in (1) (but this time for a Running state and not Failure state).
  • If we were in attack range, we now run the AimAtActor() node. This is an instant action, and return Success most of the time. Then we run a SelectorNode. This tests if we have ammo with HasAmmo(). If we don’t, we then run the Reload() function. If this fails, we return a Failure, which bubbles all the way back up to the top as in (1). Otherwise, we then
  • Now we run the SequenceNode which handles firing. We wrap the CheckTimer() condition in a FailedAsRunning decorator. This means that if the condition fails, we convert the status output to “Running”. This means that the entire behaviour will not fail, but register as running. This is designed to simulate the fact that there is a delay between successive shots, and if we failed then any other behaviours that exist alongside the attack behaviour may start to run, whilst we may still want to fire (if this is an automatic weapon). This is to prevent the AI thinking that the time between shots is a good time to IDLE!
  • If the timer allows us, we then fire the weapon (which is allowed to fail) and restart the timer for the next shot.

In this instance, we have a higher level behaviour implemented as lower level conditions and actions. Presently, the behaviour is implemented so that if the AI can shoot, it will. In reality, you may have other conditions that dictate how many shots the AI takes, and why it does so.

For example, you may remove the hasActorTarget and FindVisibleTarget nodes from this behaviour and use them to trigger the behaviour. Or, this could be combined with a cover system, that will spray bullets above the cover object, first checking if we are behind cover and threatened, otherwise running the normal attack behaviour.

1 Like

This is fantastic! I can’t believe nobody has replied yet.

A state/behaviour system like this should be included in the BGE!
Simply the level to which this is dynamic is amazing. It could be adapted to an infinite number of possible applications, be it artificial intelligence in the game or otherwise.

1 Like