Building a fast tile engine — pt. 3

This is the third and final article in our series on writing a fast tile engine for Jaakan:

  • The first article talked about the naive approach we first tried
  • The second article proposed a fast way to display a hybrid tile-with-polygon-masks layer with a fragment shader

In this one, we’re going to address the last small detail: what about sprinkles?

The wrong hammer

If you need a refresher’s course in what sprinkles are, go read update 8 and update 10. If you’re in a hurry, let’s just say they’re tile borders.

The hard part?

  • Each border style (ie. sprinkleset) is stored in a 4x4 atlas, with one grid cell per angle.
  • Each cell in the sprinkleset atlas has a different offset, to leave room to draw around it
  • There’s three sprinkleset sizes allowed: 128x128 pixels, 256x256, and 512x512, which is useful for large props such as vegetation.

Of course, often, sprinkles only barely touch the surface of an edge, like so:

But still, the whole blue square area is available, and should be drawn at the right offset, for each edge. So, for that, a simple fragment shader won’t suffice. In fact, attempting to do it from a shader would be barking up the wrong tree. In that case, we’re much better off sending to the GPU a bunch of positions and texture coordinates, rather than attempting to use textures.

Edge detection

However, before we can tell the GPU where to draw edges, we have to know where there are edges! The idea is relatively simple. For each tile:

  • Let Sc be the set of active control points for the current tile.

  • For each adjacent pair (i1, i2) in Sc (including (last, first)):
    Determine which neighbor tile could possibly share that edge

  • If potential neighbor shares the edge, ignore and move on to the next pair

  • Otherwise, add to edge list and move on to the next pair.

That’s about it.

Getting the list of active control points is a simple matter of iterating from 0 through 8 and testing if each bit is set (cf. last week’s article to see how we store shape data).

The first interesting problem is determining which neighbor could possibly share that edge. We could test all 4 neighbors (top, left, bottom, right), but that would be a waste of time. For any (i1, i2), pair there is only one possible tile that can share that edge.

A fast way to go about this is to have a lookup table that gives us, for any control point, which neighbor can possibly share that point. For example, the bottom-left control can be shared by either the bottom neighbor or the left neighbor. The middle-left control can only be shared by the left neighbor, and so on.

Knowing that, we take the intersection of ‘potential neighbors’ for both points in our edge candidate — if the intersection is empty, then we’re sure to have an edge. If not, then we must check whether the neighbor has these points active or not.

But wait, how do we know which points to test on the neighbor tile? That depends on its offset compared to the current tile.

In the example above, our pair is (0, 7) but we must check for (2, 3) in the left neighbor. And that’s another lookup table: given a direction, which control point from the neighbor corresponds to a given control point.

Finally, there’s two other edge cases (heh) we have to take care of: the first is that tiles on the edge of a layer have no neighbors. For simplicity’s sake, we just assume anything outside the map is filled with quads, so there can be no possible edge at the extremities on the map.

The second is that due to the way we store shape data, some combinations have active control points and yet do not correspond to a valid polygon: those are called degenerate polygons. The check is, again, easy:

  • If the tile has 2 active control points or less, it’s degenerate
  • If the tile has 3 control points, and they’re aligned, it’s degenerate

There’s a very simple mathematical formula to check if three points are aligned: but it still involves five subtractions, two multiplications, and two comparisons.

We can do better than that, because we know exactly where control points are. The only chance of 3 control points being aligned is for it to start on a corner and be index-adjacent, for example: (0, 1, 2), (2, 3, 4), (4, 5, 6), or (6, 7, 0).

To check that the first control is on a corner, we can simply check that it’s even. And then we just see if they’re adjacent, with a final subtlety because (6, 7, 0) wraps around. Those are very quick checks, but since we have to do them a bunch of times per tile, it’s best to cache them in an array, to know which tile is degenerate and which isn’t.

And of course, as I’m writing this, I realize that since we only have 256 variants anyway, we could have an array of 256 booleans that determine if a given polygon is degenerate or not. See, writing is healthy!

Drawing them

This article is already quite long so I’m not going to give many details, but basically:

  • We group edges by sprinkleset - some might be grass, some squarerock, some snow.
  • Each sprinkleset gets its own draw call: it’s 1 texture and a whole lot of triangles.

A layer can have up to ~10’000 sprinkled edges, given that large edges (e.g. full tile diagonals) are split into two smaller edges, so it’s important to send as many as possible to the GPU in as few calls as possible.

What we do is, for each sprinkleset, we keep a VBO (vertex buffer object) around, that contains positions and texture coordinates that we send to the GPU. We only upload it when it changes (typically on level load, or when using a terrain-modifying ability), and even 20K triangles is ridiculously low nowadays.

And there you have it:

Whereas before, the typescript version had to limit edge computation to affected neighbors when painting, the new version just goes ahead and recomputes everything on change, because it’s so cheap it doesn’t even matter.

In summary, we have, for each layer:

  • 1 draw call for the poly/tile part
  • 1 draw call per sprinkleset used

Which is much, much better than what we had before. Thanks for reading up to there, and don’t forget to share the articles you like and follow us on Twitter for more game development adventures!