Behaviour Trees in Erlang flavour

Reading about current state of the art in AI games, I’ve found that behaviour trees seem to be the next best thing. There are many examples of behaviour trees around, like Behave for Unity from AngryAnt, or the AI Sandbox from the people at AIGameDev. So, I decided to build my own in Erlang.

Why Erlang? Well, I thought it might have some advantages for AI applications. First, it’s a functional language, with function pattern matching and function variables, and I hoped those features could be useful in AI algorithms. Second, the language provides message passing and lightweight processes as primitives, which should come in handy when designing large-scale AI simulations and organizing the different modules in an AI (perception, action, reasoning…). And third, I just love it 🙂

As a first approach, I decided that the tree would be contained in its own process, and that it would take a reference to the underlying “motor system”, containing the pathfinding or steering module and the locomotion (i.e. animation) system.

After reading a couple of very useful articles in AIGameDev, I got the idea that the action in a behaviour tree is selected running the root node and following the directions there, until we get to an “action node” that has an action that completes either successfully or unsuccessfully. The parent node for this action node can then take a choice on the next node to run. I decided to implement the following nodes:

  • Sequence: runs its nodes in sequence; if none fail, then it reports success, otherwise it reports fail.
  • Selector: runs nodes in sequence until one is successful (note that this may mean that it just runs the first node).
  • Loop: runs the child node N or inifite times, unless it fails. A loop is a special kind of decorator, a node that takes a single child node and executes it or not based on some condition.
  • Condition: another decorator. Runs its child behaviour if some condition about the world holds true, otherwise fails.
  • Action! This kind of node should send some message to the underlying “motor system” and wait for results.

Let’s take a look at each one in sequence.

Action Node

The action node is the simplest of them all. It just takes an action as a parameter and sends it to the motor system. It is as simple as this:

action(Engine, {Action, Params}) ->
    Engine ! {action, Action, Params},
    receive
        {event,success} ->
            {success};
        {event,fail,Reason} ->
            {fail,Reason}
    end.

Note that one of the advantages of erlang is the simplicity of message passing. While the action is being performed, the lightweight process running the behaviour tree will be blocked – without blocking any OS thread. The engine can run on its own, performing the specific action, until it succeeds or fails. Thanks to several interface modules (jinterface, erlc, OTP.NET…), the engine can be written in other languages, like Java or C#, using different algorithms like graph-based pathfinding or steering.

Sequence Node

As we said before, this node runs its child actions one by one until either one fails, and so this action fails, or all succeed, meaning success.

seq_behaviours(_Engine, []) ->
    {success};
seq_behaviours(Engine, [{FirstBeh, FirstParams}|RestBeh]) ->
    case FirstBeh(Engine, FirstParams) of
        {success} ->
            seq_behaviours(Engine,RestBeh);
        UnhandledEvent = {fail, _} ->
            UnhandledEvent
    end.

Thanks to erlang’s pattern matching and list expressions, this node’s code is quite compact. Since this node does not deal with the underlying engine, it will not block.

Selector Node

Our implementation for a selector node will try a series of actions in turn until one succeeds. In a way, it is complementary to the sequence node.

alt_behaviours(_Engine, []) ->
    {fail,no_more_actions};
alt_behaviours(Engine, [{FirstBeh, FirstParams}|RestBehs]) ->
    case FirstBeh(Engine, FirstParams) of
        {success} ->
            {success};
        {fail, _} ->
            alt_behaviours(Engine, RestBehs)
    end.

Loop Node

The loop node takes a child node and runs its child behaviour N times, or always.

loop(Engine,{always,Behaviour={FirstBeh, FirstParams}}) ->
    case FirstBeh(Engine, FirstParams) of
        {success} ->
            loop(Engine,{always,Behaviour});
        UnhandledEvent = {fail, _} ->
            UnhandledEvent
    end;
loop(_Engine,{0,_Behaviour}) ->
    {success};
loop(Engine,{N,Behaviour={FirstBeh, FirstParams}}) ->
    case FirstBeh(Engine, FirstParams) of
        {success} ->
            loop(Engine,{N-1,Behaviour});
        UnhandledEvent = {fail, _} ->
            UnhandledEvent
    end.

Condition Node

A Condition node succeed if the condition evaluates to true and the child node succeeds.

condition(Engine,{Condition, {Beh,Params}}) ->
    if Condition ->
           Beh(Engine, Params);
       true ->
           {fail, condition_not_met}
    end.

Some Remarks

Using Erlang, a functional programming language, has some features that come quite handy:

  • A behaviour is composed of lists and tuples of the previously described behaviours. This means that a behaviour can be written in an XML format without much trouble, just by linking XML elements to Erlang functions (and you can easily parse XML in Erlang using the xmerl_scan:file/2 function).
  • A process executing a behaviour can become blocked until the engine sends some event back. This means that we don’t need to keep a explicit cursor telling us where we are in the behaviour tree; the execution stack for the behaviour process will do exactly that.

Testing Time!

To test this small module, we’ll write a small Engine process in erlang that provides a series of messages that will “tell a story” to be interpreted by the behaviour tree, and then see if the tree can follow the sequence. This mock engine could then be replaced by a real motor an sensor module that interacts with the game world and other players. But first we will describe the behaviour tree we will be using.

BehaviourTree =
             {fun beh_trees:loop/2,
                 {10,{fun beh_trees:alt_behaviours/2,[
                     {fun beh_trees:loop/2,
                         {always,{fun beh_trees:seq_behaviours/2,[
                             {fun beh_trees:action/2,{move_to,{xA,yA}}},
                             {fun beh_trees:action/2,{move_to,{xB,yB}}}
                         ]}}
                     },
                     {fun beh_trees:action/2,{pursue,{thief,10}}},
                     {fun beh_trees:alt_behaviours/2,[
                         {fun beh_trees:condition/2,{false,{fun beh_trees:action/2,{move_to,{xB,yB}}}}},
                         {fun beh_trees:condition/2,{true,{fun beh_trees:action/2,{move_to,{xA,yA}}}}}
                     ]}
                 ]} }
             }.

Our example tree will loop several times through the following routine:

  • First, the agent will go from A to B until this is no longer possible or acceptable (in our case, we consider that spotting a thief makes this behaviour fail). How we go from A to B is not important for the behaviour tree: a search algorithm such as A* or steering algorithms can provide the low level motor actions.
  • The agent will then pursue the “thief” (assuming the moving behaviour only stops due to spotting a thief), until this is no longer possible. Maybe the thief runs too much for some time, or the thief just disappears from sight.
  • Lastly, the agent will move to B if it is closer to B than to A (we will consider this condition to be false in our example) or to A otherwise. From there it will start again.

The Engine

To simulate an existing engine, we’ll use a simple list of “response events” which will be sent with no analysis of the action sent. Of course, this means that we know the behaviour beforehand, but, after all, this is just an example:

loop_responder(EventList) when length(EventList)>0 ->
    receive
        {init, Sender} ->
            loop_responder(Sender, EventList, [])
    end.
loop_responder(Sender, [], EventList) ->
    loop_responder(Sender, EventList, []);
loop_responder(Sender, [Event|Events], NextEvents) ->
    io:format("Current: ~p - Next: ~p~n", [[Event|Events], NextEvents]),
    receive after 2000 -> ok end,
    receive
        Action = {action, _ActionType, _ActionData} ->
            io:format("Receive: ~p~n", [Action]),
            io:format("Send: ~p~n", [Event]),
            Sender ! Event
    end,
    loop_responder(Sender, Events, NextEvents ++ [Event]).

The event list that will be traversed by the loop engine will be defined as:

EventList2=[{event, success},
            {event, success},
            {event, success},
            {event, fail,seen_something},
            {event, fail,agent_escaped},
            {event, success}].

This auxiliary function will allow us to initialize the engine with the behaviour agent:

exec_beh_w_init(Engine,{FirstBeh, FirstParams}) ->
    Engine ! {init, self()},
    FirstBeh(Engine, FirstParams).

Testing, Finally!!!

Let’s see how our agent will fare against the “world”:

(juggerlnaut1@azathoth)58> Engine = spawn(beh_trees,loop_responder,[EventList2]).
<0.122.0>
(juggerlnaut1@azathoth)59> Agent = spawn(beh_trees,exec_beh_w_init,[Engine, BehaviourTree]).
Current: [{event,success},
          {event,success},
          {event,success},
          {event,fail,seen_something},
          {event,fail,agent_escaped},
          {event,success}] - Next: []
<0.124.0>
(juggerlnaut1@azathoth)60>
Receive: {action,move_to,{xA,yA}}
Send: {event,success}

Current: [{event,success},
          {event,success},
          {event,fail,seen_something},
          {event,fail,agent_escaped},
          {event,success}] - Next: [{event,success}]
Receive: {action,move_to,{xB,yB}}
Send: {event,success}

Current: [{event,success},
          {event,fail,seen_something},
          {event,fail,agent_escaped},
          {event,success}] - Next: [{event,success},{event,success}]
Receive: {action,move_to,{xA,yA}}
Send: {event,success}

Current: [{event,fail,seen_something},
          {event,fail,agent_escaped},
          {event,success}] - Next: [{event,success},
                                    {event,success},
                                    {event,success}]
Receive: {action,move_to,{xB,yB}}
Send: {event,fail,seen_something}

Current: [{event,fail,agent_escaped},{event,success}] - Next: [{event,success},
                                                               {event,success},
                                                               {event,success},
                                                               {event,fail,
                                                                seen_something}]
Receive: {action,pursue,{thief,10}}
Send: {event,fail,agent_escaped}

Current: [{event,success}] - Next: [{event,success},
                                    {event,success},
                                    {event,success},
                                    {event,fail,seen_something},
                                    {event,fail,agent_escaped}]
Receive: {action,move_to,{xA,yA}}
Send: {event,success}

We can see that our agent is capable of going from A to B (if the underlying engine provides the means to do so), of handling the unexpected event of seeing a thief, of pursuing the thief (again, using e.g. a steering algorithm), and of going back to its patrol waypoints when it loses sight of the thief. Not bad for a 2-hour agent!!!

Last Words

Of course, this is a very simplistic example. A much more detailed entity model would be necessary (e.g., a spotted agent is not necessarily a “thief”), and the low level motor and sensory components would still be missing. But this example shows how one can use Erlang to very easily write and test complex, high-level behaviour trees.

Leave a Reply

Your email address will not be published. Required fields are marked *