Game Object Hierarchy

In our upcoming Knight vs Trolls game, our heroic knight will be wielding a sword which he uses to defeat foul trolls. Let’s think about how to implement this. We want the sword to be an independent GameObject, different than the knight. We need this for a few reasons. One is that we want the sword to have the freedom to move independently from the knight. We want, for example, to be able to rotate the sword to simulate a sword swing but we don’t want to rotate the knight. We might also want to allow the sword to be dropped on the ground if our knight gets hit by a troll and we want to let our knight change swords by spending coins. The sword’s position will be near the knight’s arm. As the knight moves the sword moves as well but since the two are different objects we need a way to apply the knight’s movement to the sword.

One solution is to give the sword GameObject a reference to the knight GameObject. This way the sword can read the knight’s position and update its own position accordingly.

type Sword struct{
    GameObjectCommon 
    Sprite sprite.Sprite
    Knight *Knight // the knight holding this sword
}

We add a small offset to make the sword appear near the knight’s hand otherwise it would appear dead center on the knight’s center. We can still add code to rotate the sword and it won’t affect the knight’s rotation.

func (s *Sword) Update(){
    offset := math.Vector3[float32]{-5, 5, 0}
    s.Translation = t.Knight.GetTranslation().Add(offset)
    s.Rotation = ... // some code to rotate when swung
}

We can use the same solution to give Trolls swords (or clubs, or spears). To give our player two swords, one on each hand, we would do the same and change the offset for each sword.

When the trolls hit the knight, the knight has a chance to drop his sword. Then the trolls rush to pick up the sword and our hero must get it first or bad things ensue. Since both trolls and the knight can hold the sword we must update our reference on the sword object. Ae generic GameObject reference covers both. The sword’s Holder can be either a knight or a troll since both are GameObjects.

type Sword struct{
    GameObjectCommon 
    Sprite sprite.Sprite
    Holder *GameObject // the one holding this sword
}

We are ready code everything when suddenly inspiration strikes and we come up with a new exiting game feature: trolls with shields. No problem, we can use the same design as the sword.

type Shield struct{
    GameObjectCommon 
    Sprite sprite.Sprite
    Holder *GameObject // the one holding this shield
}

But there is a twist. Our hero can attack shield-carrying trolls with the sword and disarm them. For a bit of extra fun, the shield (which is crudely made out of wood) gets stuck on the sword and drops after the knight swings the sword a few times. Very fun, but how do we code this?

We don’t really need to code much it turns out. If we make the knight’s sword the Holder of the shield we are good to go. The knight holds the sword and the sword ‘holds’ the shield. Updating the stuck shield is still done by the same code as before:

func (s *Shield) Update() {
    s.Translation = t.Holder.GetTranslation().Add(s.offset)
}

This will use the sword’s translation as basis and then add a small cosmetic offset. This way the shield moves as the sword moves. The sword’s update is the same but in it’s case the Holder is the knight. So as the knight moves, so does the sword and in turn so does the shield. We could mount our knight on a horse and have arrows be stuck on the shield the same process would make everything work as expected.

Trees

In our example, the Holder references create a hierarchical tree relationship between objects. Lets consider a knight wielding two swords, and one of the swords has a shield stuck to it. The shield itself has blocked three arrows whose tips are now buried in the shield. This is a diagram of this situation. The white arrows represent Holder references.

Organizing game objects in tree structures is very common in games and graphical applications in general. It’s so common and useful that many game engines support it out of the box, unlike here where we had to code it into our game objects. It makes sense for us to generalize our code to all game objects but before we do that we must address a problem with our solution: The sword knows who holds it but the knight doesn’t know what they are holding! This is problematic for many reasons. For example, we don’t have a way for our knight to swing or drop the sword, the sword must detach itself from its holder which is an counterintuitive way to code.

The solution is easy, we store a reference to the sword on the knight. And, because the knight can hold many items, lets make that a list of references.

type Knight struct{
    GameObjectCommon 
    Sprite sprite.Sprite
    Holds []*GameObject
}

GameObject Hierarchy

Tree hierarchies are very useful in games so we will generalize the structure we created for knight and the swords to our GameObject. Instead of calling our object references Holder and Holds we will use the more generic Parent and Children. Our GameObject interface will now have methods to set these references.

type GameObject interface {
    Update()
    Render(*sprite.Renderer)
    
    GetTranslation() math.Vector3[float32]
    GetRotation() math.Vector3[float32]
    GetScale() math.Vector2[float32]
    
    SetTranslation(math.Vector3[float32])
    SetRotation(math.Vector3[float32])
    SetScale(math.Vector2[float32])
    
    // new 
    GetParent() GameObject
    SetParent(GameObject)
    GetChildren() []GameObject
    AddChild(g GameObject)
}

As we did with the other GameObject methods, we will create default implementations for these methods in the GameObjectCommon struct.

type GameObjectCommon struct {
    Translation math.Vector3[float32]
    Rotation    math.Vector3[float32]
    Scale       math.Vector2[float32]
    
    Children   []GameObject
    Parent     GameObject
}

func (g *GameObjectCommon) AddChild(gg GameObject) {
    gg.SetParent(g)
    g.Children = append(g.Children, gg)
}

func (g *GameObjectCommon) GetChildren() []GameObject {
    return g.Children
}

func (g *GameObjectCommon) GetParent() GameObject {
    return g.Parent
}

func (g *GameObjectCommon) SetParent(parent GameObject) {
    g.Parent = parent
}

Notice that when a child game object is added the implementation also sets itself as the parent of that child.

Traversing the Tree

In the previous tutorial we kept all game objects in a list. Our game loop was to iterate over the list of game objects and call their Update and Render functions.

gameScene := []GameObject{}
gameScene = append(gameScene, Knight{})
gameScene = append(gameScene, Troll{})
gameScene = append(gameScene, Troll{})
gameScene = append(gameScene, Troll{})

// Game loop
for {
    for gameObject := range scene {
        gameObject.Update()
        gameObject.Render(renderer)
    } 
}

Let’s formalize this. We will define Scene, an object that holds GameObjects. A scene can be a level in a game or a portion of a level like a room that is loaded independently. Only one scene is active (updating and rendering) at any time.

type Scene struct {
    gameobjects []GameObject
}

In our tree hierarchy, a scene is the root of the tree. It has children but no parent. Updating and rendering a scene is not as simple as looping over the GameObjects of the scene because those GameObjects might have children. We need a way to traverse the tree structure that we have created. Traversing a tree is a well known operation. We will use a depth first search which we defined as:

func depthFirst(g GameObject, fn func(g GameObject)) {
    fn(g)
    for _, v := range g.GetChildren() {
        depthFirst(v, fn)
    }
}

This function calls a user-supplied fn function on the game object and then loops over the object’s children and calls depthFirst on them ¹. The fn function is any function we want. To Update all game objects we call depthFirst and pass a function that calls the GameObject.Update() method.

func (s *Scene) Update() {
    fn := func(g GameObject) {
        g.Update()
    }
    for _, v := range s.gameobjects {
        depthFirst(v, fn)
    }
}

If you haven’t used depth-first traversal before, I recommend you try to go through this code, perhaps with pen and paper, using the example diagram with the knight. Try to record the order in which each object is updated. Then, as an exercise, try the same with this version of depthFirst.

func depthFirst(g GameObject, fn func(g GameObject)) {
    for _, v := range g.GetChildren() {
        depthFirst(v, fn)
    }
    fn(g)
}

To render we do the same but the fn function call GameObject.Render().

func (s *Scene) Render(r *sprite.Renderer) {
    fn := func(g GameObject) {
        g.Render(r)
    }
    for _, v := range s.gameobjects {
        depthFirst(v, fn)
    }
}

With Update and Render covered, our scene update simply becomes:

scene := makeAScene()
for {
    scene.Update()
    scene.Render()
}

Order of Updates

Depth first traversal ensures that parent game objects will be updated before their children. This is desirable as children often depend on parent state for their own updates. If the knight moves, the sword’s update will need the latest position of it’s parent to update itself. If we updated the child before the parent we would create a small visual bug where the sword would lag behind it’s holder. Whether this is noticeable or not depends on the frequency of our updates (framerate) and the movement speed of the knight. Fast movement with slow framerate would be the most noticeable.

The order of updates is more important for gameplay updates. For example, if the knight dies, their sword should stop swinging and fall to the ground. If not, the knight might be able to defeat trolls postmortem. Again, not a catastrophic bug, but imagine that defeating the last troll triggered a change to the next level. This sequence would change levels with our character dead! Having a consistent and known order of game objects does not automatically eliminate this type of bug but it does make it easier to track down and fix.

---

1. This is a recursive implementation of dept first search. A stack based implementation should be faster and is planed for AGL.↩︎