Shifting the burden of creating tile-based artwork to the renderer
I recently finished making a game for a contest. A lot of the other entrants used tools like Construct or Game Maker, but I decided to go with what I’m most familiar with — C++. I made use of Box2D for simple platformer physics, and I ventured into some new territory with OpenGL and OpenAL with mostly positive results. Long story short, spending two months developing with nothing but Visual Studio and tools of my own creation made me realize anew that I really enjoy coding. I’ll no doubt spend most of my time on school projects from now on, most of which will be level design or UnrealScript, but I’ve decided that I’d continue to make an active hobby out of creating small games from scratch. Since I’m necessarily moving at a more leisurely pace, I now have the opportunity to plan and document more carefully, so I figured I’d use this old, neglected blog to do that. Mind you, these aren’t tutorials and I’m by no means an authority — I’m more or less thinking out loud, except with laboriously constructed diagrams.

This last game was a platformer with tile-based graphics. The problem with tile-based graphics, if you’re doing them the old-fashioned way, is that you end up making a lot of redundant variations of the same tile if you want them to end up looking presentable. There are cases where it’s good to have direct, pixel-level control over how things look, but much of the tile work I was doing in Photoshop could have been handled procedurally, on the fly, in the game itself. Since I’m aiming to streamline the level creation process as much as possible, delegating to the computer the task of combining different sets of graphics in a way that looks pretty is one of my first goals.

Here is a sampling of the many individual tiles that were required to make a set that still had a lot of pieces missing. Your average tile consists of a base texture, which is the same across all tiles in the set, and an overlaid trim that’s edited to fit the shape or outline of a particular tile. All of the tan brick tiles could be boiled down to two textures if the base layer and the trim layer were rendered separately by the game, and the trim layer properly wrapped around the edges of the shapes in the level.
I’d like the game to be able to generate something like the above on its own, given those two textures and the user-defined shapes, in the form of a list of vertices.
Although you can easily get away with only having a certain set of predetermined ’slope’ tiles, I figure now is as good a time as any to start venturing beyond the SNES-era notion of tile-based levels on a clearly-defined grid. I decided to work on a way of rendering overlaid trims onto arbitrarily defined shapes. Here is that process:

A 2D shape comprising edges of arbitrary angles is drawn. This example uses a convex shape with vertices drawn only on gridlines, so that if the shape were to be divided into grid-spaced tiles, each tile would have no more than 4 vertices defining its shape. Whether a tile-based approach will be used, or whether more finely detailed shapes may be drawn, is yet to be determined.

A base texture is applied to the shape, in this case sourced from a single, tiled, 32×32 image. To go with the grid-spaced tile paradigm, each vertex is drawn translated outward from the center position of the tile. The UV coordinates for each vertex are determined simply by translating the relative vertex position into UV space.
A trim texture is selected, sourced from a 32×32 image in the same format as the base texture. Thanks to transparency, trims may be of any thickness up to 1.0x the height of the image, and the trim placement algorithm does not require (or allow, if you prefer) the user to explicitly specify a desired thickness. A starting location is chosen, and the process about to be described is repeated edge-by-edge until the shape is closed. In this example, we start at the uppermost and leftmost vertex, and work clockwise.
Note: These steps work through what should happen conceptually, or how a human would lay things out. An efficient, programmatic approach will be divined once the process is completely described in these terms.

First, the distance of the edge is measured. Distance((-0.5, 0.5), (0.5, 0.32)) is 1.016, which tells us how long our trim quad needs to be.

The top-left corner of the appropriately-sized trim quad is placed at the vertex in question, becoming the anchor point for rotation. The rotation of the trim is determined by finding the angle between the horizontal and the vector formed by the edge along which the trim is placed.
The preceding steps are repeated for the next edge:
From (-0.5, 0.32) to (0.26, -0.5), distance 1.118
Vector2D(0.76, -0.82), slope angle 47.17 degrees

The edges are joined properly, but with some overlap. In order to produce a seamless transition, the overlapping area needs to be clipped off.

The edge along which the clipping should occur extends from the vertex which adjoins the two edges, along the vector halfway between the two edges (the inverse 2D cross product of -A and B? You tell me). In this non-programmatic approach, we delete everything to the left of the clipping vector.
In the actual impelementation, this information will be used to modify the bottom-left vertex of the trim quad before it is drawn. Recall that a trim texture, transparency and all, is square. The orange rectangles below outline the actual quads to which the trim textures are applied. In local coordinates, their width is equal to the length of the edge, and their height is always 1.0.

Vector C is the line which runs from the edges’ adjoining vertex through the intersection of the two quads’ bottom edges. This intersection point becomes the new bottom-left vertex of the trim quad. The UV coordinate at this vertex is (u, 0.0), where u is the distance from the original (non-clipped) bottom-left vertex to the new bottom-left vertex.
The process is repeated yet again:
From (0.26, 0.5) to (0.5, -0.5), distance 1.028
Vector2D(0.24, -1.0), slope angle 76.50 degrees

This step identifies a flaw in the process: If the edge to which we’re adding trim forms an acute angle, the edge of the trim will extend beyond the bounds of the shape. One possible solution is to mask the trim to the underlying shape, but it’s probably computationally cheaper to alter the bottom-right vertex of the trim quad in the same way that we already alter the bottom-left.
As I mentioned earlier, the so-called clipping vector for the bottom-left vertex is based on the current edge and the previous edge. Similarly, the clipping vector for the bottom-right vertex will need knowledge of the next edge as well as the one currently being iterated over in the trim placement process.

This case is simpler, however. The clipping vector for the right side is simply the next edge in the chain. The new bottom-right vertex is the point at which the next edge intersects the bottom edge of the current quad, and its UV coordinate is (u, 0.0), where u is equal to the length of the edge minus the distance between the old bottom-right vertex and the new one.
Note: You will see momentarily that this is not the best way to solve this problem. However, this is not a tutorial, but a documentation of the design process (which often takes place very late at night, I might add). I prefer to leave such momentary lapses in judgement intact in order to demonstrate how poor design choices can be avoided by taking the time to plan things out before implementing them. You will make mistakes, so it’s best to make them all as early as possible, when they can still be easily corrected.
cur: (0.5, -0.5) to (-0.5, -0.5), d 1 | (-1.0, 0.0), angle 180
next: (0.5, -0.5) to (-0.5, -0.15), d 1.06 | (-1.0, 0.35), angle 160.71

In the case of an obtuse angle, the next edge never intersects the current quad, so the bottom-right vertex should only be clipped if the angle between the two edges is greater than 90 degrees.
Additionally, because the corner formed by this edge is acute, it is a triangle rather than a quad. This is a separate issue that will be addressed in the implementation.
The process is repeated for each edge until we return to where we started.

This last overlap is a bit of a special case. Since each edge covers up the previous edge, we normally don’t have to clip the right edge except in cases of acute angles. However, assuming we draw the edges in sequence, one on top of the other, there will be an unavoidable overlap wherever we start and end.
The quick solution is to add a special case that would clip the right edge of the last trim quad. However, adding such functionality to the normal trim placement process would solve this problem as well as the previous acute angle problem without the need for special case logic. Additionally, it would be essentially identical to the process used to clip the left edges. The performance difference is negligible, but it will result in much more elegant code.
—
A shape is a series of edges. In our shape creation process, of which trim placement is a part, the edges need to be in a doubly-linked list, so that any given edge is aware of the edges before and after it. Using this information, the trim placement algorithm will determine the proper vertex positions and UV coordinates for each quad/tri, and then apply the trim texture, requiring no additional data describing the thickness of the trim.

No implementation has yet been written, and some details are still up in the air. However, we’ve come up with a decent procedure for adding trim to a shape. By articulating every step of the process as well as running through it by hand in Photoshop, I’ve been forced to critically evaluate every decision and to make sure that the code that will result from this plan will be thoroughly designed, free of hastily-made errors, and if nothing else, well-documented.



















Concept rendering is something I’d really like to improve on, but there it is. There were a lot of detail sketches of different parts and props, but unfortunately most of them didn’t make it into the final product. In fact, toward the end I realized I couldn’t finish everything, and the focus shifted a bit. It ended up being a blocky model of a harpoon gun with some pretty elaborate background scenery.
