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:
"""
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:
- Check if it can see the player.
- Turn left or in any other direction.
- 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:
"""
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.
This comment is currently awaiting admin approval, join now to view.