IndieVault.it is the main community of Italian independent video game developers. Join us for daily news and reviews about indie games: I know, I know, we only talk in Italian, but we have cookies and we are cool. And what if you don't like cookies? Well, we are in Italy, dudes. Take a slice of pizza and play our games.

Report article RSS Feed Game AI - Behavior Tree

Getting started with Behavior Tree, a simple, fast, scalable and reusable AI technique for game programming.

Posted by thek3nger on Oct 22nd, 2012
Intermediate Client Side Coding.

What they have in common the Pac-Man AI, a video games icon appeared in 1980, and Halo: Combat Evolved, the blockbuster FPS of 2001? Separating them are almost 21 years apart, twenty years of evolution that has brought games from a number of semi-anthropomorphic pixels in a realistic 3D world. However, in practice, in these two decades the videogame AI is not changed much: although the increase of the performance of the PC has allowed the algorithms of AI to evaluate a larger number of variables the algorithm at the base remained roughly the same .
Until 2004, in fact, the decision making problem in video games are simply based on state machines (or finite state machine or FSM). The concept behind this technique is quite simple.


Suppose you design the AI ​​of an enemy in a video game. The FSM approach is to describe the various states in which the enemy can be and transactions between states which correspond to events that moves our agent from one state to another. For instance the enemy can be in "approach" state if he gets close to the player or in "run away" if the enemy escape.

FSM are easy to implement, easy to understand and with good performance (for each iteration you perform only a check on all the transitions of the current state). On the other hand this method is difficult to maintain (add and remove a state can involve a lot of states and transitions) and also does not allow a great expressivity without exponentially increasing the number of states.
In 2004 is released Halo 2 with a new technique that has revolutionized the AI ​​in games: the behavior tree. The BT are actually the most used AI technique in any commercial games. But let's see in detail.

As the name says the BT are trees (and not graphs like FSM). The leaves of these trees correspond to the actions that the agent can perform while the internal functional nodes say according to which policy you should get down to the lower level of the tree.
Each node or leaf has a return value. In the leaves this value is true if and only if the corresponding action has been executed. In the internal nodes the return value is a function of the return values ​​of the children.


Let's start with a basic example. In the figure you can see a simple BT with a functional node called selector. This node execute the child nodes from left to right stopping at the first node that returns a positive value. In this particular example an agent with this BT will try to attack. If the attack is successful then the selector has finished his work and ends positively. However, if the attack is not successful (for instance the enemy can not attack because target is too far away) selector will pass to the next action: provoke. If also provoke has no effect or can not be executed the agent will limit itself to observe the player.

A selector can be implemented in this way:

python code:
class Selector(Task):
    """
    Selector Implementation
    """

    def __init__(self):
        super(Selector,self).__init__()
   
    def run(self):
        for c in self._children :
            if c.run() :
                return True
        return False

This other example uses a node called sequencer. This node is the dual of the selector: it return negatively at the first child that returns a negative value. In practice it performs its children from left to right as long as they return a positive value. In this case the agent performs in sequence:

  1. Check if it can see the player.
  2. Turn left or in any other direction.
  3. Run away from the player.

These two functional nodes are enough to build behaviour of great complexity and can, of course, be combined with each other.
A sequencer can be implement in this easy way:

python code:
class Sequence(Task):
    """
    Sequencer Implementation
    """

    def __init__(self):
        super(Sequencer,self).__init__()
       
    def run(self):
        for c in self._children :
            if not c.run() :
                return False
        return True


This is a more complex example. In this example we can recognize a BT that model the behavior of an agent that has to go through a door.
In addition to these two basic nodes is possible to define other nodes such as:

  • Random Selector - Symbolized by ~?. It is equal to the basic selector but performs her children in a random order.
  • Random Sequencer - Symbolized by a twisted arrow (~>). It is equal to the classic sequencer but with nodes performed in random order.
  • Until - Symbolized by a diamond node with a single child. This node repeats the execution of his only son until it returns false.

Of course, nothing prevents you to invent new functional nodes and use them in your BT.In this page you can find python code that implements the last BT example! :)I hope you like this little introduction. It's my first big articles in English. Sorry for any mistakes.

Post comment Comments
Guest
Guest Jan 5 2014, 1:37am says:

This comment is currently awaiting admin approval, join now to view.

Post a Comment
click to sign in

You are not logged in, your comment will be anonymous unless you join the community today (totally free - or sign in with your social account on the right) which we encourage all contributors to do.

2000 characters limit; HTML formatting and smileys are not supported - text only

Established
Jun 21, 2010
Privacy
Public
Subscription
Open to all members
Homepage
Indievault.it
Contact
Send Message
Email
Members Only
Membership
Join this group
Group Watch
Track this group
Tutorial
Browse
Tutorials
Report Abuse
Report article
Related Groups
IndieVault
IndieVault Hobbies & Interests group with 75 members