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.

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++.