AI: Behavior trees

In this tutorial, I would like to discuss a design paradigm known as "behavior trees". Generally speaking, behavior trees are less prone to bugs then finite state machines and more accessible to non-programmers.

Atomic goals

To begin with, we want to break down the goals of our AI system into a limited set of specific tasks. For an action game, these core tasks (called atomic goals) would be primarily concerned with moving and rotating objects. You can even have goals for animation and graphic effects. The general rule of thumb is that the total number of atomic goals must be finite. The aim is to reuse the code, instead of writing a different AI class for each enemy type in your game.

Let's look at a simple example.

MoveTo = {}

function MoveTo:Create(x, y, speed)
  local goal = {}
  setmetatable(goal, { __index = MoveTo })
  goal.x = x
  goal.y = y
  goal.speed = speed
  return goal
end
function MoveTo:Destroy()
  self.x = nil
  self.y = nil
  self.speed = nil
end
function MoveTo:Process(dt, owner)
  local dx = self.x - owner.x
  local dy = self.y - owner.y
  local dist = math.sqrt(dx*dx + dy*dy)
  local eta = dist/self.speed
  if eta < dt then
    owner.x = self.x
    owner.y = self.y
    return "completed", eta
  end
  local step = self.speed*dt
  owner.x = owner.x + dx/dist*step
  owner.y = owner.y + dy/dist*step
  return "active", dt
end

Each goal has a "Process" function that tries to complete its objective during the alloted time step. The "Process" function returns a status code which describes if the goal has been completed, has failed or is still active. This status code is important since it affects which goal from the behavior tree is processed next. In this example, the returned status code is either "active" or "completed". This might vary for other types of goals. The second return value is the amount of time required to complete the goal. Knowing this time is useful because some goals may be completed mid-frame while other goals may be processed for several frames.

Composite goals

Sequence
There are several types of composite goals. The "Sequence" goal allows you to execute several sub-goals in succession. After each sub-goal is completed, the sequence moves to the next sub-goal. Each sub-goal returns the exact time required for its completion and the remaining amount of time is passed to the next sub-goal. The sequence is completed once all of its sub-goals have completed. Unless you set the "loop" parameter, in which case the sequence will continue processing its sub-goals in a loop.

function Sequence.Create(loop)
  local goal = {}
  setmetatable(goal, { __index = Sequence })
  goal.goals = {}
  goal.loop = loop
  goal.active = 0
  return goal
end
function Sequence:Destroy()
  self:PopAll()
  self.goals = nil
  self.loop = nil
  self.active = nil
end
function Sequence:Push(goal)
  table.insert(self.goals, goal)
end
function Sequence:PopAll()
  while #self.goals > 0 do
    local last = table.remove(self.goals)
    last:Destroy()
  end
  self.active = 0
end
function Sequence:Process(dt, owner)
  -- no sub-goals
  if #self.goals == 0 then
    return "inactive", 0
  end
  -- activate
  if self.active == 0 then
    self.active = 1
  end
  -- process sub-goals
  local status = "active"
  while dt > 0 do
    -- process active goal
    local goal = self.goals[self.active]
    local used = 0
    status, used = goal:Process(dt, owner)
    dt = dt - used
    if status ~= "completed" then
      break
    end
    -- next goal in queue
    self.active = self.active + 1
    if self.active > #self.goals then
      -- sequence is complete
      if self.loop ~= true then
        status = "completed"
        break
      end
      self.active = 1
    end
  end
  -- deactivate
  if status ~= "active" then
    self.active = 0
  end
  return status, dt
end
Note that there is an issue with the code above. Sequences may possibly get into an infinite loop when all of the sub-goals complete immediately. One option is to make sure the sequence doesn't loop more than once, in case all of its sub-goals are completed immediately.

Selector
Sequences are pretty handy although they interrupt as soon as one of the sub-goals fail. This is why we also need "Selectors". Selectors are similar to sequences, except that when one of their sub-goals fails they move onto the next. Selectors are completed as soon as one of their sub-goals is completed.

Parallel
In addition to sequences and selectors there is also the "Parallel". A parallel allows you to run several goals simultaneously. For example, a parallel can be used to animate and move a sprite at the same time. With Lua, the implementation would probably be based on preemptive multi-tasking, but the results will look simultaneous.

GoalLoopCompletedFailed
Sequence false when all sub-goals complete when any sub-goal fails
 true never

Selector false when any sub-goal completes when all sub-goals fail
 true never

Parallel false when all sub-goals complete when any sub-goal fails
 true never

Conditional goals

Using sequences and selectors you can easily model the behavior of NPCs in your game. Without input however, the NPC can only move blindly in predefined patterns. To make their behavior more clever, we need to introduce "conditional" goals. Conditional goals poll the environment to see if a particular condition is true. Depending on the state of the game, each conditional goal returns a corresponding status code. We can use this approach to check for a variety of conditions, for example:
"IsInRange" - checks if some object is in the vicinity of the NPC
"IsTouching" - checks if some object is colliding with the NPC
"IsFacing" - checks if some object is in the line of sight of the NPC

Unconditional goals

With larger behavior trees, it's useful to add a couple of hard-coded goals such as "Fail" and "Complete". These goals simply return a status code which will allow you to control the "execution flow" of the behavior tree.

Messaging and events

The primary way in which our AI-controlled objects can interact with each other is through messaging. Messages that are passed between objects are basically strings. For example, if a bullet hits another object it would send out a "shot" message. If the receiving object happens to be an "enemy" it would react by destroying itself. Notice that messages are not handled by the object itself but by its currently active goal. Therefore, if the enemy is already "dead", it wouldn't react to another "shot" message. To implement a fully working messaging system we would need a few utility functions. First off, objects have to be indexed and accessed somehow so that we can send messages to a specific receiver by its ID.

Simple example

For the purposes of this tutorial, I have combined some of the above-mentioned goals into a small module called "ai.lua". Let's test the module using the script below. The code shouldn't be too hard to understand. We create ten unique sprites and move them all counterclockwise in a square-shaped pattern. The movement pattern is defined as a sequence with four "MoveTo" sub-goals. Since the loop parameter for the sequence is set to "true" the sprites keep following the path forever.

-- include the ai module
ai = dofile ( "Tutorials/ai.lua" )

display:create ( 'AI', 800, 600, 32, true )

-- list of all the sprites
sprites = {}

-- create sprites and move them in a square pattern
for i = 1, 10, 1 do
  local sequence = ai.Sequence ( true )
  sequence:Push ( ai.MoveTo ( 100, 100, 150 ) )
  sequence:Push ( ai.MoveTo ( -100, 100, 150 ) )
  sequence:Push ( ai.MoveTo ( -100, -100, 150 ) )
  sequence:Push ( ai.MoveTo ( 100, -100, 150 ) )

  local sprite = Sprite ( i * 50 + 100, 100 )
  sprite.canvas:circle ( 5 )
  sprite.canvas:fill ( )
  sprite.goal = sequence
  display.viewport:add_child ( sprite )
  table.insert ( sprites, sprite )
end

-- update sprite goals
timer = Timer ( )
timer:start ( 16, true )
timer.on_tick = function ( timer )
  local seconds = timer:get_delta_ms ( ) / 1000
  for i, v in pairs ( sprites ) do
    if v.goal then
      local status = v.goal:Process ( seconds, v )
      if status ~= "active" then
        v.goal:Destroy ( )
        v.goal = nil
      end
    end
  end
end
Download:  ai.lua
ai_example.lua