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
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
1 2 3
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
This is fine…if all your objects have flat, axis-aligned sides.
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
compare. This thinking led to a new
Drawer interface and updated comparison:
1 2 3 4 5 6 7 8
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
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 -
DrawAfterreported 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
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.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:
Lessneeds 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
1 2 3 4 5 6 7 8 9 10
And the corresponding implementations in
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
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
correctly, leaving only the special cases for each implementation of
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
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
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!