Behavior Tree

Recently, I have been utterly intrigued by behavior trees. I have always been struck by how difficult it is to design and tweak entity behaviors using finite state machines. I have been using nested state machines in previous projects and it is always a pain when there are changes in the game flow even when it is just small menu changes. After reading about the advantages of easy to design decision flow and reusable actions/conditions in some articles online, I decided to try and implement something simple to test it out.

Firstly, I guess we need an enum of behavior status to handle.

public enum BehaviorStatus
{
 Pass,
 Fail,
 Running,
 Error
}

The behavior base class.

public abstract class Behavior 
{
 /// The parent behavior
 public Behavior Parent { get; private set; }

 /// The children behaviors
 public List  Children = new List  ();

 /// The index of the active behavior
 protected int activeBehaviorIndex = -1;
  
 /// Add child and make sure parents are set up.
 public void AddChildBehavior (Behavior child)
 {
  child.Parent = this;
  Children.Add (child);
 }
 
 /// Process Behavior logic and return status.
 public virtual BehaviorStatus Decide ()
 {
  return BehaviorStatus.Pass;
 }
 
 /// Resets active status of self and children
 public void ResetActiveBehavior ()
 {
  if (-1 != activeBehaviorIndex)
  {
   Children [activeBehaviorIndex].ResetActiveBehavior ();
   activeBehaviorIndex = -1;
  }
 }
}

A selector which is a list of behaviors that are tried one after the other until one succeeds.

public class Selector : Behavior 
{
 public override BehaviorStatus Decide ()
 {
  BehaviorStatus status = BehaviorStatus.Fail;
  
  for (int i = 0; 
       i < (activeBehaviorIndex == -1 ? Children.Count : activeBehaviorIndex + 1); 
       ++i)
  {
   status = Children [i].Decide ();
   
   // Error,
   Debug.Assert (BehaviorStatus.Error != status, "Error status in Priority.");
   
   if (BehaviorStatus.Running == status)
   {
           // Running, Store active behavior
    activeBehaviorIndex = i;
    return status;
   }
   else
   {
           // Not running, Reset active behavior and their active children
    ResetActiveBehavior ();
   }

   // Pass, Stop looking for behavior
   if (BehaviorStatus.Pass == status)
   {
    return status;
   }
         
   // Fail, try another one.
  }
  
  // Fail, Everything
  return status;
 }
}

A sequence is a list of behaviors that are run one after another.

public class Sequence : Behavior 
{
 public override BehaviorStatus Decide ()
 {
  BehaviorStatus status = BehaviorStatus.Fail;
  
  // Start making decision from the active index
  for (int i = (activeBehaviorIndex == -1 ? 0 : activeBehaviorIndex); 
       i < Children.Count; 
       ++i)
  {
   status = Children [i].Decide ();
   
   // Error,
   Debug.Assert (BehaviorStatus.Error != status, "Error status in Sequence.");
  
   if (BehaviorStatus.Running == status)
   {
              // Running, Store active behavior
    activeBehaviorIndex = i;
    return status;
   }
   else
   {
           // Not running, Reset active behavior and their active children
    ResetActiveBehavior ();
   }

   // Fail, Stop execution
   if (BehaviorStatus.Fail == status)
   {     
    return status;
   }
     
   // Pass, continue execution
  }
    
  return status;
 }
}

Example condition and action.

public class ExampleCondition : Behavior 
{
 public override BehaviorStatus Decide ()
 {
  // Check condition
                if (true)
                {
                    return BehaviorStatus.Pass;
                }

  return BehaviorStatus.Fail;
 }
}

public class ExampleAction : Behavior 
{
 public override BehaviorStatus Decide ()
 {
  // Check for any problems
                if (true)
                {
                    return BehaviorStatus.Fail;
                }

                // Check if action finished
                if (true)
                {
                    return BehaviorStatus.Pass;
                }

                // Do action

  return BehaviorStatus.Running;
 }
}

An example of how it is all setup

// Setup
Selector root = new Selector ();  

Sequence talkToPlayer = new Sequence ();
Condition checkIfNearPlayer = new Condition ();
Action walkToPlayer = new Action ();
Action startConverstationWithPlayer () = new Action ();
Action walkAwayFromPlayer = new Action ();

Sequence chaseRatsAway = new Sequence ();
Condition checkIfNearRat = new Condition ();
Action chaseRat = new Action ();

Action wander = new Action ();

root.AddChildBehavior (talkToPlayer);
talkToPlayer.AddChildBehavior (checkIfNearPlayer);
talkToPlayer.AddChildBehavior (walkToPlayer);
talkToPlayer.AddChildBehavior (startConverstationWithPlayer);
talkToPlayer.AddChildBehavior (walkAwayFromPlayer);

root.AddChildBehavior (chaseRatsAway);
chaseRatsAway.AddChildBehavior (checkIfNearRat);
chaseRatsAway.AddChildBehavior (chaseRat);

root.AddChildBehavior (wander);

// Update
root.Decide ();

This works for now but I am sure there are better ways of setting up the behavior tree. Maybe with an editor or xml. I think I would also want to improve the way I am tracking the running behaviors by putting them into a queue.

Tile based space partitioning

I needed a way to split the world into tiles so that an entity can quickly find other entities nearby.

The tile node contains the entities in categories and a list of waypoint ids.

public class TileNode 
{    
    /// Contains a list of entities in this tile node    
    public List  [] EntitiesInNode;    

    /// Contains a list of waypoint ids in this quad tree node    
    public List  WaypointsInNode = new List  ();    
    
    public TileNode (int entityGroupCount)     
    {        
        EntitiesInNode = new List  [entityGroupCount];        
        
        for (int i = 0; i < entityGroupCount; ++i)        
        {            
            // reserve 20 entities             
            EntitiesInNode [i] = new List  (20);        
        }    
    }
}

The system holds the tiles and splits the world into grids. Notice that the members are static because there is supposed to be only one instance of this system anyway.

public class TilePartitioningSystem : MonoBehaviour 
{
    /// Size of a single tile
    public static float TileSize { get; private set; }

    /// Total size of the world
    public static float WorldSize { get; private set; }

    /// How many squares on the side
    public static int TileRowCount { get; private set; }

    /// Nodes in the quad tree
    public static TileNode [] Tiles;

    public static void InitializeTilePartitioningSystem (int tileRowCount, float worldSize, int entityGroupCount)
    {
        Debug.Assert (1 < tileRowCount, "Invalid tileRowCount");
        Debug.Assert (0 < worldSize, "Invalid worldSize");

        TileRowCount = tileRowCount;

        TileSize = worldSize / tileRowCount;

        WorldSize = worldSize;

        Tiles = new TileNode [TileRowCount * TileRowCount];

        for (int i = 0; i < Tiles.Length; ++i)
        {
            Tiles [i] = new TileNode (entityGroupCount);
        }

        // Store waypoints in respective tiles
        for (int i = 0; i < WaypointSystem.Waypoints.Length; ++i )
        {
            WaypointBehaviour waypoint = WaypointSystem.Waypoints [i];

            int tileIndex = TilePartitioningSystem.GetTileIndex (waypoint.gameObject.transform.position);

            Tiles [tileIndex].WaypointsInNode.Add (i);
        }
    } 

    public static int GetTileIndex (Vector3 position)
    {
        return (int) (position.x / TileSize) + ((int) (position.z / TileSize) * TileRowCount);
    }

    public static int GetTileIndex (float x, float z)
    {
        return (int) (x / TileSize) + ((int) (z / TileSize) * TileRowCount);
    }

We need ways to add and remove a moving entity from the tiles.

/// Add an entity to the tile.
public static void AddEntityToTile (int tileIndex, int entityGroup, GameObject entity)
{
    Debug.Assert (0 <= tileIndex && tileIndex < Tiles.Length, "Out of range:" + tileIndex);
    Debug.Assert (0 <= entityGroup && entityGroup < Tiles [tileIndex].EntitiesInNode.Length, "Invalid entityGroup:" + entityGroup);
    Debug.Assert (null != entity, "AddEntityToTile:null entity");
  
    Tiles [tileIndex].EntitiesInNode [entityGroup].Add (entity);
}

public static void RemoveEntityFromTile (int tileIndex, int entityGroup, GameObject entity)
{
    Tiles [tileIndex].EntitiesInNode [entityGroup].Remove (entity);
}

We need a way to get a list of the nearby tiles. Tiles in the corners or on the last/first rows will have fewer neighbors.

public static void GetNearbyTiles (ref List  nearbyTiles, int tileIndex)
{
    // Add start tile
    nearbyTiles.Add (tileIndex);
  
    // Determine edges of tile
    bool notFirstRow = tileIndex >= TileRowCount,
     notLastRow = tileIndex < (Tiles.Length - TileRowCount),
            notFirstColumn = 0 != (tileIndex % TileRowCount),
     notLastColumn = (TileRowCount - 1) != (tileIndex % TileRowCount);
  
    // Add surrounding tiles
    // Add tile below
    if (notFirstRow)
    {   
        nearbyTiles.Add (tileIndex - TileRowCount);
    }
    // Add tile above
    if (notLastRow)
    {
        nearbyTiles.Add (tileIndex + TileRowCount);
    }
    // Add tile on the left
    if (notFirstColumn)
    {
        nearbyTiles.Add (tileIndex - 1);
    }
    // Add tile on the right
    if (notLastColumn)
    {
        nearbyTiles.Add (tileIndex + 1);
    }
    // Add tile on the bottom right
    if (notFirstRow && notLastColumn)
    {
        nearbyTiles.Add (tileIndex - TileRowCount + 1);
    }
    // Add tile on the bottom left
    if (notFirstRow && notFirstColumn)
    {
        nearbyTiles.Add (tileIndex - TileRowCount - 1);
    }
    // Add tile on the upper left
    if (notLastRow && notFirstColumn)
    {
        nearbyTiles.Add (tileIndex + TileRowCount - 1);
    }
    // Add tile on the upper right
    if (notLastRow && notLastColumn)
    {
        nearbyTiles.Add (tileIndex + TileRowCount + 1);
    }
}

Finally, the entity updates itself in the TilePartitioningSystem when it moves.

int newTileIndex = TilePartitioningSystem.GetTileIndex (gameObject.transform.position);

// Update tile index
if (newTileIndex != entityData_.QuadTreeIndex)
{
    TilePartitioningSystem.RemoveEntityFromTile (entityData_.QuadTreeIndex, (int) entityData_.EntityGroup, gameObject);

    entityData_.QuadTreeIndex = newTileIndex;

    TilePartitioningSystem.AddEntityToTile (entityData_.QuadTreeIndex, (int) entityData_.EntityGroup, gameObject);
}

So if an entity wants to find the other entities of a certain category nearby they just check the TilePartitioningSystem like this:

TileNode tile = TilePartitioningSystem.Tiles [entityData.QuadTreeIndex];

The obligatory Hello World.

Fadzuli.said ("Hello World.");

Welcome to my game development blog. Here I wish to share the stuff that I pursue and the thoughts that occur to me whilst I level up in this career that I have chosen.