Josh's blog

← Previous post ☆ Next post →

Making a Game in Go, part 6

In parts 1 through 5 I built up something of a “game engine” that was increasingly flexible in terms of when each (drawable) component was drawn. In doing so the amount of book-keeping in the central Game structure increased.

What even is a game? I (jokingly) suggest the following definition:

A game is a database of game components.

Database?

You: (sobbing) You can’t just make everything a database… please…

Josh: (points at a seagull) Database!

Yeah - though I won’t be shipping PostgreSQL with my game. I mean “database” as in “an organised collection of information”, not as in “Microsoft SQL Server”.

In the first few posts, Game was managing draw ordering, but in part 5 I refactored that part out into DrawDAG. So the Game’s most important field became a helper data structure for tracking the parent component of every component.

1
2
3
4

type Game struct {
    //...snip...
    parent map[interface{}]interface{}
}

In a SQL database metaphor, parent is like a table with two columns, and a unique index on the first column. parent is useful for a number of things, but it can’t speed up everything. Time to add more tables to the database?

Some things I can think of that could benefit from more data structures inside Game:

Quickly finding the component corresponding to an identifier would be useful for any component that wants to directly talk to other components.

Being able to quickly find components of a particular type would help for “checks”. For example, suppose a component needs to check for collision. There may be only a few distinct colliders among all the components, so it doesn’t make sense to have the check scan all the components in the game.

These features make a lot of sense as the basis for adding scripting. Analogously, scripts on the web need to make use of functions for finding DOM elements (getElementByID, getElementsByClassName, etc), so similarly, at some point we must provide a way for scripts to find and interact with game components.

Beyond having fast querying over the components, there’s another reason why pushing more book-keeping into Game is useful. The set of components is not necessarily fixed. New components can be added, and existing components might be removed, after the game has begun running. Does it really make sense for the responsibility of tracking all the additions and removals to fall on each component that might have subcomponents? That’s extra logic that would have to be added to each type of component (and there could be many), that doesn’t relate to the purpose of the component itself. Centralising this in Game would mean it is implemented just once, and avoids diffusing responsibility.

Components by ID

Let’s define a new interface for component types that want to opt-in to this:

1
2
3

type Identifier interface {
    Ident() string
}

And provide an implementation, designed to make it easy to adopt by embedding:

1
2
3
4
5
6
7
8
9

type ID string

func (id ID) Ident() string { return string(id) }

// Example embedding:
type Foo struct {
    ID
    // other fields
}

The data structure for the job is a textbook Go map:

1
2
3
4
5

type Game struct {
    //...snip...
    
    byID map[string]Identifier
}

Why not map[string]interface{}? No particular reason. All the components in the map will satisfy the Identifier interface, so using map[string]Identifier avoids the (very unlikely) programmer error of putting other things into the map.

Finally, when the component is registered and unregistered from Game, byID needs to be updated. Even if a component type is an Identifier, Ident might return an empty string, making the component anonymous.

Why not require all components to have an ID method? No particular reason, except that would mean adding it to every component type, including those that definitely don’t need it.

An alternative might be to provide an ID string as an argument to Game’s register function.

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

func (g *Game) registerOne(component, parent interface{}) error {
    // ... snip ...
    
    if id, ok := component.(Identifier); ok && id.Ident() != "" {
        if _, exists := g.byID[id.Ident()]; exists {
            return fmt.Errorf("duplicate registration of ID: %q", id.Ident())
        }
        g.byID[id.Ident()] = id
    }
    
    // ... snip ...
}

func (g *Game) unregisterOne(component interface{}) {
    // ... snip ...
    
    if id, ok := component.(Identifier); ok && id.Ident() != "" {
        delete(g.byID, id.Ident())
    }
    
    // ... snip ...
}

Components by parent

… that is, find subcomponents of a given component. No special interface is needed. There is a choice to be made around how to store the children of each parent. Attempt #1:

1
2
3
4
5
6

type Game struct {
    //...snip...
    
    // component -> subcomponents in a set of type map[interface{}]struct{}
    chidren map[interface{}]map[interface{}]struct{}
}

That looks a bit untidy and (this second part arguably not a problem) the iteration order of each set of children is unpredictable. Using a slice (as in map[interface{}][]interface{}) looks a bit neater and maintains order, but component removals happen in linear time with the number of child components.

To cut a long story short, I ended up implementing an “order-preserving” type Container that uses a slice for main storage but a map for reverse lookups and set-like operations. Here’s the core of the idea:

 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

type Container struct {
    items []interface{}
    reverse map[interface{}]int
}

func MakeContainer(items ...interface{}) *Container {
    c := &Container{
        // in here, the items arg has type []interface{}
        items: items,
        reverse: make(map[interface{}]int),
    }
    for i, x := range items {
        c.reverse[x] = i
    }
    return c
}

// ... various other methods omitted ...

func (c *Container) Add(item interface{}) {
    c.reverse[item] = len(c.items)
    c.items = append(c.items, item)
}

func (c *Container) Remove(item interface{}) {
    i, ok := c.reverse[item]
    if !ok {
        // not present in the container
        return
    }
    c.items[i] = nil
    delete(c.reverse, item)
    if len(c.items) > 2*len(c.reverse) {
        c.compact()
    }
}

func (c *Container) compact() {
	i := 0
	for _, x := range c.items {
		if x == nil {
			continue
		}
		c.items[i] = x
		c.reverse[x] = i
		i++
	}
	c.items = c.items[:i]
}

c.items = c.items[:i] reduces the length of the slice, but it continues using the same underlying array, maintaining the same capacity. I did it this way, instead of allocating a new slice, because it seems likely that a Container that previously had a lot of items would have a similar number of items at a later point. However, compact then never frees any memory.

The children data structure then becomes:

1
2
3
4
5
6

type Game struct {
    // ...snip...
    
    // component -> children of component
    children map[interface{}]*Container
}

Components by path

I haven’t felt the need to implement this yet, but I gave it some thought. Two likely choices for a data structure in Game for speeding up path lookups might be:

1
2
3
4
5

// Direct: path string -> component
map[string]identifier{}

// Layers: Component -> name -> subcomponent
map[interface{}]map[string]interface{}

In the first case, lookup by a path string would need len(path) work to hash the path, but the total memory to store path strings would be quadratic in the depth of the game tree. That doesn’t seem ideal.

In the second case, once path is split by whatever the path separator token is into the path \(P\), there are \(O(|P|)\) lookups - but the whole path doesn’t need to be stored for each leaf component, avoiding the quadratic complexity. Seems like a winner.

Components by type

The fun one! First we need a way to represent types. Fortunately Go has this solved already with the reflect package: values of type reflect.Type are comparable and can be used as a map key:

1
2
3
4

type Game struct {
    //...snip...
    byType map[reflect.Type]*Container
}

But which types are worth “indexing”? Just take whatever reflect.TypeOf returns? This has the downside that matching interfaces aren’t recorded, only the concrete type.Consider the problem of finding all colliders. It’s unlikely that they will all have the same concrete type (Wall, Floor, Enemy, etc), but is more likely that they all satisfy an interface such as:

1
2
3

type Collider interface {
    CollidesWith(geom.Box) bool
}

Rather than capture concrete types, then, it seems better to capture behaviours (as represented by interfaces).

If we know all the interesting interface types, we can check them in register using type assertions (without resorting to reflect), but reflect is still needed to obtain the key in the map - the reflect.Type value representing each interface.

This is slightly contorted in Go. Because every value has a concrete type, reflect.TypeOf will never return a type representing an interface. One workaround recommended by the reflect package is to reflect.TypeOf a value of type pointer-to-interface (e.g. (*Collider)(nil)), and then use the Elem method to get the type being pointed to.

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

func (g *Game) registerOne(component, parent interface{}) error {
    
    // ...snip...
    
    // Register by concrete type
    g.byType[reflect.TypeOf(component)].Add(component)
    
    // Register by each interface type
    if _, ok := component.(BoundingBoxer); ok {
        g.byType[reflect.TypeOf((*BoundingBoxer)(nil)).Elem()].Add(component)
    }
    if _, ok := component.(Collider); ok {
        g.byType[reflect.TypeOf((*Collider)(nil)).Elem()].Add(component)
    }
    if _, ok := component.(Drawer); ok {
        g.byType[reflect.TypeOf((*Drawer)(nil)).Elem()].Add(component)
    }
    if _, ok := component.(Updater); ok {
        g.byType[reflect.TypeOf((*Updater)(nil)).Elem()].Add(component)
    }
    // etc
}

Can this be improved? Yes. reflect.Type can be used for interface checks using the Implements method. So if we put all the interesting interface types into a slice, we can loop over them - and we even get a chance to put more types into the slice at runtime before registering any components, in case the user of the game engine comes up with any more:

 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

// Various values of reflect.Type to save us having to do the pointer-elem dance
var (
    BoundingBoxerType = reflect.TypeOf((*BoundingBoxer)(nil)).Elem()
    ColliderType      = reflect.TypeOf((*Collider)(nil)).Elem()
    DrawerType        = reflect.TypeOf((*Drawer)(nil)).Elem()
    UpdaterType       = reflect.TypeOf((*Updater)(nil)).Elem()
    // etc
)

// Behaviours contains all the interface types that are indexed in Game.byType.
var Behaviours = []reflect.Type{
    BoundingBoxerType,
    ColliderType,
    DrawerType,
    UpdaterType,
    // etc
}

func (g *Game) registerOne(component, parent interface{}) error {
    // ...snip...
    
    g.byType[reflect.TypeOf(component)].Add(component)
    
    for _, b := range Behaviours {
        if reflect.TypeOf(component).Implements(b) {
            g.byType[b].Add(component)
        }
    }
}

Since the number of behaviours should be fixed and small, there should not be much issue in storing a reference to each component per interface.

Combinations of the above

With more indexes comes more work required to update indexes. Even worse, there will be a point where adding yet more data structures to speed up finding components is increasing work for increasingly specific use-cases. That said, one combination of the above that I did end up implementing was between components by type and by ancestor…ish.

Going back to the collider example, it occurred to me that it’s not enough to simply find all the Colliders in the game. Suppose multiple levels are loaded at once, but only one is being shown at any given moment. byType[ColliderType] would end up containing Colliders from all the levels, and it would be bad if they all affected collision detection if the geometry overlapped. Even if not, avoiding collision detection between different levels might have merit for efficiency reasons. We want to find Colliders that descent from the same level.

The first iteration of the data structure worked a bit like this:

 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

type abKey struct {
    ancestor  interface{}
    behaviour reflect.Type
}

type Game struct {
    //...snip...
    
    // {ancestor,behaviour} -> all the descendants of ancestor
    //    implementing the behaviour
    byAB map[abKey]*Container
}

func (g *Game) registerOne(component, parent interface{}) error {
    // Set parent first, since this is used later for byAB
    g.parent[component] = parent

    //...snip...
    
    for _, b := range Behaviours {
        if !reflect.TypeOf(component).Implements(b) {
            continue
        }
        // Starting with component and proceeding upwards,
        // add component to byAB for the current component
        // and behaviour.
        for p := component; p != nil; p = g.parent[p] {
            key := abKey{
                ancestor: p,
                behaviour: b,
            }
            if g.byAB[key] == nil {
                // can't add to a nil *Container
                g.byAB[key] = MakeContainer(component)
                continue
            }
            g.byAB[key].Add(component)
        }
    }
}

This structure is fast for lookups: g.byAB[key] returns the collection of components of a given type that are descendants of a given component in \(O(1)\). But, yet again, I wrote code that is quadratic in the depth of the game tree. The deeper a component is, the more ancestors it gets added to, and in the worst case every component is on the path of descendants. So for a tree that is \(D\) layers deep, byAB stores at least \(O(D^2)\) references to components, and that was beginning to use a few megabytes of RAM even in my small example game.

To fix this, I went with a similar approach to how I would index paths above. Instead of storing a reference to each component against every ancestor, I instead store it once against its parent (and the parent against its parent, and so on):

 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

type abKey struct {
    parent    interface{}
    behaviour reflect.Type
}

type Game struct {
    //...snip...
    
    // {parent,behaviour} -> subcomponents of parent either
    //    implementing the behaviour, or themselves having
    //    descendants implementing that behaviour (or both).
    byAB map[abKey]*Container
}

func (g *Game) registerOne(component, parent interface{}) error {
    // Set parent first, since this is used later for byAB
    g.parent[component] = parent

    //...snip...
    
    for _, b := range Behaviours {
        if !reflect.TypeOf(component).Implements(b) {
            continue
        }
        // At each step, c is the direct subcomponent of p.
        // Note the double assignments.
        for c, p := component, g.parent[component]; p != nil; c, p = p, g.parent[p] {
            key := abKey{
                parent: p,
                behaviour: b,
            }
            if g.byAB[key] == nil {
                // can't add to a nil *Container
                g.byAB[key] = MakeContainer(c)
                continue
            }
            if g.byAB[key].Contains(c) {
                // c is already a child of p in byAB, so
                // no need to continue up the tree.
                break
            }
            g.byAB[key].Add(c)
        }
    }
}

The downside to avoiding the quadratic memory consumption is that lookups in this new byAB are more involved. The basic recursive approach is as follows:

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

// Query returns all components that descend from the
// given component and implement a given behaviour.
func (g *Game) Query(component interface{}, behaviour reflect.Type) []interface{} {
    var result []interface{}
    // component is its own ancestor, so check it first
    if reflect.TypeOf(ancestor).Implements(behaviour) {
        result = append(result, component)
    }
    key := abKey{
        parent: component,
        behaviour: behaviour,
    }
    for _, x := range g.byAB[key].items {
        if x == nil {
            continue
        }
        result = append(result, g.Query(x, behaviour)...)
    }
    return result
}

The built-in append, like MakeContainer above, is variadic. The ellipsis operator ... lets you provide a slice of arguments to a variadic argument in one go, instead of having to call append once for each item.

This implementation has the minor downside that each call to Query, including the recursive calls, allocates its own result slice (likely a few times as items grow it beyond capacity).

Maybe the calling code is happy to be given components one at a time. Oh! Sounds like a visitor pattern!

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

// Query visits all components that descend from the
// given component and implement a given behaviour.
func (g *Game) Query(component interface{}, behaviour reflect.Type, visit func(interface{})) {
    // component is its own ancestor, so check it first
    if reflect.TypeOf(ancestor).Implements(behaviour) {
        visit(component)
    }
    key := abKey{
        parent: component,
        behaviour: behaviour,
    }
    for _, x := range g.byAB[key].items {
        if x == nil {
            continue
        }
        g.Query(x, behaviour, visit)
    }
}

In my eagerness, I really wanted to use this for more than just collisions. What about drawing? Well, aside from components that draw, there are also components that affect the drawing of their descendants. Query(game, DrawerType, visit) will call visit for each Drawer under game, but skip calling visit with all those components in the middle that are not Drawers. This is surmountable using parent, but Query itself is recursively visiting those intermediate components. Each visit function takes interface{} as its argument, and is therefore responsible for ensuring the value has the desired type, so all that is needed is to remove the reflective type check within Query.

Finally, since it looked like Query was fast becoming the new PreorderWalk, why not implement postorder traversal as well? (This is in fact necessary - if additional state has to be set up before visiting descendants, e.g. a draw transform, then that state might have to be un-wound after visiting the descendants.)

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

// Query visits all components that descend from the
// given component and either implements the given behaviour
// or has descendants implementing that behaviour.
func (g *Game) Query(component interface{}, behaviour reflect.Type, visitPre, visitPost func(interface{})) {
    // Look ma, no check that component implements behaviour!
    // (And it often does not!)
    visitPre(component)
    key := abKey{
        parent: component,
        behaviour: behaviour,
    }
    for _, x := range g.byAB[key].items {
        if x == nil {
            continue
        }
        g.Query(x, behaviour, visitPre, visitPost)
    }
    visitPost(component)
}

With that, hopefully I have no more to say about recursion.