Entity Pooling

Memory allocation in run time can be pretty heavy depending on how much you do it, getting rid of objects every loop will trigger the garbage collector (at 1 MB in the Xbox) often making you get lag spikes once in a while.

I encountered this issue with my engine, where entities were being created and deleted almost every frame, this made the lag unbearable. I knew from the start I had to pool the entities, so I did using this method:

static List EntityList = new List();

public static void GetEntity(out Entity Returnee)
{
        int Count = EntityList.Count;
        if(Count > 0)
        {
                  Returnee = EntityList[Count - 1];
                  EntityList.Remove(Returnee);
         }
         else
         {
                  Returnee = new Entity();
          }
}

Something I am not showing here is the way to return the entities to the list, that's by simply re adding them to list of entities, trivial.



The main issue with this way of pooling is that you are required to remove things from a list, this could get heavy if the list gets bigger, but for the time this method did improve my overall performance I thought I was happy with the results, until one day one of my class mates said something about how a pool can know what the next available index was instead of taking things out of a list, this made me really curious and I went on that to find a better way of pooling.

What I found is that removing things from the list was just wasteful and not necessarily, if I knew the next available index I could use that instead of removing the ones that were being used, this was possible by creating a base object that represents an item that can be activated when in the pool and "deactivated" or "unavailable" when "not" in the pool ("" because it is always in the pool at all times), the new pool looks like this:

public class Poolean where T: Poolable, new()
    {
        private List Pool;
        int MaxCount;
        int CurrentFreeIndex;
        bool SpecificType;
        Type ElementType;

        public Poolean(int BufferSize)
        {
            SpecificType = false;
            Pool = new List(BufferSize);
            MaxCount = 0;
            CurrentFreeIndex = 0;
            ExpandPool(BufferSize);
            
        }

        public Poolean(int BufferSize, Type typeOfElement)
        {
            ElementType = typeOfElement;
            SpecificType = true;
            Pool = new List(BufferSize);
            MaxCount = 0;
            CurrentFreeIndex = 0;
            ExpandPool(BufferSize);
        }

        private void ExpandPool(int size)
        {
            int start = MaxCount;
            MaxCount += size;

            if (SpecificType)
            {
                for (int i = start; i < MaxCount; i++)
                {
                    T NewPoolElement = (T)Activator.CreateInstance(ElementType);
                    NewPoolElement.Index = i;
                    NewPoolElement.InUse = false;
                    Pool.Add(NewPoolElement);
                }
            }
            else
            {
                
                for (int i = start; i < MaxCount; i++)
                {
                    T NewPoolElement = new T();
                    NewPoolElement.Index = i;
                    NewPoolElement.InUse = false;
                    Pool.Add(NewPoolElement);
                }
            }
        }

        public void ReturnPoolable(Poolable returnee)
        {
            returnee.InUse = false;
        }

        public void GetPoolable(out T vessel)
        {
            vessel = (T)Pool[CurrentFreeIndex];
            vessel.InUse = true;

            //find ther next available item
            int Next = vessel.Index + 1;
            GetNextAvailableElement(Next);
        }

        private void GetNextAvailableElement(int LastPlusOne)
        {
            for (int NextInLine = LastPlusOne; NextInLine < MaxCount; NextInLine++)
            {
                Poolable Current = Pool[NextInLine];
                if (!Current.InUse)
                {
                    CurrentFreeIndex = Current.Index;
                    return;
                }
            }

            //if it gets here then we need to start from the beginning of the list until we reach the last "Next", if this happens, 
            //then all elements are being used in the list, we need to increase the size of the list.

            for (int Start = 0; Start < LastPlusOne - 1; Start++)
            {
                Poolable Current = Pool[Start];
                if (!Current.InUse)
                {
                    CurrentFreeIndex = Current.Index;
                    return;
                }
            }

            //if we still here... then yes all the elements are being use, you need to inscrease the size of the pool.

            ExpandPool(MaxCount);
            GetNextAvailableElement(LastPlusOne);
        }
   
    }

As you can see, the new pool return references to the element in the pool, but it never ever removes that reference from the pool itself, instead it makes its "used" tag true, and looks for the next available from the index that was just taken out, in case the pool ever runs out of elements, it will double its size to continue working properly. A poolable base class looks like this:

public class Poolable
    {
        public int Index;
        public bool InUse;

        public Poolable()
        {

        }
    }

Real simple!


Well that's the cool thing I learned today, now all my entities are created really much much faster.

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.