Introduction

Suppose you want to make a 2D RPG, much like the old Final Fantasy games on the SNES (the good old days). And before you start any game, you have to examine the masters of old. Let's take a good look at a screen shot of Chrono Trigger shown on the right.

Pretty, isn't it? Notice, though, how our little Crono is partially obscured by the wall. How is that accomplished? It is accomplished several ways:

• Draw Chrono First, then the walls (painter's algorithm)
• Sort everything based on Y positions.

The first option is easier to implement - just simply remember to render your character before any walls are drawn. However, this does not lend itself to generalization.

The second method, a render sort, is much more general, robust, and powerful solution. This method is what I call sorted rendering lists. And this method, itself, has many sub-methods. Here are the most popular ones:

• Dynamic arrays (resizing an array of entities every time you add one)
• A std::vector type
• Rendering trees

The first method is extremely inefficient. Deleting, copying, reallocating every time you add an item to the array is not only a ugly hack, it has poor performance (imagine if you have to do that for hundreds or thousands of sprites).

The second, although the code is cleaner, it still results in poor performance because in essence you are doing exactly the same thing as the first method.

The last method is much, much better. What is a tree? A tree is binary in nature, consisting of nodes that have pointers to two sub-nodes, right and left. If you're an astute person, you can immediately tell right of the bat the advantage of using trees.

If you've had experience with linked lists or trees before, you should have no problem understanding the rest of the tutorial. If you haven't, then I suggest a quick Google for trees and data structures, grasp the concept of them, and then come back.

I'm a Tree Hugger

Here are some off-the-head (best-case) algorithmic analyses of Binary Search Trees (BST):

Insertion: O(log N) - By the way, when you insert into trees, you're also taking care of the sorting step too.
Deletion: O(log N)
Traversal: O(N)
For more details about this, take a look at this article

Generally, this is much better than the array approach:

Insertion/Searching: O(N) - depending on what search/sort algorithm you use.
Deletion: O(N) - just simply delete your way through.
Traversal: O(N)

Again, algorithmic analysis proves that trees are good.

OK, I'm in. Now show me some code!

Let's get down to code. For this tutorial I'm only going to create a simple rendering tree, but it will be easily extendable.

The smallest unit of a tree is a node. Or leaf...

//....code...

struct sNode
{
    sSprite *sprite; //pointer to sprite its referring to
    int y;           //the y values
    int x;           //the x value
    sNode* left;     //pointer to the child node to the "left"
    sNode* right;    //pointer to the child node to the "right"
};

There - we have our node. It's pretty transparent, but I'll still explain its internals:

- sSprite* sprite - this is just the pointer to the sSprite object, whatever it may be. Note: if you're an inexperienced programmer (i.e. "noob"), don't copy and paste this code into your own programs, because sSprite isn't defined (unless you coincidentally defined an sSprite before...). So just replace your sSprite* sprite with whatever sprite object you happen to be using.

- int x,int y - these are just the location of the of the node.

- sNode* left, sNode* right - these are pointers to the left and right child nodes, respectively. the left points to the node which have lesser Y values than itself, and the right points to the node which have greater Y values than itself. The cool thing about trees is that subtrees retain the same properties of the parent tree, so when you insert nodes into the tree, its extremely easy to do so.

The Tree Itself

If you're still confused about the tree structure, all your confusion will be banished by the end of the tutorial, don't worry. Now we'll proceed onto the tree structure itself. It will be extremely painful.

    sNode* head;

That's it. "WHAT!" you say. "Where are all the complex data structures and ugly fangled code that looks like it came from the depths of coding hell?"  Don't worry, it'll come! So how is that the tree itself? Let's look at a diagram of a tree:

Yes, I agree, it is the crappiest tree you've ever seen in your entire life...but then again...I'm not known for my artistic abilities.

The head node is represented by our pointer, sNode* head. The head has its two pointers, left child and right child, which have their own two pointers, left child and right child, and so on.

Trees are recursive in nature, so that's how you can represent one tree with only one pointer. In essence, the sNode* head is "carrying" the whole tree.

So, we've come up with the structure of the trees, but we still haven't figured out how do they work (man...now I'm feeling like I'm explaining trees instead of rendering trees...but they're one and the same I guess.).

So if we've got only one pointer that represents our tree, how do we access all the nodes? We do that by traversal. There are three ways of traversing any tree:

1. Pre-order - you visit the current node, followed by the left subtree, then the right subtree.
2. In-order - you visit left subtree, current node, then right subtree.
3. Post-order - you visit the left subtree, right subtree, then finally you visit the current node.

Well that's great and all, but what the heck does that actually mean? Time for some pseudocode!

//pre order code
void PreOrder(sNode* node)
{
    if (!node) //check if its valid
        return; //not valid, exit

    //since its preorder, visit the current node
    DoSomethingWithNode(node);

    //check if left pointer is valid. If it is, visit it!
    if (node->left)
        PreOrder(node->left); //traverse the left side

    //check if the right pointer is valid. If it is, visit it!
    if (node->right)
        PreOrder(node->right); //traverse right

}

So how does this work? Let's start with a PreOrder(head); It enters the function, check if the node is valid - it is, go on.

It does something with the node (whatever that may be): process it, draw it, eat it, whatever. After that, it moves on to check if the left pointer is valid. This simply checks if this node has a left node "attached" to it. It does, then do pre-order all over again. It checks if the left node is valid, does something with the node, and then so on. Sooner or later it'll hit a dead end - the node isn't valid, so it jumps out of the function, and then it goes to the previous PreOrder "body" which called this PreOrder body, and proceeds to the right subtree.

Did that make sense? It had better not, because recursion is simply like that. You have to visualize this in your mind...really strange stuff.

If you don't understand recursion, you might be thinking, "Why doesn't this get stuck in an infinite loop by repeatedly calling itself?" Notice, however, in the beginning of the function it does a validity check. If it's not valid, it exits out of the function, so this validity check acts as a stopper for the infinite loop problem.

But rest assured, if your tree is constructed correctly, then this type of recursion works.

Now let's examine the other types of traversal:

//In order code
void InOrder(sNode* node)
{
    if (!node)  //check if its valid
        return; //not valid, exit

    //check if left pointer is valid. If it is, visit it!
    if (node->left)
        InOrder(node->left); //traverse the left side

    /* since its inoder, visit the current node
       AFTER it has visited the left subtree/node */
    DoSomethingWithNode(node);

    //check if the right pointer is valid. If it is, visit it!
    if (node->right)
        InOrder(node->right); //traverse right

}


//Post order code
void PostOrder(sNode* node)
{
    if (!node) //check if its valid
        return; //not valid, exit

    //check if left pointer is valid. If it is, visit it!
    if (node->left)
        PostOrder(node->left); //traverse the left side

    //check if the right pointer is valid. If it is, visit it!
    if (node->right)
        PostOrder(node->right); //traverse right

    /* since its postoder, visit the current node
       AFTER it has visited both the left subtree/node
       AND the right subtree/node */
    DoSomethingWithNode(node);

}

Not much difference, just the order in which you traverse the left subtree, right subtree and visit the node itself.

So what's the big deal with all this inorder, postorder stuff? Well, the different types of traversals are used for different types of jobs. For example, for deleting the whole tree, we need to use PostOrder, because we can't delete the node itself before hand, or we would lose all of its children. We have to delete its left subtree, right subtree, and THEN delete itself.

Now that we know how to traverse the tree, let's talk about insertion.

Insertion Point: Sector AB01

I love it how the military coins all these terms to define stuff. For example, they say, "Tango down," or, "Fire in the hole!" I mean, what the heck are those? Tango? Fire in the hole?

Anyways, I'll dump some code on you (sorry about that, its the only way), and then make up for the shock by exhaustively explaining it. It won't be so bad, though :)

But first, we'll have to have some initialization code first - our tree isn't even initialized!

Node* head = NULL; 

//Init our tree
void InitTree()
{
    head = new sNode;

    if (!head)
    {
        printf("Error creating head node!\n");
        return;
    } //end if

    head->left = NULL; //the left pointer doesn't point to anything
    head->right = NULL; //same

    //set the head's sprite pointer to NULL
    head->sprite = NULL;
}

Ok, our tree is properly initialized.

We allocate a new sNode, called head. We then check to see if we allocated properly (basic error checking), followed by setting both left/right pointers to NULL. This is an important step, because when you allocate memory for anything, the value isn't defined, and it could be anything, so we have to set it to NULL just to be safe.

Now to insertion. Let's examine how we would approach this. We have a function, InsertNode(sNode* node,sNode* child), and we pass the node we want to attach it to, and the node we want to attach. We will assume that you already alloc'd or new'd an sNode, and filled it with appropriate values. Then we will decide where to attach this new node. It will be a lot like our traversal functions.

Let's examine what we have so far:

sNode* head = NULL; 

//Init our tree
void InitTree()
{
    //.........InitTree code here..............
}

void InsertNode(sNode* node,sNode* child)
{
    //validate 
    if (!node || !child) 
        return;

    //we put something here...decide how to attach child to node
}

How do we decide where to attach this new node? Well we look at the criteria for sorting, the Y values: does this new node have a greater or lesser Y value than the node that was passed to us? If greater, then traverse the right tree - if lesser, then traverse the left tree. Here's code to show you what I mean.

sNode* head = NULL;

//Init our tree
void InitTree()
{
    //.........InitTree code here..............
}

void InsertNode(sNode* node,sNode* child)
{
    //validate 
    if (!node || !child) 
        return;

    if (child-> y >= node->y)
    {
        /* the child's y is bigger or equal than the node's y
           insert to the right
           but before we do, we have to check
           is the right tree valid? */
        if (node->right)
            InsertNode(node->right,child); //insert into right tree
        else
            node->right = child; //nope - make node's right the child
    }
    else
    {
        //the child's y is less than the node's y
        if (node->left)
            InsertNode(node->left,child); //insert into left tree
        else
            node->left = child;
    }
}

That's it - pretty straightforward.

As you can see, this function is recursive too - OMG! So much recursion! Yeah...I know...these trees suck :Grin:.

So first we compare - is the child's Y value bigger than or equal to the node you want to insert to's Y? If so, then we have to insert it into the right subtree (if it exists). If the right subtree doesn't exist, then you just make the node's right pointer the child itself.

So what happens if the right subtree does exist? Well you pass the node's right pointer as the node itself when you make the recursive call, and it keeps on comparing till it finds the perfect spot to place this pesky little child. See what I mean by how subtrees retain the properties of the parent? One more reason I love trees...anyways...

The same with the left tree...no need to re-explain there.

Now I'll wrap this insertion stuff up with the following code, which demonstrates how to build a tree:

void main()
{
    //load gfx
    //load input
    //whatever

    //initialize our tree
    InitTree();
 
    //main loop
    while (1)
    {
        //retrieve input
  
        //now let's build our rendering tree
        sNode* temp = new sNode;
        temp->sprite = wallsprite;
        temp->x = 100;
        temp->y = 120;
        temp->left = temp->right = NULL;

        InsertNode(head,temp);

        //reuse
        temp = new sNode;
        temp->sprite = crono;
        temp->x = 100;
        temp->y = 100;
        temp->left = temp->right = NULL;

        InsertNode(head,temp);
  
        //draw the rendering list

        //destroy the rendering list
    }
}

Notice how I deliberately inserted the wall sprite first, and then Crono, even though Crono is behind the wall. This is to show that no matter how you insert it, it will come out all sorted and nice looking.

So now we've got Insertion done and over with. All we have left is rendering the actual tree, and deletion of the tree.

Notice how I've been sneaking up on you with the rendering list. I subtly (or maybe not so subtly) switched from explaining trees to rendering trees. But then again...its not that big of a jump.

Rendering the actual tree

So now we've built our tree - we can render it now! It's nothing more than a problem of InOrder traversal. Why is it inorder? Because you have to draw the left subtree first (lesser Y values), itself, and right subtree last (greater Y values) - basically following painter's algorithm.

So to follow my brutal techniques I used previously, I'll just perform a code dump on your head. So prepare for a gruesome mess of code.

void RenderNode(sNode* node)
{
    if (!node)
        return;

    if (node->left) //some redundant error checking
        RenderNode(node->left);

    //draw the node itself
    DrawNode(node);

    if (node->right) //some redundant error checking
        RenderNode(node->right);
}

You knew that was coming, didn't you?

Wow - isn't that simple? The tree is already sorted (because of its inherent sorted/binary nature), so all you gotta do is follow the links and draw the nodes.

Astute readers will notice that head isn't referring to any sprite - it just holds the tree in place. So in DrawNode, you need a mechanism for detecting an invalid node (by checking if the sprite is NULL or not - in InitTree I set the sprite to NULL).

Of course, if you're conservative, then you can use head as a valid node, but I personally like the head to be empty.

Deforestation

Now we have the problem of deletion left. Is it hard, is it easy? Its just another matter of traversal, this time its Post-Order.

void DeleteNode(sNode* node)
{
    //post order
    //delete left branch
    if (node->left) //validate left pointer
        DeleteNode(node->left);

    //delete right branch
    if (node->right) //validate right pointer
        DeleteNode(node->right);

    //we can't delete ourselves...BUT, we can delete its children
    if (node->left)
    {
        //make sure it doesn't have any children
        if (!node->left->left && !node->left->right)
        {
            delete node->left;
            node->left = NULL;
        }
    }

    //do the same thing with the right node
    if (node->right) //does it have a right node
    {
        //make sure it doesn't have any children
        if (!node->right->left && node->right->right)
        {
            delete node->right;
            node->right = NULL;
        }
    }
}

I'm going crazy from the left right right left left right!!!

Not that much, but looks a bit complicated with all those if statements and comments. So here's how you implement this:

void DestroyResources()
{ 
    //delete gfx, sound, etc
    DestroyNode(head);
}

That seems all fine and dandy. However, if we run this through a debugger, we'll find after calling DestroyNode head is still valid! How is this possible? Well remember that in DestroyNode, we destroy the children, not the node itself, so after all this recursive madness, we end up with a still living head...so...we know what to do boys.

void DestroyResources()
{ 
    //delete gfx, sound, etc
    DestroyNode(head);

    //SEEK AND DESTROY
    delete head;
    head = NULL;

    //MUAHAHAHA
}

So now our head is dealt with.

"Is it over?" - Matrix Revolutions

We've come a long way. For me, at least. Writing this took longer than I thought (about 4-5 hours). We have a fully functional tree in our hands, and its up to us what we want to do with it.

We are just scratching the surface of data structures and trees, but for the most part, the tree we just went through is sufficient for most our needs.

The thing is, all this recursion and new/delete will be sure to cause some memory problems in the future. I can't stress enough, ERROR CHECK, ERROR CHECK, ERROR CHECK. Go overboard with it. Only that way can your programs can be bullet proof. Or they can dodge bullets. Whichever it happens to be, just be sure to but a lot of redundant validation in your functions, especially insertion and deletion functions.

And I'm sure that at least some of you will be going "huh? huh? huh" on the recursion parts. The trick to these are visualizing them either in your mind or even drawing these recursive graphs on paper. I did that when I first encountered these. They simplify the understanding of recursion SO MUCH.

So with that, I leave you. Along with a sample console program that demonstrates trees.