Fast Tilemap Shader

I ran into an interesting article a few weeks back about using a custom shader to draw tilemaps in Unity. I was doing a small tech-demo for a pixel art game that required some large tilemaps and was looking for a way to draw it quickly.

The article I found mentioned the ability to render an entire tilemap layer with a single quad. Using a texture look-up along with a tileset image it’s entirely possible to render 1000×1000 tilemap layers in a single draw call.

There is one downside though. It doesn’t lend itself to modifying tiles very easily. So it’s fantastic for static tilemaps but not so great for dynamic.

Here’s how the process works.

  1. Parse the tilemap to an array of  tileset entries.
  2. Use the array to create an image where each pixel represents the same tileset entry.
  3. When rendering use the tileset entry image as the primary texture.
  4. Pass the tileset image as a texture to the shader as well.
  5. Sample the current color in the tileset entry texture.
  6. Convert the color to tileset space, ie, the index into the tileset.
  7. Sample the tileset image and use that as the actual rendered color.

That isn’t too bad. And I’ll split this up into two major topics and go into each in detail.


Tilemap to Tileset Entry Image

The Tileset and Tilemap

What do I mean by tileset entry? A tileset entry is an index into the tileset image.
What does the index represent? Take a look at this image.

tile_index

The indices are zero based and count up from left to right and top to bottom.

When you parse a tilemap it usually includes an array of id’s representing the tileset index. The index is then used whenever you want to draw or use a tile. In this example tileset if we were given any index we could calculate the X and Y position in the tileset with the following.

X = index % width
Y = index / width (as an integer)

Given index 5 and following the formula we get X = 1 and Y = 2.

The tilemap itself is then just an array of tileset entries. This image will explain what the tilemap array looks like.

tilemap_index

or

0 1 1 0 0 1 0 1
1 0 0 1 1 0 1 0

Internally we might have an array (one or two dimensional) that contains this information.

As you can see a tilemap will use the indices in the tileset as a reference for which image to draw.

The Tilemap Image

Now that we know how the tilemap is stored we can convert that to an image.

The tileset entry image is a mapping of the tilemap’s tileset index array.

A problem I had in Unity when I first created the image is the single image data format. You cannot create a texture of integers or of non-float4 pixel types. That requires me to take different steps than you might.

Let’s say we have a texture where each pixel is a single value. For my example I will say the texture is a single float. (This can be represented with a single component of a float4 texture.)

When we want to create the tilemap image we will create an image that is the tilemap width by the tilemap height and each pixel represents the index into the tileset. In my case I normalize the float value and multiply the value by the normalization amount passed to the shader.

In our example images we had 8 total tiles in the tileset. So we would divide the value by 8 every time we add a new float to the image.

Every time we want to get the actual index we would multiply the value retrieved from the texture by 8. We could then determine the X and Y coordinate on the tileset image convert to UV coordinates.


Shader

Shader Variables

For our shader we will need a few variables passed in. Here is a list of what I needed and a short explanation of what I used them for.

Shader Variables
Name Usage
Tileset index count Used for de-normalizing the tileset index when sampled from the image.
Tileset width/height Used to determine the location within the tileset when sampling.
Tilemap width/height Locating the UV offset of the fragment into each tile.
Tileset image ratio (float2) The ratio of pixels in the tilest image to the actual pixels we can use.
Tileset/Tilemap entry sampler This is where we get our tile id before we resample the tileset image.
Tileset image sampler Needed to actually render the tiles.

Conversion from Tileset Indices

We start with the vertex shader.

struct vtype
{
float4 position;
float2 texcoord;
};

vtype vertex_shader(vtype in)
{
vtype result;
result.position = MVP * in;
result.texcoord = in.texcoord;
}

That one is simple. All we want is to move the position of the vertex into projection space and keep the UV coordinates. Nothing special here.

Now we get to the fragment shader, this is where the bulk of the work is done.
We can look at the overall logic in this list.

  1. Flip the UV coordinates if you are using a bottom-left = (0,0) coordinate system.
  2. Retrieve the index into the tileset for the current fragment.
  3. Determine the X and Y coordinates in the tileset image.
  4. Find the starting UV coordinate for the tile we are in within the tileset image.
  5. Get the current offset into the tile.
  6. Fix the offset for any missing tile fractions.
  7. Flip our Y back if we are using a bottom-left UV space.
  8. Sample the tileset image and return.

So I said that we need to “Fix the offset for any missing tile fractions.” What is that? Well there is a problem that I ran into with one of my favorite tile editors. I used tiled, which is a fantastic tilemap editor, to generate my tilemaps. The problem arose from the fact that tiled accepts non-tile dimension multiples for the image size. That is to say if I have a 32×32 pixel tile and I provide tiled a 48×48 tileset it will still allow me to use it. What it will do is lop off the extra pixels and just render the part that fits on a perfect grid.

You also saw a reference to this in the shader variables table. The tileset image ratio is the multiplier to convert this value. It’s easy just to use a multiplier because tiled will tile from the top-left corner of the image and we moved ourselves into a UV space that uses top-left coordinates.

Here’s the fragment shader.

float4 fragment_shader(vtype in)
{
// Step 1) I use GL so I have to flip my UV
float2 flipped_uv = float2( in.texcoord.x, 1.0 - in.texcoord.y );

// Step 2) Retrieve the index into the tileset
// Remember I mentioned that I used Unity which requires Float4's for all textures
// If you can have a single float for each "pixel" in your texture there is no need
// for the .x at the end.
int index = tex2D(entry_sampler, flipped_uv).x * tileset_tilecount;

// Step 3) Get the X and Y coordinates in the tileset
int xpos = index % tileset_size_in_tiles.x;
int ypos = index / tileset_size_in_tiles.y;

// Step 3a) We increment the y position by one to account for the fact
// that GL reads UV's from the bottom left.
// A Y coordinate of 0.0 is the top of the image.
// We want to read from the bottom left so we fix our UV to have the Y on the bottom.
ypos += 1;

// Step 4) Find the starting UV coordinate.
// We divide by the size in tiles to take a coordinate like:
// X = 4, Y = 2 on a 8 by 3 tileset into, (1/2, 2/3)
// Normalizing the X and Y coordinate into the UV space.
float2 uv = float2(xpos, ypos) / tileset_size_in_tiles;

// Step 5) Determine the offset into the tile for this fragment.
// What we use here is the "fraction" operator. It returns only the fractional
// part of a decimal value.
// We get the actual UV coordinate and then multiply it by the size in tiles.
// This gives us a non-normalized tilemap location ie it is within the bounds
// of [0, map_size) on the x and y axis.
// The fractional portion is then the amount between 0 and 1 within the tile.
// Then the last division by the tileset size is bringing us into the "tile-space"
// or the actual size of a tile between a normalized coordinate system on the tileset image.
float xoffset = frac( in.texcoord.x * map_size_in_tiles.x ) / tileset_size_in_tiles.x;
float yoffset = frac( in.texcoord.y * map_size_in_tiles.y ) / tileset_size_in_tiles.y;

// We can add this to the UV now. However remember that GL is bottom-left based so we
// will subtract Y from the uv position.
uv += float2( xoffset, -yoffset );

// Step 6) Match any missing image size.
uv *= image_ratio;

// Step 7) Return to the normal UV coordinate space if we are in GL.
uv.y = 1.0f - uv.y;

// Step 8) Return the final color.
return tex2D(tileset_sampler, uv);
}


 

The End!

And that’s it!

I’m sure any implementation you make will be different than this. This only renders a single layer of a tilemap and most maps are multiple layers. And like I said it doesn’t handle changing tiles very gracefully because you have to re-create the tilemap image and send it to your graphics hardware.

I can’t guarantee that any of the code discussed in the project is 100% accurate as well. If there are any problems or you would like some help do not hesitate to email me.

Here’s a quick demo of this working in a unity project: