Intrusive linked node

Dealing with large number of objects can be tasking, specially in games, traditionally we have our objects living in some sort of collection, and then we traverse this collection to perform a task (like Update() or Draw()).

Collections work amazingly, traditionally I seen that the generic List is used the most, I use them often, but I stopped using them to managed my objects, simply because of how slow and tasking the "Remove()" function was, let me explain this:

when you have a collection of 10 elements in a List, and you decide to remove element 4, you would have to shift the following 6 elements down a slot to keep the list continuous, since the list is just a glorified "array", this can be very expensive, imagine if you were to remove element 1 in a list that contains 10,000 elements, not fun.

Linked list in the other hand do a much nicer job for removing elements, since they know what's next and what was previously, I would suggest to use linked list when you don't need to access an specific element in a collection, linked list do not work nicely when trying to "find" things inside them, because they are not indexed, you would have to check from start to end for an element using some comparison check on every single element, not fun.

Currently in my game, I use my own "collections" which are very specific, I have an "Actor Node" which takes care of the actors, like this:

public class ActorNode
    {
        public IActor Subject;
        public ActorNode SelfReference;
        public ActorNode NextActor;
        public ActorNode PreviousActor;

        public static ActorNode Head;

        public ActorNode(IActor subject)
        {
            SelfReference = this;
            Subject = subject;
        }

        public void Activate()
        {
            if (Head != null)
            {
                Head.PreviousActor = SelfReference;
                NextActor = Head;
            }
            Head = SelfReference;
        }

        public void Deactivate()
        {
            if (PreviousActor == null) //check for head
            {
                if (NextActor != null)
                {
                    Head = NextActor;
                    NextActor.PreviousActor = null;
                }
                else
                {
                    Head = null;
                }
            }
            else
            {
                if (NextActor != null) //check for tail
                {
                    NextActor.PreviousActor = PreviousActor;
                    PreviousActor.NextActor = NextActor;

                    NextActor = null;
                    PreviousActor = null;
                }
                else
                {
                    PreviousActor.NextActor = null;
                }
            }

            PreviousActor = null;
            NextActor = null;
        }
    }

This Node is a "component" of my actors, meaning that they live inside my actor class, using my factory design pattern (check last post for reference) I easily activate them, and using my Recycle method (also last post) I deactivate them before returning them to the pool, like this:

public class AnActor: PooleanNode<AnActor>, IActor, Irecycle
{
    LinkedPoolean<AnActor> Pool = new LinkedPoolean<AnActor>();
    
    ActorNode ActorLink;    

    public AnActor()
    {
        ActorLink = new ActorNode(this);
    }

    public static void Create()
    {   
        AnActor Vessel;
        Pool.Get(out Vessel);
        Vessel.ActorLink.Activate(); //Activates the node so it is in the collection
    }

    public void Recycle()
    {
        ActorLink.Deactivate(); //deactivates the node so it is taken out.
        Pool.ReturnPoolable(this);
    }
}

Now, let's assume that the "IActor" interface contains a method called "Update()", we can use this collection to update all the currently activated actors like this:

public static void UpdateAll() //function that updates all the actors
{
     ActorNode Current = ActorNode.Head; //gets the current head
     if(Current == null) //make sure there are elements in the collection
     {
         return; //if there's nothing, then get out.
     }
     IActor CurrentActor; //container for the current subject that needs to update

     do
     {
          CurrentActor = Current.Subject; //get the first subject
          
          CurrentActor.Update(); //Update it and then

          Current = Current.NextActor; //check for the next node

     } while (Current != null); //and if that node is not null, then repeat.
}

That function will make sure that all the activated nodes will update.

Thanks for reading.

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!

Taking casting out of the picture

Once again! I have done another revision to the way I am doing pools, it is almost like an obsession, in any case, it has proven to be fantastic, onto the code:

public class LinkedPoolean<T> where T : PooleanNode<T>, new()
    {
        public T Head;

        public LinkedPoolean()
        {
            Head = Activator.CreateInstance<T>();
        }

        public void Get(out T Vessel)
        {
            if (Head != null)
            {
                Vessel = Head;
                Head = Head.Next;
            }
            else
            {
                Vessel = Activator.CreateInstance<T>();
            }
         
        }

        public void ReturnPoolable(T Return)
        {
            Return.Next = Head;
            Head = Return;
        }
    }

The Key change here is the way we access the "Activator", you see, there's a function to create an instance that takes a Generic parameter T, and there's another version of the function that takes an argument "Type" and returns an "Object", the object returned by the second function is sadly not the right type, so in order to use it I used to cast it, this would create a hit on the performance. The function that takes a parameter of type T returns an object of type T, making casting unnecessary.

This improvement was only possible though if the PooleanNode knew which "kind of poolean node" it was, new Poolean node class:

public class PooleanNode<T> where T: PooleanNode<T>
    {
        public T Next;
    }

This in turn makes the poolean node type safe, before hand it was potentially possible to subscribe a poolean node into a pool of another type, it was kind of weird at the beginning to see a class expecting itself to be the template, but it is kind of cool the way it works.

Thanks for reading~

The Pooling Redo

I can't believe that I first attempted to make a proper pool back in April, that's only 6 months ago! I learned so much and looking back I feel dumb, but that's the main purpose of this blog! I like to check out my learning curve.

Anyways, to the pools, not too long ago I read about intrusive lists and how they were awesome for managing your game objects, before that my take on recursions were weird as well, I abandon the method and just made a while loop scanning of the nodes to traverse the tree, so no more recursion because the Xbox hates you using memory!

My last revision on the pool was cool, managed and it served it's purpose pretty well, but then I read about recursive lists and I thought that I could use something like that in the pool, a linked list pretty much but instead of using the built in linked list I wanted to make the nodes of the pool the actual objects and not a sub object attached to a node.

public class LinkedPoolean<t> where T : PooleanNode, new()
    {
       Type TypeOfT;

        T Head;

        public LinkedPoolean()
        {
            TypeOfT = typeof(T);
            Head = (T)Activator.CreateInstance(TypeOfT);
        }

        public void Get(out T Vessel)
        {
            if (Head != null)
            {
                Vessel = Head;
                Head = (T)Head.Next;
            }
            else
            {
                Vessel = (T)Activator.CreateInstance(TypeOfT);
            }
        }

        public void ReturnPoolable(T Return)
        {
            Return.Next = Head;
            Head = Return;
        }
    }

The thing to note here is that it is so ridiculous simple in comparison to my first attempt, and I was thinking that the last attempt was short! now, in this case I made the "PooleanNode" a base class cause it bugs me to know that I would have to use a "Property" to fetch a single field (which is all that class has in it as for now), but if that doesn't bother you then you may as well make the class an interface.

Poolean class:

public class PooleanNode
    {
        public PooleanNode Next;
    }

Well more weird things will result out of this, I am going to be changing quite a bit of things in my engine, because this method it is not just about 10 times faster and more memory friendly but it is also a good design.

Recursion

I have heard a lot about how recursion is bad, and why we should use collections instead and that collections are faster/safer, I believe it, but recursion has it's moments when it proves to be more useful than collections.

When you have that typical scenario of nodes, with one child and one parent (or many of both, etc) and then you call a function that calls the same function of either the parent of the child, that's a recursive function call, it will iterate all the elements that satisfy the criteria, such as "Draw all the children of this node", then we call draw on the parent, and the parent call draw on the children, etc.

What I think is bad about recursion is when the function being used recursively needs to pass arguments to be further tested down the line of nodes, or when the function itself returns a value to be processed by the parent, this is bad simply because we need to allocate memory for as long the functions we are using are alive (memory in the stack), for example if a parent node needs to count all it's children it could send an int by reference down the line and tell the children to add one or the children could return an int that's equal to the current number + 1, the stack wont release memory until the functions are finalized.

This could be avoid nevertheless, if you must have something to be analyzed down the line then you could make use of a "static" variable, that means you just need to set that variable once and all the nodes will know about it (a local static variable), that means you are not really allocating memory per call, just looking at memory already available to you.

I used recursion to add new elements to my drawing sorting, this proved to be quite fast and efficient, so instead of using a collection I used a node system that holds an "IDrawSorted" type of object and calls draw on it whenever the parent node needs to draw, code example:

public class SortingNode
    {
        public static SortingNode TopParent;
        static Poolean NodePool = new Poolean(1000, 100);
        public static SortingNode FindingAPlace;

        public SortingNode Child;
        public SortingNode Parent;
        public IDrawSorted Drawer;
        public int Z;

In the fields we have 2 static variables, one for the node that is being analyzed and another one for the current top parent, this node class is also pooled, take a look at my previous post to know about how the Poolean class works. After that you can see that the node can contain a child and a parent, as well as the information of the IDraw (The actual drawing object and it's Z position for Z sorting).

public static void Create(out SortingNode Vessel)
        {
            NodePool.Get(out Vessel);
        }

As a rule I never ever use "new" in my code design, simply because using new on objects can cause memory leaks, so all my objects are properly managed, using factory pattern methods to get "instantiated" since they really are not being created on the fly, they already live in a pool.

public void Add()
        {
            if (FindingAPlace.Z <= Z)
            {
                if (Child != null)
                {
                    Child.Add();
                }
                else
                {
                    Child = FindingAPlace;
                    FindingAPlace.Parent = this;
                }
            }
            else
            {
                if (Parent == null)
                {
                   //if a node has no parent, it is the head.
                    TopParent = FindingAPlace;
                    FindingAPlace.Child = this;
                    Parent = FindingAPlace;
                }
                else
                {
                    Parent.Child = FindingAPlace;
                    FindingAPlace.Child = this;
                    FindingAPlace.Parent = Parent;
                    Parent = FindingAPlace;
                }
            }
            FindingAPlace = null;
        }

So, this is a recursion function, as you can see it does not take any arguments and it returns nothing, so prior to call this function the information you want to analyze has to be pre loaded to the static variable inside the class, this is accomplished by accessing them by "SortingNode.FindingAPlace = YourDrawer;", this way we only set it once, and then send it to analyze. In this function we are looking if the current Z value we are passing through the static IDrawSorted is smaller or equal to the current's IDrawSorted living in the node, we will check if it has a child in the event that it is smaller or equal, so we further test down the line until we find a place were to place this new node, this is faster than a normal collection simply because I do not need to change or push down all the resting elements down the line by one because if we need to insert something in between the line we simply just change the references pointing to the parents and children to of the new node.

public void Draw()
        {
            if (Child != null)
            {
                Child.Draw();
            }
            Drawer.Draw();
        }

Recursively calling draw on every children, this is a secondary function.

public void StartDrawing()
        {
            if (Parent != null)
            {
                Parent.StartDrawing();
            }
            else
            {
                Draw();
            }
        }

this is the the entry point to the drawing class, I do it this way in case that the node that called "StartDrawing" might not be the current top node, therefore we need to find the top node to start calling draw.

public void Recycle()
        {
            if (Child != null)
            {
                Child.Parent = null;
                Child.Recycle();
            }
            Child = null;
            NodePool.ReturnPoolable(this);
        }

    }

Finally we have a recycle method to put the entire collection back into the pool when we don't need it anymore.




And that concludes my recursion method and how I use them to sort my drawing, this is working nicely in the Xbox. Currently I am working on an Xbox title because I am waiting for the new Windows phone 8 to come out as well as the new Visual Studio, once that's out I will be porting all my code to C++.

New Poolean

Looking back to when I made my first "Pool" (called Poolean) and the reasons why I made it the way it was I came to realize I was trying to avoid using "List.Remove(T)" besides avoiding to create new elements every time something was needed.

Some time after that I stumbled upon a performance problem that was going to 

hinder my game if the number of elements to be managed was going to be big, let'ssay that a pool is used a lot, meaning that the elements within the pool are

almost always "In use" and often the pool requires to expand (create new elementsto accommodate demand). Following the way the pool used to work, I would have to check if the "next" element was free, and if it was not continue until I ran out of space, then I started back from 0 to right before the element I just used, andif nothing was available then expand the pool.

The problem with this is that if I want something that requires big numbers (likeparticles) it would get hairy real quick.

I was trying to make a class that could hold a collection of objects and be able to remove the objects without having to shift things around (like List.Remove(T) does) because once again that would be very slow, I came with the idea of removing the certain element and swapping the last element in the collection to the position of the element we just removed, putting the count down by one and that would be all, in order to do this, the object I wanted to use in this "Collection" would have to contain an interface that allows access to certain index number, just a simple property to know in which position the element is in the collection. This methodology could fix my Poolean issue, by knowing how many items are in the pool, and knowing I always remove the last one, this made the entire "Searching for the next element" completely obsolete, which made me happy, so now the new Poolean looks like this:    

public class Poolean<T> where T: new()
    {
        public T[] Pool;
        public int Size;
        public int GrowthAmount;
        public int CurrentFreeIndex;
        public Type TypeOfT;

        public Poolean(int size, int Growth)
        {
            CurrentFreeIndex = size - 1;
            GrowthAmount = Growth;
            TypeOfT = typeof(T);

            Pool = new T[size];

            Size = size;

            for (int i = 0; i < Size; i++)
            {
                T NewElement = (T)Activator.CreateInstance(TypeOfT);
                Pool[i] = NewElement;
            }
        }

        public void Get(out T Vessel)
        {
            if (CurrentFreeIndex > -1)
            {
                Vessel = (T)Pool[CurrentFreeIndex];
                Pool[CurrentFreeIndex] = default(T);
                CurrentFreeIndex--;
            }
            else
            {
                //Expand
                CurrentFreeIndex += GrowthAmount;
                Size += GrowthAmount;
                Pool = new T[Size];
                for (int i = 0; i < GrowthAmount; i++)
                {
                    T NewItem = (T)Activator.CreateInstance(TypeOfT);
                    Pool[i] = NewItem;
                }

                //try again
                Vessel = (T)Pool[CurrentFreeIndex];
                Pool[CurrentFreeIndex] = default(T);
                CurrentFreeIndex--;
            }
        }

        public void ReturnPoolable(T Poolable)
        {
            CurrentFreeIndex++;
            Pool[CurrentFreeIndex] = Poolable;
        }
    }

As you can see it is a lot shorted and easier to understand, let's go over the Constructor first, in the constructor you specify how many elements do you want in the pool to begin with and in the event that the pool runs out of space, how many elements you want to add, pretty simple, there we define what type T is and then we populate the array of Ts with objects of type T. Then we have the "Get" function which takes an element out of the pool if it has any left and if it doesn't it expands, and finally we have the "ReturnPoolable" which adds the element back to the pool and gets the count up by one.

This made the pool lightning faster, but I hope I come up with an idea to make it even faster.

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.