⬅️ 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.

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:

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:

- Find all pairs of compnents that could overlap (after projecting them onto the screen space).
- Use separating planes to find the relative order between them. These become directed edges in a graph, where the components are the vertices.
- 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!