Making a Game in Go, part 3

In Part 1 of this series, I described an overly simple but not terribly useful basis for a game engine in Go. In Part 2, I explained one way to divide the work of drawing and updating components when they are arranged in a hierarchy, with the drawback that the ordering between subcomponents of different parent components cannot be changed.

In this Part 3, I will take the other “fork of the road” and write about extra data structures to overcome those limitations.

The downsides

Before implementing a bunch of data structures and algorithms it is worth reflecting on what is about to be lost by doing so.

The method of delegating work from each component to each of its direct subcomponents (as in the previous post) has its upsides:

The delegation of responsibility is clear, which makes it easier to debug. (Component foo not being drawn? Does its parent ever call Draw on it?)
The whole tree of components can be deserialised, for example, using gob, without, say, having to build up helper data structures in a post-processing step, or by overriding the serialiser/deserialiser behaviour (implementing GobEncode/GobDecode).
Implementing extra data structures involves the work of “extra bookkeeping” - it’s not enough for each component to know about its subcomponents. The additional structures have to be kept up to date.

But there are responses to each of these points, too:

Why should each component have to know how to delegate responsibility to its subcomponents? That seems like something that could be written once and shared across all of them.
Post-processing is going to happen anyway, e.g. to load game assets like image and sound files.
Some extra data structures are going to be needed for implementing other features, like scripting.

Finally, since I’m still at the “engine” layer of the game code, it makes sense to do all the clever stuff here. Though hopefully it’s obvious to any game programmers reading this that I’m not doing anything novel, or particularly clever. (Doing it is its own reward!)

To make it so that we can draw things in an order that is not constrained by the logical organisation of the game tree, the responsibility for drawing can’t just be delegated to the subcomponents in turn. Drawing has to be managed in some central place.

The draw list

In previous posts, there were two separate interface types for drawing (Drawer) and providing draw ordering information (DrawOrderer). Let’s combine them. Not only do they tend to be implemented together, but I shall put them together if only for the sake of some conceptual simplifications later:

1
2
3
4


type Drawer interface {
    Draw(screen *ebiten.Image, opts *ebiten.DrawImageOpts)
    DrawOrder() int
}

Recall that the goal is to be able to draw things in order, no matter where they are in the game tree. We have a data structure for things that are in an order: a slice. (Or an array, a list, or whatever it is called in your favourite language. In Go, a slice.)

1

type drawList []Drawer

Secondly, we must be able to keep the items in a drawList sorted, so let’s implement sort.Interface:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


func (d drawList) Less(i, j int) bool {
    return d[i].DrawOrder() < d[j].DrawOrder()
}

func (d drawList) Len() int {
    return len(d)
}

func (d drawList) Swap(i, j int) {
    d[i], d[j] = d[j], d[i]
}

Why not use sort.Slice, like before?

No particular reason, other than demonstrating two ways of doing it.

We can put the drawList into Game as a field (called drawList). Game.Draw can be simplified to just draw the draw list without any type assertions, and Game.Update can now keep it sorted in one line:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


type Game struct {
    // Not all the components, just the top-level ones.
    Components []interface{}
    
    // All the components that can be drawn.
    drawList drawList
}

func (g *Game) Draw(screen *ebiten.Image) {
    for _, d := range g.drawList {
        d.Draw(screen, nil)
    }
}

func (g *Game) Update() error {
    // ... Updates happen here ...
    
    // Keep the draw list sorted
    // Use stable sort to prevent flickering between items
    // with equal draw order value.
    sort.Stable(g.drawList)
    return nil
}

Why aren’t you checking if the list is already sorted, like before?

Aside from being shorter code, the sort algorithms are probably reasonably good on data that is already sorted, and if the draw order is changing frequently, the check is mostly redundant.

The problems now are:

drawList is currently empty (assuming the user of Game is in another package). There is no way to keep drawList up to date with the contents of Components, or their descendants.
The options passed to each component’s Draw method don’t reflect that of their parent components. For example, hiding a parent component doesn’t hide any of its descendants.

Let’s fix those.

Scanning

We know that the components will be arranged in a tree. And some components are likely to have different internal arrangements to others. Scene, from Part 2, is essentially just a flat slice of subcomponents, whereas a hypothetical Sprite might consist of exactly two subcomponents called SpriteSheet and Actor.

We also want Game to find out about all the components. Perhaps it needs a way to traverse the tree.

To abstract away the details of how subcomponents are stored, and just get them in a consistent way, here is another interface:

1
2
3


type Scanner interface {
    Scan() []interface{}
}

Scan is intended to return all the direct subcomponents of a component. I called it Scan because it “scans” the internals of the component, but some alternative names for the method might be Subcomponents or Children.

Two different example implementations might look like:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


type Scene struct {
    Components []interface{}
}

func (s *Scene) Scan() []interface{} { 
    return s.Components
}

type Sprite struct {
    Sheet SpriteSheet
    Actor Actor
}

func (s *Sprite) Scan() []interface{} {
    return []interface{
        &s.Sheet,
        &s.Actor,
    }
}

How would Game make use of Scan? With a depth-first search, of course. In fact if we make Game itself implement Scanner, then the depth-first search doesn’t even have to be a method of Game. Here’s a function that calls some callback function for every component it can reach from some starting component recursively, using Scan:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


// Walk walks through a tree of components by calling Scan
// to find subcomponents of each component. It visits components
// in depth-first order.
func Walk(component interface{}, visit func(interface{})) {
    visit(component)
    if sc, ok := component.(Scanner); ok {
        for _, c := range sc.Scan() {
            Walk(c, visit)
        }
    }
}

And thus we can build drawList:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


func (g *Game) Scan() []interface{} { return g.Components }

// Load is used to load the game. Call this after setting up
// g.Components.
func (g *Game) Load() {
    // First make sure drawList is empty (in case Load is
    // called again).
    g.drawList = nil

    // Use Walk to find all the Drawers in the game tree,
    // and add them to the draw list.
    Walk(g, func(c interface{}) {
        if d, ok := c.(Drawer); ok {
            g.drawList = append(g.drawList, d)
        }
    })
}

Hiding and transforming

A feature implemented in Part 2 was that each component could be drawn using options derived from its parent, and its grandparent, and so on. Examples were:

A parent component should be able to move or scale all its child components.
Hiding a parent component should automatically hide all the child components.

The game engine shouldn’t really care how each component wants to store state, so again, we can abstract these ideas with interfaces:

1
2
3
4
5
6
7


type Hider interface {
    Hidden() bool
}

type Transformer interface {
    Transform() ebiten.DrawImageOpts
}

Here ebiten.DrawImageOpts is used as the container for transforms to apply, as before, but we could use some other type if we want to do more things than apply geometry or colour matrices.

These interfaces are separate from Drawer, despite being concerned with things that primarily affect drawing, because they are useful for parent components that might not do any drawing themselves. For example, a Scene, which just contains other components, doesn’t draw anything itself, but might return a geometry matrix that moves all the components within it (establishing its own coordinate system).

Why Hidden and not Visible?

It’s true that dealing with the logical negation of a condition increases the chances of negation confusion (!NotVisible()?) However, I chose to keep Hidden instead of Visible as Hidden is congruous with the one implementation of the interface I’ve made so far. The visible/hidden state can be stored, and the interface implemented, by embedding a type such as the following:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


type Hides bool

func (h Hides) Hidden() bool { return bool(h) }

func (h *Hides) Hide() { *h = true }
func (h *Hides) Show() { *h = false }

type SomeComponent struct {
    Hides  // brings Hidden, Hide, and Show methods with it
    ...
}

Hidden works better than visible for this case because the default value of any variable or field, if uninitialised, is the zero value for the type, which for bool is false. That means that when constructing a component with a Hides field, Hides doesn’t need to be set to false - it comes that way naturally. If it were done the other way around, i.e. with a field called Visible, then it would have to be explicitly set to true all the time all over the place.

Why Hides and not Hidden for the type name?

Hidden is considered more “readable” than IsHidden because getter-style naming is discouraged. But a struct type cannot have both a field and a method with the same name, and that applies even if you are acquiring a method for your type by embedding another type. The easier thing to change is the type name. Embedding Hides makes the struct descriptive of one of its behaviours (i.e. “this component has the behaviour ‘hides’, as in, is capable of hiding”), even if the name is awkward when setting the field.

The Parent Trap

With Hider and Transformer, the Draw method of Game can now use that information to hide components and transform drawing for those that aren’t hidden. An immediate, yet incorrect, implementation is as follows:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


// Wrong!
func (g *Game) Draw(screen *ebiten.Image) {
    for _, d := range g.drawList {
        // Hidden?
        if h, ok := d.(Hider); ok && h.Hidden() {
            continue
        }
        // Transformed?
        var opts ebiten.DrawImageOpts
        if tf, ok := d.(Transformer); ok {
            opts = tf.Transform()
        }
        // Draw!
        d.Draw(screen, &opts)
    }
}

This is wrong because it doesn’t combine the values returned from Hidden and Transform from the parent components, which is what we wanted. So how do we do that? In the Part 2 way of doing things, this was easy to implement because if a parent component was hidden or wanted to supply draw options, it changed how it drew its subcomponents!

In order to obtain the cumulative hidden and transform values, Draw must follow the chain of parents up the tree, so that it may call Hidden and Transform on them. There are two ways we could store the information:

Have all the components store a reference to their parent, and supply it via some new interface (Parenter?)
Implement another helper data structure inside Game.

Option 1 kind of sucks, because the majority of components don’t really need to know anything about their parents or ancestors. The information is stored implicitly by the structure of the tree. If this were implemented, the “parent pointer” either needs to be set manually (asking for trouble) or the hypothetical Parenter interface also needs to have another method Game can use to provide the information as it Walks the game tree. Or we repurpose Scan or something.

Since the information is primarily for the benefit of Game and nothing else, let’s go with option 2:

1
2
3
4
5
6


type Game struct {
   Components []interface{}
   
   drawList drawList
   parent   map[interface{}]interface{}
}

parent is intended to be a map of components to their parent components.

Huh? map[interface{}]...?

Yes! You can use interface types as map keys in Go. This is a thing that works!

The majority of game components are going to be pointers to struct types, and pointer values are comparable. This also means you can have pointers as map keys: map[*T]... This sort of thing is a bit iffy in some other languages because they desire to have map or dictionary types disregard “object identity” (i.e. memory location) in favour of comparing the values being pointed at. Go has no operator overloading, EqualTo() / Hash() override, or the ability to supply such functions to the map builtin type, so pointers-as-map-keys really does mean that Go will hash and compare the pointers themselves. This pattern is useful when we need a shadow data structure to secretly augment the data we’re given with extra data on a per-item basis.

Next, we need to populate parent. The depth-first Walk above doesn’t supply enough information to visit to record the parent of each component, so let’s change that so that the visit callback is passed each component and its parent:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


// Walk walks through a tree of components by calling Scan
// to find subcomponents of each component. It visits components
// in depth-first order. For the first component visited, visit
// is passed nil as the parent.
func Walk(component interface{}, visit func(c, p interface{})) {
    walk(component, nil, visit)
}

// Actual implementation of Walk.
func walk(component, parent interface{}, visit func(c, p interface{})) {
    visit(component, parent)
    if sc, ok := component.(Scanner); ok {
        // Recursively walk all of component's subcomponents.
        for _, c := range sc.Scan() {
            // component is the parent of c
            walk(c, component, visit)
        }
    }
}

With that in place, Load can be updated to build parent:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


// Load is used to load the game. Call this after setting up
// g.Components.
func (g *Game) Load() {
    g.drawList = nil
    g.parents = make(map[interface{}]interface{})

    Walk(g, func(c, p interface{}) {
        if d, ok := c.(Drawer); ok {
            g.drawList = append(g.drawList, d)
        }
        g.parent[c] = p
    })
}

Note: You can append a nil slice, but you can’t set values in a nil map.

Now Draw can use it to accumulate the values needed to draw correctly:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


// Correct but inefficient
func (g *Game) Draw(screen *ebiten.Image) {
drawLoop:
    for _, d := range g.drawList {
        var opts ebiten.DrawImageOpts
        
        // Starting at d, walk up the tree parent-by-parent
        // and skip drawing if any of them are hidden
        for p := d; p != nil; p = g.parent[p] {
            if h, ok := p.(Hider); ok && h.Hidden() {
                continue drawLoop
            }
            if tf, ok := p.(Transformer); ok {
                o := tf.Transform()
                
                // Concat o onto opts
                opts.GeoM.Concat(o.GeoM)
                opts.ColorM.Concat(o.ColorM)
            }
        }
        
        d.Draw(screen, &opts)
    }
}

This is nice. Unfortunately, if the game tree is deep, this can become slow. If we are at a component of distance \(n\) from the root of the tree, then the inner loop has \(O(n)\) iterations, and each of the components along the way could themselves be in the draw list - the inner loop might be executed for them too. Therefore Draw has time complexity \(O(n^2)\). For most 2D games this isn’t likely to be a huge issue, but if the engine is going to be useful as a general library, we ought to ensure a faster solution.

Since whether or not a component is hidden, or what its transform is, is not likely to change in between calls to Hidden and Transform, we can cache the accumulated value for each component, computing them only once.

Here it is. Feel free to skip ahead:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68


func (g *Game) Draw(screen *ebiten.Image) {
    type state struct {
        hidden bool
        opts   ebiten.DrawImageOptions
    }
    cache := map[interface{}]state{
        // The Game g is not hidden, has no transform,
        // and is the topmost component. Filling this in
        // provides a terminal case for the inner loop.
        g: {hidden: false},
    }

	for _, d := range g.drawList {
        // Is d hidden itself? Shortcut.
        if h, ok := d.(Hider); ok && h.Hidden() {
            // in case we encounter any descendants of d
            cache[d] = state{hidden: true}
            continue // skip drawing
        }
        
        // Walk up g.parent to find the nearest cached state.
        // Record a stack of components we saw along the way.
        // This loop terminates because it will reach hit g
        // eventually.
        var st state
        stack := []interface{}{d}
        for p := g.parent[d]; ; p = g.parent[p] {
            if s, found := cache[p]; found {
                st = s
                break
            }
            stack = append(stack, p)
        }
        
        // Unwind the stack, computing state along the way.
        // Everything in the stack doesn't have a cached state,
        // so save time in future iterations by caching the
        // intermediate values.
        for len(stack) > 0 {
            l1 := len(stack) - 1
            p := stack[l1]
            stack = stack[:l1]
            if h, ok := p.(Hider); ok {
                st.hidden = st.hidden || h.Hidden()
            }
            if st.hidden {
                cache[p] = state{hidden: true}
                continue
            }
            // p is not hidden, so compute cumulative opts.
            // Note the reverse Concat (st.opts onto o,
            // then swap).
            if tf, ok := p.(Transformer); ok {
                o := tf.Transform()
                o.GeoM.Concat(st.opts.GeoM)
                o.ColorM.Concat(st.opts.ColorM)
                st.opts = o
            }
            cache[p] = st
        }
        
        // Skip drawing if hidden.
        if st.hidden {
            continue
        }
        d.Draw(screen, &st.opts)
    }
}

You can define types inside functions?

Yes.

Registering and unregistering

There is one last piece needed before pressing on. In the Part 2 paradigm, each component could change its subcomponents without telling anything else. It’s none of ya business!

In this new paradigm, any components that come into existence after Load won’t be drawn, because they won’t be in the draw list, unless we tell Game somehow.

We could call Load again, and figure out the draw list and the parents from scratch. This would be fine, because all Load is doing is building up a database of components, and that should be pretty snappy. But later on we will also want to load images, sounds, and other resources from disk, for example, so re-Load-ing could ultimately be quite slow.

Instead, we provide a method to call when components are added or removed. Behold, Register:

1
2
3
4
5
6


func (g *Game) Register(component, parent interface{}) {
    if d, ok := component.(Drawer); ok {
        g.drawList = append(g.drawList)
    }
    g.parent[component] = parent
}

The new component will be put into sorted order in the next Update, so there is no need to do a whole careful insertion dance.

But notice that Register has the same body as the function passed to Walk in Load, so let’s refactor Load:

1
2
3
4
5
6


func (g *Game) Load() {
    g.drawList = nil
    g.parents = make(map[interface{}]interface{})

    Walk(g, g.Register)
}

What the heck is the method g.Register doing without parentheses and arguments?

You can “curry” methods in Go. The expression g.Register is a function with the signature func(interface{}, interface{}) that saves the reference to g:

1
2


reg := g.Register
reg(c, p)  // same as calling g.Register(c, p)

You can also go the other way: if you want a function with the signature func(*Game, interface{}, interface{}), you can use the expression (*Game).Register:

1
2


reg := (*Game).Register
reg(g, c, p)  // same as calling g.Register(c, p)

But hold up a sec! That’s cute and all, but what if the new component being registered has subcomponents of its own - shouldn’t they be registered too? You raise a good point:

1
2
3
4


// Infinite recursion
func (g *Game) Register(component, parent interface{}) {
    walk(component, parent, g.Register)
}

Uh… please hold… To break the recursion we can separate the function that registers one component from the user-friendly method that registers a whole subtree:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


// Register registers a component and all its descendants
// with the game.
func (g *Game) Register(component, parent interface{}) {
    // Note the lowercase "register"
    walk(component, parent, g.register)
}

// register registers one component with the game.
func (g *Game) register(component, parent interface{}) {
    if d, ok := component.(Drawer); ok {
        g.drawList = append(g.drawList)
    }
    g.parent[component] = parent
}

What about un-registering? Our first cut implementation isn’t brilliant:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


// Subtle future whoops!
func (g *Game) Unregister(component interface{}) {
    Walk(c, g.unregister)
}

// Small quadratic whoops!
func (g *Game) unregister(component, _ interface{}) {
    var newList drawList
    for i, d := range g.drawList {
        if d != component {
            newList = append(newList, d)
        }
    }
    delete(g.parent, component)
}

There are two minor issues:

unregister is doing linear-time work in looping over the draw list, and producing an almost-identical list of almost the same size. Repeatedly calling unregister (say, by unregistering one top-level component, causing all the descendants to unregister) could result in quadratic time complexity.
Unregister is using Walk, which calls the callback first, before walking the subcomponents. This is a preorder tree traversal. For reasons I will get into in a later post, we want a postorder traversal, so that we unregister the children before unregistering the parent. For the purposes of this post, however, there is no problem unregistering parents before children.

The second issue is left as an exercise for the reader. (Rename walk to preorderWalk, make a copy, call it postorderWalk, and then swap the order of looping over the result of Scan and the call to visit. Then use that in unregister).

The first issue we can solve with another map and a couple of other tricks. Let’s build the improvements into drawList.

1
2
3
4


type drawList struct {
    list    []Drawer        // index -> Drawer
    reverse map[Drawer]int  // Drawer -> index
}

reverse will be able to map from Drawer back into an index in list. So the idea is that unregister will be able to jump right to the index of the component to remove, and remove it:

1
2
3
4
5
6
7
8


func (g *Game) unregister(component, _ interface{}) {
    if d, ok := component.(Drawer); ok {
        i := g.drawList.reverse[d]
        // TODO: Somehow remove g.drawList.list[i] in constant time
        delete(g.drawList.reverse, d)
    }
    delete(g.parent, component)
}

Bring out yer dead!

Anyway, back to unregister and that TODO. There’s actually no reason we need to do a huge amount of surgery on drawList.list. Introducing tombstone:

1
2
3
4


type tombstone struct{}

func (tombstone) Draw(*ebiten.Image, *ebiten.DrawImageOpts) {}
func (tombstone) DrawOrder() int { return math.MaxInt }

Sorry… type tombstone struct{}? Struct with no fields? Also what’s with the methods having just types in the parentheses?

Yes, you can have a type that is an empty struct. Because it has no fields, there’s no reason to refer to the receiver by name in its methods. By the same logic, you don’t need to name any of the args if you don’t need them, similar to how unregister has one named arg (component) and one blank (the underscore, _).

The idea with tombstone is that when unregister-ing a component, we replace it with tombstone{} in the draw list:

1
2
3
4
5
6
7
8


func (g *Game) unregister(component, _ interface{}) {
    if d, ok := component.(Drawer); ok {
        i := g.drawList.reverse[d]
        g.drawList.list[i] = tombstone{}
        delete(g.drawList.reverse, d)
    }
    delete(g.parent, component)
}

tombstone doesn’t draw, so the component is gone (visually speaking). What cleans up the tombstones from the list? Well, eventually Update is called, and Update sorts the draw list. tombstone defines its DrawOrder as math.MaxInt, i.e. absolute last. So after sorting the draw list, Update can trim them off the end of the slice:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


func (g *Game) Update() error {
    // ... Updates happen here ...
    
    // Keep the draw list sorted
    // Use stable sort to prevent flickering between items
    // with equal draw order value.
    sort.Stable(g.drawList)
    
    // Trim any tombstones on the end.
	for i := len(g.drawList.list) - 1; i >= 0; i-- {
		if g.drawList.list[i] != (tombstone{}) {
			break
		}
		g.drawList.list = g.drawList.list[:i]
	}
    return nil
}

But what if I have components that want to always draw last, and return a draw order of math.MaxInt?

If necessary, we can enforce tombstones are last regardless of DrawOrder with an override in drawList.Less:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


func (d drawList) Less(i, j int) bool {
	if d.list[i] == (tombstone{}) {
		// tombstones are not less than anything,
		// even other tombstones
		return false
	}
	if d.list[j] == (tombstone{}) {
		// non-tombstones are less than tombstones
		return true
	}
	return d.list[i].DrawOrder() < d.list[j].DrawOrder()
}

Why trim the tombstones from the end, and not the front?

For (admittedly very marginal and theoretical) performance gain. After trimming from the end, the array underlying the slice will have capacity at the end, and the next append will reuse that space. (Okay but why not append to the front? Because that’s not how the built-in append function works.)

Hope you enjoyed Part 3. Join me for Part 4 soon, which I hope will be even longer!