Welcome to the blog of

Josh Deprez

⬅️ Previous post Permalink link

Published 15 September 2021

Making a Game in Go, part 4

Welcome to Part 4 of this series. In parts 1 through 3, I built up a small game game engine to the point where it was useful for many styles of 2D game. Components from different parts of the game tree can be drawn in different orders, thus accomplishing most of what is needed for implementing platformers and top-down adventures where the walls have “height”.

Unfortunately… yes, the engine is still incomplete. There is one major style of “2D” game that will be difficult to implement in the engine so far: the “isometric” game.

Third Dimension entered the chat

I put “2D” in scare quotes precisely because “isometric” isn’t a 2D style - not really. It is a 3D style that is (usually) possible to draw entirely as a sequence of flat images.

Note: “Isometric” is also in scare quotes for reasons of pedantry explained by the Wikipedia article.

Let’s blunder onwards, and add a Z axis to the engine. It already sort-of has one, it’s just called DrawOrder. Wherever we currently have a 3D point for storing position or size information, we now use a 3D point. And when we need a 2D point (e.g. for drawing on the screen, which is always 2D), we’ll project the 3D point onto the 2D plane by adding some amount to each of X and Y that is proportional to Z:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
// Int3 is our 3D vector type. It uses integer components.
type Int3 struct { X, Y, Z int }

// ..., bunch of image.Point-like methods omitted ...

type Projection { ZX, ZY float64 }

// Project projects a point from 3 dimensions into 2.
func (π Projection) Project(p Int3) image.Point {
    return image.Pt(
        p.X + int(π.ZX * float64(p.Z)),
        p.Y + int(π.ZY * float64(p.Z)),
    )
}

You can…?

Yes, π is a letter (of the Greek alphabet) and is therefore a valid identifier in Go. I used π because it is easy to type on a Mac (Option-P) and π is a conventional algebraic symbol for projections (in the same way \(x, y, z\) are variables in algebra). It doesn’t always have to mean the number 3.14159…

Now, “clearly”, if we return the Z position from DrawOrder (assuming the Z axis increases as objects get “nearer”) everything will be draw in the correct order, right?

1
2
3
func (s *Sprite) DrawOrder() int {
    return s.Actor.Pos.Z
}

Actually, that’s not enough. If two components have equal Z, then they are likely one on top of another, and if they overlap at all the one on top would need to be drawn later (if that is the “camera angle” implied by the projection).

So, uh, ok, I guess we’ll change everything to return two values from DrawOrder, and use the second value to tiebreak the draw-order on equal Z?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
type Drawer interface {
    Draw(...)
    DrawOrder() (int, int)
}

func (d drawList) Less(i, j int) bool {
    az, ay := d.list[i].DrawOrder()
    bz, by := d.list[j].DrawOrder()
    if az == bz {
        // Y axis pointing downwards
        return ay > by
    }
    // Z axis pointing towards "camera"
    return az < bz
}

This is fine…if all your objects have flat, axis-aligned sides.

A character is supposed to be behind a hexagonal prism, but is drawn in front of it
An example of incorrect drawing order. The stick figure is intended to be obscured by the prism, because it is behind the right side, but because the figure's Z value is higher than the back of the prism, it is drawn after the prism.

Whoops.

Fixing draw order, badly

I hinted fairly strongly in the previous section that isometric games really aren’t 2D games, they are at their core 3D games. Therefore we might look to how 3D games solve the problem.

3D games typically have access to a Z buffer, that records depth information on a per-pixel basis. The Z buffer answers the question “how far away was the geometry that resulted in each pixel?”, and is used during rendering to ensure closer things remain on top of things further away. For each pixel being drawn, if the pixel currently in the screen buffer came from something further away, it can be drawn over (and update the Z buffer with the new depth value), but if it came from something nearer, leave it alone.

Resorting to a Z buffer is a bit of a problem, for two reasons:

  • With flat 2D drawing, the source images would need to be paired with extra depth information. Each pixel would have a corresponding number in a depth map, that when added to the Z of the component, can be compared and written into the Z buffer. Creating depth maps might be burdensome on pixel artists.
  • ebiten doesn’t seem to provide a way to use the Z buffer that already exists in the underlying graphics pipeline…quite possibly because it is trying to be a simple 2D library.

For fun 🤪 I tried hand-rolling a Z buffer using ebiten’s shader functions. Each shader has up to 4 input images but only 1 output image, so the Z buffer shader had to be separated into two shaders:

  • The first shader reads from the Z buffer, the depth map, and the source image, and writes the pixels from the source image to the screen buffer when the depth map indicates the pixel is nearer then the corresponding point in the Z buffer.
  • The second shader reads from the Z buffer and the depth map, and writes to the Z buffer when the pixel is nearer.

Sadly a single buffer cannot be used simultaneously as a source and a target for an ebiten shader, and the second shader tries to do that with the Z buffer. So I had the second shader write into a temporary buffer, copying most of the Z buffer in the process, then swapped the old Z buffer for the temp before the next draw.

All this mucking around with shaders and depth maps is overkill, and also - unsurprisingly? - didn’t have great performance with my toy example. Framerate dropped to 20fps on the WebAssembly build, with less than 200 components. Maybe I could have optimised it, but as solutions go, it seems a bit like cracking a walnut with the Mesta 50.

Fixing draw order, a bit gooder

How did old games manage isometric drawing on slow hardware without Z buffers? By just ordering everything correctly! It’s just that the ordering can’t be reduced to assigning every component one or two numbers compared in a consistent way.

Take the hexagonal prism example (essentially the same as an “isometric” square with the front and back truncated). After sketching a few of the arrangements on paper, the answer for this shape is:

  • If another component is on top (its Y is less than the prism’s top Y) then draw the prism first and the other component later.
  • If another component is in front of the prism’s front half (i.e. its farther Z is greater than the prism’s middle), then draw prism first, other later.
  • Otherwise draw the prism later and the other first.

Since this decision is specific to the prism shape, it will be up to the prism to make the decision, rather than providing some numbers that drawList can compare. This thinking led to a new Drawer interface and updated comparison:

1
2
3
4
5
6
7
8
type Drawer interface {
    Draw(...)
    DrawAfter(Drawer) bool
}

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

DrawAfter is intended to compare the current Drawer with another, and reports if it thinks it should draw after the one it is given. Here’s the example implementation in Prism, and some other interfaces invented out of necessity along the way:

 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
type BoundingBoxer interface {
    // geom.Box is like image.Rectangle but 3D.
    // BoundingBox returns a 3D axis-aligned bounding
    // box for the component.
    BoundingBox() geom.Box
}

type ZPositioner interface {
    // For flat objects that don't have depth (i.e. thickness),
    // they can just report a Z position.
    ZPos() int
}

// DrawAfter reports if the prism should be drawn after x.
func (p *Prism) DrawAfter(x Drawer) bool {
    // Prism has a BoundingBox method.
    pbox := p.BoundingBox()
    
    // Figure out the draw order based on the type of x.
    switch x := x.(type) {
    case BoundingBoxer:
        xbox := x.BoundingBox()
        
        // If there's no overlap in X, then no need to 
        // draw this after that.
        if pbox.Min.X >= xbox.Max.X || pbox.Max.X <= xbox.Min.X {
            return false
        }
        if pbox.Max.Z <= xbox.Min.Z { // p is behind x
            return false
        }
        if pbox.Min.Z >= xbox.Max.Z { // p is in front of x
            return true
        }
        if pbox.Min.Y >= xbox.Max.Y { // p is below x
            return false
        }
        if pbox.Max.Y <= xbox.Min.Y { // p is above x
            return true
        }
        // The hexagon special.
        // The plane separating the front and back 
        // is 8 pixels in.
        if pbox.Min.Z+8 <= xbox.Min.Z { 
            // x is in front of the front half of p
            return false
        }
        if pbox.Min.Z+8 >= xbox.Max.Z { 
            // x is behind the front half of p
            return true
        }

    case ZPositioner:
        return pbox.Min.Z > int(x.ZPos()) // p is after x
    }
    return false
}

This is not enough! Some screenshots from various attempts at fixing this:

Hexagons drawing in the wrong order
The base-level prisms drawing in random order.
Hexagons drawing in the wrong order
The stick figure is atop the coloured prism, but the prism still obscures the figure.

Now, the perplexing thing about the latter screenshot (the stick figure atop the coloured prism) was that:

  • The comparison between the coloured prism and the stick figure was demonstrably, provably, and testably correct - DrawAfter reported the right answer when comparing the prism with the figure, and
  • The draw order was correct when the stick figure jumped onto the prism from in front of the prism, but not from behind the left or right sides.

And here’s why! The ordering provided to sort doesn’t have enough information to sort correctly. The prism knows when it was supposed to be drawn before or after the figure based on its midline, but the figure didn’t know this because that is a detail internal to Prism. So in some cases the figure and prism would both report false from DrawAfter. sort.Stable then considered them to be equal, preserving the existing ordering.

This can also happen transitively: the order between another prism and the coloured prism is known by sort, so if the figure and the other prism were in another relation known to sort, then sort.Stable might not have to compare the figure with the coloured prism at all!

More things are needed to make this sort-based approach work:

  • Less needs to ask both components what order they think they should be in.
  • It’s not enough to ask both components whether they must be drawn after the other, because both could report false, placing them in a false equivalence. They must also report whether they must be drawn before the other.
  • As much information about ordering is needed, even between components that don’t overlap at all, to prevent transitivity issues.

Here is the two-sided Less test:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
type Drawer interface {
    Draw(...)
    DrawAfter(Drawer) bool
    DrawBefore(Drawer) bool
}

func (d drawList) Less(i, j int) bool {
    return d.list[i].DrawBefore(d.list[j]) ||
        d.list[j].DrawAfter(d.list[i])
}

And the corresponding implementations in Prism (working!):

 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
69
70
71
72
73
74
75
76
77
78
79
80
81
// DrawAfter reports if the prism should be drawn after x.
func (p *Prism) DrawAfter(x Drawer) bool {
    pbox := p.BoundingBox()
    switch x := x.(type) {
    case *Prism:
        // Fast path for other prisms
        if p.pos.Z == x.pos.Z {
            return p.pos.Y < x.pos.Y
        }
        return p.pos.Z > x.pos.Z

    case BoundingBoxer:
        xbox := x.BoundingBox()
        if pbox.Max.Z <= xbox.Min.Z { // p is behind x
            return false
        }
        if pbox.Min.Z >= xbox.Max.Z { // p is in front of x
            return true
        }
        if pbox.Min.Y >= xbox.Max.Y { // p is below x
            return false
        }
        if pbox.Max.Y <= xbox.Min.Y { // p is above x
            return true
        }
        // The hexagon special.
        if pbox.Min.Z+8 <= xbox.Min.Z { 
            // x is in front of the front half of p
            return false
        }
        if pbox.Min.Z+8 >= xbox.Max.Z { 
            // x is behind the front half of p
            return true
        }

    case ZPositioner:
        return pb.Min.Z > int(x.ZPos()) // p is after x
    }
    return false
}

// DrawBefore reports if the prism should be drawn before x.
func (p *Prism) DrawBefore(x Drawer) bool {
    pbox := p.BoundingBox()
    switch x := x.(type) {
    case *Prism:
        // Fast path for other prisms
        if p.pos.Z == x.pos.Z {
            return p.pos.Y > x.pos.Y
        }
        return p.pos.Z < x.pos.Z

    case BoundingBoxer:
        xbox := x.BoundingBox()
        if pbox.Min.Z >= xbox.Max.Z { // p is in front of x
            return false
        }
        if pbox.Max.Z <= xbox.Min.Z { // p is behind x
            return true
        }
        if pbox.Max.Y <= xbox.Min.Y { // p is above x
            return false
        }
        if pbox.Min.Y >= xbox.Max.Y { // p is below x
            return true
        }
        // The hexagon special
        if pbox.Min.Z+8 >= xbox.Max.Z { 
            // x is behind the front half of p
            return false
        }
        if pbox.Min.Z+8 <= xbox.Min.Z { 
            // x is in front of the front half of p
            return true
        }

    case ZPositioner:
        return pbox.Max.Z < int(x.ZPos()) // p is before x
    }
    return false
}

This is still a lot of trouble to go to, and it is incomplete. For simplicity the examples above bake in constants about the shape of the prism (8 pixels!) and the “camera angle” implied by the projection. The “real” code is more involved. Some of the repetitive logic could be refactored into, say, Less, to do “obvious” cases involving BoundingBox correctly, leaving only the special cases for each implementation of Drawer to handle.

But is there a “textbook” correct approach?

Fixing draw order properly?

Shaun Lebron provides a useful explanation of isometric draw ordering. To summarise Shaun’s post:

  1. Find all pairs of compnents that could overlap (after projecting them onto the screen space).
  2. Use separating planes to find the relative order between them. These become directed edges in a graph, where the components are the vertices.
  3. Use a topological sort of the graph to produce a draw order.

What is the algorithmic complexity of this approach? Here’s a naïve function which implements step 1:

 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
// BoundingRect returns an image.Rectangle that bounds the box if it were
// projected.
func (b Box) BoundingRect(π Projection) image.Rectangle {
    // details omitted
}

type drawerPair [2]int

// FindOverlaps finds pairs of components that might overlap
// in screen space.
func (d drawList) FindOverlaps(π Projection) []drawerPair {
    var edges []drawerPair
    for i, u := range d {
        switch u.(type) {
        case BoundingBoxer:
            urect := u.BoundingBox().BoundingRect(π)
            for j, v := range d {
                if i == j {
                    continue
                }
                switch v.(type) {
                case BoundingBoxer:
                    vrect := v.BoundingBox().BoundingRect(π)
                    if vrect.Overlaps(urect) {
                        edges = append(edges, drawerPair{i, j})
                    }
                case ZPositioner:
                    // ZPositioners overlap everything.
                    edges = append(edges, drawerPair{i, j})
                }
            }
            
        case ZPositioner:
            // ZPositioners overlap everything.
            for j := range d {
                if i == j {
                    continue
                }
                edges = append(edges, drawerPair{i, j})
            }
        }
    }
    return edges
}

Slight differences in detecting overlap aside, the structure of this function looks like typical \(O(n^2)\) time complexity - for each component, it searches through the whole list for other components that could overlap. And that is exactly right. We might be able to reduce this with some fun data structures for efficiently finding potential overlaps, and exclude ZPositioner (it produces lots of edges, but it may be possible to deal with them separately).

But consider the best algorithms for topological sort, which work in time \(O(|V|+|E|)\) (i.e. time linear in number of vertices plus number of edges). Our plucky game developer might be implementing a game with tons of overlaps, leading to a large number of edges \(|E| \approx |V|^2\) - then \(O(|V|+|E|) = O(|V|^2)\) (quadratic) as well. The fussy sort.Stable approach, at \(O(n(\log n)^2)\), is starting to seem not so shabby!