PCS Nodes && Trees

Note: These Game Engine blogs are a series of write-ups I did when I was in school for my master’s degree. I took a series of three courses run by Ed Keenan where we built a game engine from scratch in C++.

So first things first, let’s get something out of the way as far as main principles go for this project. We could use STL (C++’s Standard Template Library) classes for a lot of things. They would do the job just fine, but they also have a lot of bloat. Basically what I’m saying is that they’re slow and we can write our own classes that are much faster and do exactly what we need with a little added robustness.

So the first thing we’re building is what’s called a PCS Tree, which stands for “Parent-Child-Sibling Tree.” Think of it like a binary tree, but each node can have any number of children, so it’s an n-ary tree. With this data structure we’ll be able to build any kind of hierarchy imaginable. So let’s see how this works.

The PCSNode object has four pointers — parent, child, nextSibling, and prevSibling. The PCSNode object also has a character array for a name so that we can keep track of the nodes by giving them a unique name. Here is what the class looks like in some pseudo-UML

And here is what a sample tree might look like:

Each arrow that leaves a node represents one of those pointers that the object holds. If an arrow points to 0, it means it points to null or nothing. You may notice some simple data structures here that are being used and built upon. For example, Nodes on the same level are stored in a double-linked list. But notice that a parent does not point to all of its children — it only point to the first child. This is because we don’t know how many children any given node will have so that would make it impossible to store pointers for each of them. So we simply point to the youngest child (I say youngest because my insertion always inserts at the front), and that youngest child then points to its next sibling.

So how is this data structure useful?

Well, we can use this structure for pretty much anything we’d like. One good example though is for character models. Consider the body parts of a 3D character on a screen. If we wanted to move his/her arm, — the hand, forearm, and upper arm would all move too. So with this hierarchical structure, we can push a translation, rotation, or whatever we want down the tree starting at that arm and it will perform that to all objects below it.

This PCSTree structure can also be used for file systems, drawing order, collision checks, and many other things.

One MAJOR benefit of this structure is the optimization of early outs.

Consider the following example: We have a FPS game where the body parts are destructible if they get hit by a bullet. If we use the PCSTree structure for our collision checks, that is creating a hierarchy of bounding boxes, then we can exit the code early if a bullet hasn’t hit the person at all. So using the arm example from above, why do we need to check if the bounding box around the hand has collided if the the bounding box around the whole arm (that includes the hand) has never been hit? We could also use this structure to dynamically create the arm’s bounding box by adding up its children (Upper_Arm, Forearm, Hand). And let’s say the Hand has been hit, we can remove the hand node, and the Arm’s bounding box would update accordingly based on the available children.

Also consider this for a tree with a full body structure and an overall bounding box around an entire body. Why do we need to check if the hand has been hit if the entire character was never hit? We don’t. This can be a huge optimization when you have lots of large complex trees for many things on a screen at one time and you have to check and see if objects have collided every frame.

This PCSNode class and Tree class system may seem simple, but it’s actually a lot of code to build a full-fledged custom class. Especially one that is robust and keeps track of stats like the current number of nodes in the tree at any time or eve the current number of levels in the tree. We have to write functions that print the tree, print a given node’s children or siblings, and many more functions to make our lives easier when we’re debugging.

That’s what I got for this week. Let me know what you guys/gals think! I plan to write one of these once a week with my progress so make sure to check back if you enjoyed this.