Behavior Tree

I have been experimenting with behavior trees for a bit now, always finding I am over complicating things or that I did not prepare to solve all my needs with them, but the potential exists.

Right now I am working on a flash game along side an artist (I am so glad I don't have to draw) and I implemented an straight forward almost component like behavior system, such as "I give you the draw behavior, therefore you draw".

This was great to start, I didn't put too much thought into it and I ended creating some pretty cool behaviors, like interpolations (much like the tween class in Unity, but not as huge, of course), recycling routines, click events, functions proxy (Delegate like things, but in As3), collision responses, sequences, etc.

The problem was there was no stop at some behavior, once the entity got the behavior there was no way to stop the behavior from happening, since there was no real condition evaluation unless I went out of my way and filled the behavior with possibilities within its routine (which is dirty).

So I created 2 supporting templates that would work together to make my behaviors only fire when the conditions apply.

First, I created a "BaseCondition":

public class BaseCondition implements IBehavior
 {
  static var Head:BaseCondition;
  var Next:BaseCondition;
  var Self:BaseCondition;

The first part explains that this class is the type of IBeahvior (To comply with my Entity IBehavior collection, and to not disturb what was already in place and working properly).

The Head, Next and Self are the elements used to keep this class pooled, if you would like to know more about it please check my previous post here

The IBehavior interface contains 2 functions, Update():void and Recycle():void, pretty simple.

var Condition:ICondition;
  
  public var TrueConditions:Vector.<BaseCondition>
  public var FalseConditions:Vector.<BaseCondition>
  
  public var TrueActions:Vector.<IBehavior>
  public var FalseActions:Vector.<IBehavior>
  
  public function BaseCondition()
  {
   Self = this;
   TrueConditions = new Vector.<BaseCondition>();
   FalseConditions = new Vector.<BaseCondition>();
   TrueActions = new Vector.<IBehavior>();
   FalseActions = new Vector.<IBehavior>();
  }

Then we have a field for the condition, this condition is what makes the base condition unique, depending on this ICondition we will be able to tell what we are looking for, such as "Is this element inside the view frustum?".

Then we have 4 collections, one for the true branch (in case the condition is true, follow up with these conditions), another for the false conditions and 2 more of the true and false actions, meaning that depending on the residing condition in this base condition we will execute either the actions in the true collection or in the false collection, this proves to be very useful as you start evolving your behaviors.

Coming next we have the factory patterns I use, they are essentially the same with one another except for a small difference, this is done for convenience when creating behaviors (to avoid a mess of having to create things, link them and then reuse them).

public static function Create(Condition:ICondition):BaseCondition
  {
   var Vessel:BaseCondition;
   if (Head != null)
   {
    Vessel = Head;
    Head = Head.Next;
   }
   else
   {
    Vessel = new BaseCondition();
   }
   
   Vessel.Condition = Condition;
   
   return Vessel;
  }
  
  public static function CreateRoot(Owner:Entity, Condition:ICondition):BaseCondition
  {
   var Vessel:BaseCondition;
   if (Head != null)
   {
    Vessel = Head;
    Head = Head.Next;
   }
   else
   {
    Vessel = new BaseCondition();
   }
   
   Vessel.Condition = Condition;
   Owner.BehaviorList.push(Vessel);
   
   return Vessel;
  }
  
  public static function CreateTrueBranch(PreviousBranch:BaseCondition, Condition:ICondition)
  {
   var Vessel:BaseCondition;
   if (Head != null)
   {
    Vessel = Head;
    Head = Head.Next;
   }
   else
   {
    Vessel = new BaseCondition();
   }
   
   Vessel.Condition = Condition;
   PreviousBranch.TrueConditions.push(Vessel);
   
   return Vessel;
  }
  
  public static function CreateFalseBranch(PreviousBranch:BaseCondition, Condition:ICondition)
  {
   var Vessel:BaseCondition;
   if (Head != null)
   {
    Vessel = Head;
    Head = Head.Next;
   }
   else
   {
    Vessel = new BaseCondition();
   }
   
   Vessel.Condition = Condition;
   PreviousBranch.FalseConditions.push(Vessel);
   
   return Vessel;
  }

There's nothing really special to tell, if the factory pattern is not really clear to you please read my last post, there I explain my pool system and the factory pattern used in it.

public function Update():void
  {
   if (Condition.CheckCondition())
   {
    var count:int = TrueActions.length;
    for (var i:int = 0; i < count; i++)
    {
     TrueActions[i].Update();
    }
    
    count = TrueConditions.length;
    for (var i:int = 0; i < count; i++)
    {
     TrueConditions[i].Update();
    }
   }
   else
   {
    var count:int = FalseActions.length;
    for (var i:int = 0; i < count; i++)
    {
     FalseActions[i].Update();
    }
    
    count = FalseConditions.length;
    for (var i:int = 0; i < count; i++)
    {
     FalseConditions[i].Update();
    }
   }
  }

And here we have the heart of this behavior tree, where we check the condition and depending on the outcome we will either do the true reaction or false reaction, and follow the proper path in the behavior.

public function Recycle():void
  {
   Next = Head;
   Head = Self;
   
   var count:int = TrueActions.length;
   for (var i:int = 0; i < count; i++)
   {
    TrueActions[i].Recycle();
   }
   
   count = TrueConditions.length;
   for (var i:int = 0; i < count; i++)
   {
    TrueConditions[i].Recycle();
   }
   
   count = FalseActions.length;
   for (var i:int = 0; i < count; i++)
   {
    FalseActions[i].Recycle();
   }
   
   count = FalseConditions.length;
   for (var i:int = 0; i < count; i++)
   {
    FalseConditions[i].Recycle();
   }
   
   TrueActions.length = 0;
   FalseActions.length = 0;
   TrueConditions.length = 0;
   FalseConditions.length = 0;
  }
 
 }

Finally we have our recycle method, pretty essential to my system, we have to make sure to recycle absolutely every single behavior and condition, for reuse. And this concludes the BaseCondition, it is not complicated but we haven't really seen it in action, in order to make this work we require a "ICondition" as well as another "IBehavior" to append to one of the action branches, let's start with the condition:

public class Con_CollidedWith implements ICondition
 {
  static var Head:Con_CollidedWith;
  var Next:Con_CollidedWith;
  var Self:Con_CollidedWith;
  
  var Target:PhysicsComponent; //Contains all the physics info.

  
  public function Con_CollidedWith()
  {
   Self = this;
  }
  
  public static function Create(Target:PhysicsComponent):Con_CollidedWith
  {
   var Vessel:Con_CollidedWith;
   if(Head != null)
   {
    Vessel = Head;
    Head = Head.Next;
   }
   else
   {
    Vessel = new Con_CollidedWith();
   }
   
   Vessel.Target = Target;

   return Vessel;
  }

This is pretty much the same pattern I follow for almost everything that requires to be pooled, in there you can see an object of type of "PhysicsComponent", in there I store variables that represent the entity in the physical world, such as position, body type (Rectangle, poly, circle, etc), a collision list, etc.

  public function CheckCondition():Boolean
  {
   return Target.CollisionList.length > 0;
  }
  
  
  public function Recycle():void
  {
   Next = Head;
   Head = Self;
  }
  
 }

Finally we have the CheckCondition (which is part of the ICondition interface) where I test the condition at hand, in this case if we have something in our collision collection (meaning we have collided with something in the collision phase) it will return true, otherwise false. That concludes an example of a condition, you can create all sort of conditions, you can test if an enemy has certain amount of HP, or if a button has been clicked, etc. Now we move to the last piece of the puzzle, the Action, for this example I will use a function proxy action:

public class Act_ExecuteFunction implements IBehavior
 {
  static var Head:Act_ExecuteFunction;
  var Next:Act_ExecuteFunction;
  var Self:Act_ExecuteFunction;
  
  var Execute:Function;
  
  public function Act_ExecuteFunction()
  {
   Self = this;
  }
  
  public static function Create(Execute:Function):Act_ExecuteFunction
  {
   var Vessel:Act_ExecuteFunction;
   if(Head != null)
   {
    Vessel = Head;
    Head = Head.Next;
   }
   else
   {
    Vessel = new Act_ExecuteFunction();
   }
   
   Vessel.Execute = Execute;
   
   return Vessel;
  }
  
  public function Update():void
  {
   Execute.call();
  }
  
  
  public function Recycle():void
  {
   Execute = null;
   Next = Head;
   Head = Self;
  }
  
 }

As you can see in our Update function (this will only get called if the condition fell in the action branch where this action resided in) we call the function we appended to this action, much like a delegate. But we still don't know how to put all of this together, so allow me to make an example, in my current game there is "Honey" in the air and you require to collide with it in order to acquire it, here is how I make a honey:

public static function CreateHoneyItem(X:Number, Y:Number):void
  {
   var Honey:Entity = Entity.Create(World.InGameGroup);
   var Graphics:GraphicsComponent = GraphicsComponent.Create(Honey, AnimationLibrary.HONEY_GRAPHICS);
   var Physics:PhysicsComponent = PhysicsComponent.Create(Honey, X, Y, PhysicsComponent.ITEM);
   Physics.TurnIntoCircle(16);
   
   var Drawer:B_Draw = B_Draw.CreateOwnerless(1, Graphics, Physics); //gets recycled upon collision by the honey collision response
   
   var Condition_Collision:BaseCondition = BaseCondition.CreateRoot(Honey,Con_CollidedWith.Create(Physics));
   Condition_Collision.TrueActions.push(Act_ExecuteFunction.Create(HoneyCollisionResponse));

}

public static function HoneyCollisionResponse():void
{
    //Do your response here
}

So in order to make a honey I call the factory method for the honey, this will create a honey, and give it's behavior. The behavior says that it will Draw (B_Draw), Also says that if the honey collides with something then execute the function proxy (HoneyCollisionResponse).

There's more behind the scene, such as the collision system, the render system, etc, but it is not hard to get the idea on how the behavior tree works. Using this you can come up with all sort of complex behaviors, but the main issue with this is that they are inflexible upon creation, there won't be learning of AI, it will just run the routine over and over, but that doesn't have to be that way, there are methods to make this work the way you want to, implementing weight based decisions instead of just conditionals could be a way, there's a lot of things that can be implementing using this Behavior Tree pattern, but that would be another post for another time.

My Factory Design Pattern

I will talk a bit about how I create my "Game objects".

The first thing you need to know is that I do not use the keyword "New" to instantiate a new object, this is because I need to have control over my game objects (coming from the pools), Let's create a quick example, I am going to assume that you know about my pool system, but if you don't please take a look at the previous post.

We will start with the body of the class.

public class Slime: PooleanNode<Slime> 
{
    static LinkedPoolean<Slime> Pool = new LinkedPoolean<Slime>();

    public Slime()
    {
    }
}

Here we have declared a "Slime class" that can be pooled with my pool class, as you can see the constructor is public so we can instantiate them with the activator class, also there's a static pool of slimes living inside this class, this will mean that in every single slime object you will have access to the same pool, this is important cause all the slimes need to come from the pool, now moving into the "creational" method.

public static Slime Create() //this function must live inside the slime class.
{
    Slime Vessel;
    Pool.Get(out Vessel); //if it doesn't live inside the class, the pool wouldn't be
    return Vessel;        //visible, you would have to make it public and access it
}                         //like "Slime.Pool", I don't recommend that. 

And done, we have create an static method that will take slimes out of the pool and return them, simple as that! now for some logic on why I do this, by making a new slime this way I make sure they come from the pool and that they are not generated outside of the pool, this is handy when we want to manage them and when we want to avoid tasking the garbage collector, since we are not allocating new memory.

Now let's expand on it, to make it useful, you can declare multiple creation methods to obtain different results, let's say that the Slime has some fields like position or maybe current hit points, etc, we can modify these elements like this:

public class Slime: PooleanNode<Slime> 
{
    static LinkedPoolean<Slime> Pool = new LinkedPoolean<Slime>();

    Vector2 Position;
    int HP;

    public Slime()
    {
        Position = Vector2.Zero;
        HP = 1;
    }

    public static Slime Create(Vector2 Position, int HP) 
    {
        Slime Vessel;
        Pool.Get(out Vessel); 
        Vessel.Position = Position;
        Vessel.HP = HP;
        return Vessel;       
    } 
}

By default the slime starts at position 0,0 and with 1 HP, but we can create any slime anywhere we want as well as giving it any amount of HP we want, we can create more methods to define things ever further.

Lastly I define a recycle method that I use when I need to get rid of the object and sent it back to the pool, like this:

public void Recycle()
{
    Pool.ReturnPoolable(this);
}

That makes sure that the object is sent back into the pool to be reused by the factory method, this is an overly simplified version of what I use in my current game, if you would like to check the game out, here:

Game

Thanks for reading!

Entity Label vs Entity Object.

Looking back at the things that moved me into trying this new system, and what was keeping me in object oriented programming, I can safely say that there's good and bad on both of this two designs.

Taking the best out of something and merging it with the best out of something else usually results in interesting outcomes, this is one of those cases.

Inheritance is such a powerful tool, the beauty of inheritance is that allows us to create new objects from already existing objects, they encapsulate all the old goodness (sometimes not so good) plus the new functionality. This makes it easy when sorting classes from their bases, such a list of base classes, but in reality is a list of a lot of different classes that derive from one, in my opinion, virtual functions are fantastic when we wanted to modify behaviors, or when giving special instructions to derived classes, etc, all this was the beauty of Inheritance, but it soon became a mess when adding more classes on top of classes, going from base to base modifying things in order to allow some general implementation.

Still there was plenty of good in the Inheritance pattern, and this is why while coding this new Entity system engine I decided to think over if I wanted to do labels entities or object entities.

When it comes to memory usage, making entities as labels sounds like the way to go, simply because there was no need to allocate memory for a new object to be placed, making objects that hold data from data that is already in memory might sound silly, at least in this case.

An Entity label is just a tag, nothing almost, but it requires some management, to live in some sort of collection, and this sometimes could be hard to debug because you are meant to have many labels with many different components in them, maybe this is not the case when it comes to MMOs but I can't speculate since I have no experience on them.

I am taking all this and putting it into the things I do, making game engines for local usage. Making an Entity object allows you to do simple things such as "register" it by itself to your self managed Factory, also, entities will have the advantage of being able to have minimal but useful implementation, such as cloning themselves, resetting values to default(why this is a good idea, coming up), etc.


Single Inheritance (double in C#, since everything inherits from "object" by default) was the pretty balance I wanted, objects that require a single base class to work with anything, nothing else, no more complicated hierarchies, just one base, multiple outcomes, another base, other multiple outcomes.

Looking at the core design of the Entity System, we have... labels (Entities) which are not objects, systems (meddle with the components), and the components themselves, besides some managers making sure things work smooth, such as the game manager, system manager, component managers maybe? etc.

To not have Inheritance made me feel like I couldn't be flexible when coding and linking all these elements together, I started to ponder if this was because I was used to OOP or because I didn't quite understand just yet what an Entity system was, soon after I decided to not really pay attention to this and just went and said "what's good in OOP, and what's good in ES".

In with inheritance, I made base classes for my most basics objects, base entities, base systems, base components, I could finally start doing some more than just thinking about the design and why I wanted to stay away from inheritance and just embraced what felt good and natural.

so for the Entities, I wanted to give it a meaning to be an object instead of just a label, so I made sure that this object wasn't just a waste of time, but rather a useful way to manage all my entities and to make it easy to work on them instead of just creating more and more, here's how my entity class looks for now:

public class Entity
    {
        #region fields
        List m_Components = new List();
        List m_AffectingSystems = new List();
        Type m_ThisType = null;

        #endregion

        #region properties
        public List Components { get { return m_Components; } set { m_Components = value; } }
        public Type GetThisType { get { return m_ThisType; } }
        #endregion

        #region constructor

        public Entity(Type thisType)
        {
            m_ThisType = thisType;
        }

        #endregion

        #region methods
        /// 

        /// adds the components into the list, only if the list doesn't contain them already. 
        /// 
        /// 
public void AddComponent(params BaseComponent[] components)
        {
            for (int i = 0; i < components.Count(); i++)
            {
                bool toAdd = true;

                for (int a = 0; a < m_Components.Count; a++)
                {
                    if (m_Components[a].ID == components[i].ID)
                    {
                        toAdd = false;
                    }
                }
                if (toAdd)
                {
                    components[i].Owner = this;
                    m_Components.Add(components[i]);
                }
            }
        }

        //mutual reference, between entity and systems.
        public void AddSystem(params BaseSystem[] systems)
        {
            for (int i = 0; i < systems.Count(); i++)
            {
                if (!m_AffectingSystems.Contains(systems[i]))
                {
                    m_AffectingSystems.Add(systems[i]);
                    systems[i].AddEntity(this);
                }
            }
        }


        /// 

        /// Perform your component resetting here.
        /// 
        public virtual void ResetParameters()
        {

        }


        /// 

        /// once the entity dies, or is not required anymore, it will go back into the pool it came from, that way it can be used again
        /// 
        public void ReturnToFactory()
        {
            ResetParameters();
            for (int i = 0; i < m_AffectingSystems.Count; i++)
            {
                m_AffectingSystems[i].RemoveEntity(this);
            }
            EntityFactory.Return(this);
        }

        #endregion
    }

Being able to make my entity into an object allowed me all of this very basic functionality, something that maybe a manager would have to do if it was just a label, regardless, this class is meant to be inherited as you can tell, that the type of entity is specified in the constructor, take for example this little player class I made for testing which inherits from Entity:

public class Player : Entity
    {
        #region fields

        #endregion

        #region properties
        #endregion

        #region constructors
        public Player()
            : base(typeof(Player))
        {
            Initialize();
        }
        #endregion

        #region methods

        public void Initialize()
        {
            if (this.Components.Count > 0)
            {
                this.Components.Clear();
            }
            else
            {
                //animation portion
                AnimationCO animation = new AnimationCO();
                animation.Texture = TexturePool.GetTexture("Player");
                animation.AddNewAnimation(42, 64, 42, 0, 5, "WalkingDown", 200.0f, 200.0f, 200.0f, 200.0f, 200.0f);
                animation.AddNewAnimation(42, 64, 0, 0, 1, "Idle", 200.0f);
                animation.AddNewAnimation(42, 64, 42, 64, 5, "WalkingLeft", 200.0f, 200.0f, 200.0f, 200.0f, 200.0f);
                animation.AddNewAnimation(42, 64, 42, 128, 5, "WalkingUp", 200.0f, 200.0f, 200.0f, 200.0f, 200.0f);
                animation.AddNewAnimation(42, 64, 42, 192, 5, "WalkingRight", 200.0f, 200.0f, 200.0f, 200.0f, 200.0f);

                //position portion
                PositionCO position = new PositionCO();
                position.Position2D = new Vector2(0.0f, 0.0f);

                //input portion
                InputCO input = new InputCO();
                input.Index = PlayerIndex.One;
                input.AddInput(Buttons.LeftStick, 0.1, PlayerIndex.One, Global.TheActions.MOVE, true);
                input.AddInput(Buttons.A, 0.0, PlayerIndex.One, Global.TheActions.DASH, false, 300.0);
                input.AddInput(Buttons.X, 0.0, PlayerIndex.One, Global.TheActions.RUN, true);

                //action portion
                ActionCO action = new ActionCO();


                this.AddComponent(animation, position, input, action);
            }

        }

        public override void ResetParameters()
        {
            Initialize();
        }

        #endregion
    }

Take in consideration that this Player class is just for testing, but also take a look at some of the things going on, you can tell some of what's happening in the engine by just looking at how my entities are being made, also a quick note, "CO" is what I use for mention "Component". Going back to the simple implementation, thanks to the "ResetParams" we can simply reset the parameters back to it's original form, isn't that useful for re usability? The Initialization can be ignored really, what's important here is that the constructor passes it's own type to the base entity, thanks to this we are going to be able to make new instances of players very easily. "Why..?" Here's the other pretty part of having the Entities as objects, The Entity Factory:

public class EntityFactory
    {
        #region fields
        static EntityFactory m_EntityFactory = null;
        static Dictionary> m_RegisteredEntities = new Dictionary>();
        static ComponentGetter m_PositionGetter = new ComponentGetter();

        #endregion

        #region constructors
        private EntityFactory()
        {

        }
        #endregion

        #region methods

        public static EntityFactory Initialize()
        {
            if (m_EntityFactory == null)
            {
                m_EntityFactory = new EntityFactory();
            }

            return m_EntityFactory;
        }

        #endregion


        #region creational methods

        /// 

        /// creates an entity into the world.
        /// 
        /// 
the type of entity, this type needs to be within the namespace./// 
where in the world you want to create this new entity (applicable only to entities that require position)/// 
which systems are going to affect the entity.

public static void CreateEntity(Type entityType,Vector3 position, params BaseSystem[] theSystems)
        {
            
            //checks if the current type of entity exists in the pool.
            if (m_RegisteredEntities.ContainsKey(entityType))
            {
                //exists in the pool, use it.
                if (m_RegisteredEntities[entityType].Count > 0)
                {
                    Entity CreationalVessel = m_RegisteredEntities[entityType][0];
                    CreationalVessel.AddSystem(theSystems);
                    FixPosition(CreationalVessel, position);
                    m_RegisteredEntities[entityType].Remove(CreationalVessel);
                }
                    //doesn't exist in the pool, make a new one and use it.
                else
                {
                    Entity CreationalVessel = (Entity)Activator.CreateInstance(entityType);
                    CreationalVessel.AddSystem(theSystems);
                    FixPosition(CreationalVessel, position);
                }
            }
            else //if the type of entity doesn't exists, then it will register it and try again.
            {
                Entity vessel = (Entity)Activator.CreateInstance(entityType);
                m_RegisteredEntities.Add(vessel.GetThisType, new List());
                m_RegisteredEntities[vessel.GetThisType].Add(vessel);
                CreateEntity(entityType, position, theSystems);
            }
        }

        /// 

        /// re registers or registers for the first time e
        /// 
        /// 
public static void Return(Entity returnee)
        {
            if (m_RegisteredEntities.ContainsKey(returnee.GetThisType))
            {
                m_RegisteredEntities[returnee.GetThisType].Add(returnee);
            }
            else
            {
                //throw EntityCreatedOutOfWorldException();
            }
        }

        /// 

        /// fixes the position of the Entity only if it contains a position component.
        /// 
        /// 
/// 
public static void FixPosition(Entity entity, Vector3 position)
        {
            PositionCO vessel = m_PositionGetter.GetComponent(entity);
            if (vessel != null)
            {
                vessel.Position3D = position;
            }
        }

        #endregion
    }

As you maybe noticed in the Entity base class, there was this function "return to factory", this is a flyweight design pattern, entities are going to be created only if they need to, at some point you will not require to reallocate memory to make new entities, you will just start using the ones that had been made and use before, even though this is a work in progress (cause at some point we want to limit the amount of objects instantiated at once) it is very functional.

with this design pattern, we don't even need to concern ourselves in run time to allocate the new entities we are using, we just need to create them, give them their rules (the systems) and let them be. if you have to do this "Entity myEntity = new Entity();" somewhere outside the engine, then it will give you problems, or it will simply be ignored, depends on you.

so to the bottom line, for the purpose to have a data driven component engine, I have decided to embrace the minimum basics of object oriented programing, inheritance to it's minimal, so powerful.

Later on I will talk about the base systems and components.