Tile-map rendering in Tristeon

A Tile-Set is a grid-like object used to hold multiple 2D graphics, at once, at the expense of a single texture. Each cell in a Tile-Set grid is called a Tile. Tiles often take the shape of squares, due to the grid structure, but this is not always the case.

A Tile-Map, then, is a composition of tiles to form a scene or image. Tile-sets and tile-maps are a common practice on 2D level design, as it often accelerates the process because the art can be reused and adjusted, and specialized tools can be created.

In a traditional renderer, tiles are represented by 2D sprites. They are then given a position and are rendered one by one in a simple for loop. This approach works well for smaller levels, but as you may notice, with this approach the renderer is spending a lot of time individually rendering each sprite, causing it to scale at at O(n) speed. This approach is fine at a smaller scale but quickly becomes unusable if the user desires to create bigger levels.

To combat this issue, I have designed a tile rendering technique that utilizes GPU acceleration to severely improve the renderer’s scalability.

Summary

The technique I developed makes use of a full-screen fragment shader to sample tiles on a per-pixel basis. Thanks to this approach, tiles aren’t rendered one by one but instead only get sampled if their pixels are visible.

The technique consistently renders at O(1) speed as opposed to the original O(n) speed, significantly improving scalability. There are a few limitations which I will discuss at the end of the post.

Data

Tile-map
Tiles in Tristeon are represented by a one-dimensional array of Tiles. The Tile structure contains an index, which informs the renderer which tile on the tileset it is, and a tileSetID, informing the renderer which tileset is drawn on the given Tile.

struct Tile
{
	int index = -1;
	int tileSetID = -1;
};

A tile-map can contain multiple tile-sets, each tile-set is represented by a unique ID. As the amount of textures per shader is often limited, I iteratively render the tile-map multiple times with a different texture. Tiles that don’t contain the current texture get discarded.

In order to use this data on the GPU, the tiles first have to be uploaded to the VRAM. I have decided to use Buffer Textures (https://www.khronos.org/opengl/wiki/Buffer_Texture) to do so. Buffer textures are one-dimensional textures containing flat unfiltered data.

Creating a buffer texture is a simple process, and looks a lot like the creation of other more commonly used buffers:

//Creation
glGenBuffers(1, &tbo);
glBindBuffer(GL_TEXTURE_BUFFER, tbo);
glBufferData(GL_TEXTURE_BUFFER, sizeof(Tile) * _width * _height, tiles.get(), GL_STATIC_DRAW);

glGenTextures(1, &tbo_tex);
glBindBuffer(GL_TEXTURE_BUFFER, 0);

//In the render loop
glBindTexture(GL_TEXTURE_BUFFER, tbo_tex);
glTexBuffer(GL_TEXTURE_BUFFER, GL_R32I, tbo);

The tile-map is then represented in the shader using the structure below. The structure contains the buffer texture (samplerBuffer) and the width and the height of the level. It also introduces two new variables (tileRenderWidth, tileRenderHeight), which simply represent the width and the height of the rendered tiles in pixels.

struct Level
{
    samplerBuffer data;
    uint width;
    uint height;
    
    uint tileRenderWidth;
    uint tileRenderHeight;
};
uniform Level level;

Tile-set
As described earlier, a tile-set is a texture that is split up in a number of tiles. Within Tristeon, this always happens in a uniform way, the user is able to define the amount of tiles that occur horizontally and vertically and the amount of spacing (empty pixels) that exists in between them.

In the tile shader, a tile-set is represented as follows:

struct TileSet
{
    isampler2D texture;
    uint cols;
    uint rows;

    uint spacingLeft;
    uint spacingRight;
    uint spacingTop;
    uint spacingBottom;

    uint horizontalSpacing;
    uint verticalSpacing;

    uint id;
};
uniform TileSet tileSet;

The function below uses these parameters to sample a tile based on UV coordinates and the tile’s x and y coordinates on the texture.

vec2 getTileUV(vec2 uv, uint tileX, uint tileY)
{
    //Coords beyond our tileset mess up spacing so we clamp them
    tileX = tileX % tileSet.cols;
    tileY = tileSet.rows - uint(1) - (tileY % tileSet.rows);
    ivec2 texSize = textureSize(tileSet.texture, 0);

    //Determine the amount of pixels per tile
    uint tilePixelsX = (uint(texSize.x) - ((tileSet.spacingLeft + tileSet.spacingRight) + ((tileSet.cols - uint(1)) * tileSet.horizontalSpacing))) / tileSet.cols;
    uint tilePixelsY = (uint(texSize.y) - ((tileSet.spacingTop + tileSet.spacingBottom) + ((tileSet.rows - uint(1)) * tileSet.verticalSpacing))) / tileSet.rows;

    //Determine the start point of the tile depending on spacing
    uint startX = tileSet.spacingLeft + (tileX * tilePixelsX) + (tileX * tileSet.horizontalSpacing);
    uint startY = tileSet.spacingBottom + (tileY * tilePixelsY) + (tileY * tileSet.verticalSpacing);

    //Scale UV to tile coords, then normalize into texture coords
    float x = ((uv.x * tilePixelsX) / texSize.x);
    float y = ((uv.y * tilePixelsY) / texSize.y);

    //Add start pixels, also scaled into normalized texture coords
    float u = x + (startX / float(texSize.x));
    float v = y + (startY / float(texSize.y));
    
    return vec2(u, v);
}

While the function may seem a little messy, it simply determines the pixels of the tile and then offsets and scales the UV values to represent the tile as if it was a simple 0…1 texture.

Camera
Most 2D games allow some form of a dynamic camera, capable of movement and possibly more. In Tristeon, cameras can move and zoom in/out. The camera is represented using the following structure:

struct CameraData
{
    int posX;
    int posY;

    uint pixelsX;
    uint pixelsY;

    float zoom;
};
uniform CameraData camera;

The pixelsX and pixelsY inform the shader about how many pixels the screen contains. This is useful for determining which pixel is currently being sampled and thus which tile it should represent.

Technique

Rendering a full-screen shader
To start the technique off, I render a full-screen triangle, a technique described by Randall Rauwendaal in https://rauwendaal.net/2014/06/14/rendering-a-screen-covering-triangle-in-opengl/. This technique simplifies rendering a full-screen quad because it removes the need for any sort of buffers.

Fragment shader
The next step is to use the triangle’s fragment shader to determine which pixel represents which part of a tile. The goal within the main function of the fragment shader is to scale the screen UVs in such a way that we’re able to determine which tile is under the pixel and what UVs we need to send to the getTileUV() function.

Center UVs
Within texture coordinates, the (0, 0) point is defined as the bottom-left corner. In Tristeon, (0, 0) is set in the center of the screen and as such the texture coordinates need to be slightly adjusted:

vec2 coords = texCoord;
coords.x -= 0.5f;
coords.y -= 0.5f;

Camera position & zoom
The next step is to adjust the current coordinates to the camera’s position. Doing this early means we can use the coordinates to calculate the position on the grid in world space afterwards.

coords.x += float(camera.posX) / (camera.pixelsX / camera.zoom);
coords.y += float(camera.posY) / (camera.pixelsY / camera.zoom);

To be able to use the camera’s position (which is measured in pixels), we have to scale it down to uniform coordinates. The screen coordinates are usually represented using 0…1 coordinates, which simply represent { x / width, y / height}.

To achieve the same, we simply have to divide the camera’s position by the camera’s pixels. Zooming is then achieved by adjusting the amount of pixels the camera displays by dividing the pixel count by the camera’s zoom value.

Determine tile size
Using the camera’s pixels and zoom, we can determine the texture coordinate range of a tile on the screen.

float normalizedTileWidth = float(level.tileRenderWidth) / (camera.pixelsX / camera.zoom); 
float normalizedTileHeight = float(level.tileRenderHeight) / (camera.pixelsY / camera.zoom);

This can then be used to divide the screen up in a grid of tiles. Any pixels that represent tiles outside of the level’s dimensions can immediately be discarded at this point.

float tileX = (coords.x / normalizedTileWidth);
float tileY = (coords.y / normalizedTileHeight);
if (tileX >= level.width || tileY >= level.height || tileX < 0 || tileY < 0) 
    discard; //Discard all out of map tiles

Calculate tile index and UV
The tileX and tileY variables calculated previously can now be used to calculate both the tile’s index and the UV coordinates within the tile:

//Calculate tile index by taking the integer part of tileX and tileY
uint dataX = uint(floor(tileX));
uint dataY = uint(floor(tileY));
uint dataIndex = dataY * level.width + dataX;

//Calculate tile UVs by taking the decimal part of tileX and tileY
float tileU = mod(tileX, 1.0f);
float tileV = mod(tileY, 1.0f);

Read tile data
Using the tile’s index, we can now read the tile-map to figure out what tile is placed on this position. The texelFetch() function is used to read the buffer texture. It works similar to the texture2D() function except it takes an integer index to read the buffer’s texels directly.

//Read the tile's tile-set first and discard if it's not the one currently being rendered
int tileSetValue = texelFetch(level.data, int(dataIndex) * 2 + 1).r;
if (tileSetValue != int(tileSet.id))
    discard;

//Read the tile's value
int dataValue = texelFetch(level.data, int(dataIndex) * 2).r;
if (dataIndex == -1)
    discard; //Discard empty tiles

//Convert the index to x,y coordinates for the tile-set
ivec2 tileIndex = ivec2(dataIndex % int(tileSet.cols), tile / int(tileSet.cols));

Tile UV
The last step is to convert the data index and the tile’s UV into the UV to be used on the tile-set. We can use the getTileUV() function described in the tile-set section to calculate the UV by passing it the tile UV values we calculated earlier. This value can then be used to determine the fragment color.

vec2 tileSetUV = getTileUV(vec2(tileU, tileV), uint(tileIndex.x), uint(tileIndex.y));
FragColor = texture(tileSet.texture, tileSetUV);

Results

With the full tile-map shader in place (https://github.com/Tristeon/Tristeon/blob/master/bin/Internal/Shaders/TileShader.frag), we are able to yield good looking results at high speeds.

To get an idea of how performant the renderer runs, I’ve tested its performance at increasingly bigger tile-map sizes:

By eliminating the need to iterate over each tile and render them separately, the renderer practically renders at O(1) speed.

One thing to note however, is that the render time appears to increase slightly at the 1000×1000 tile-map which indicates that the buffer’s size becomes significant enough to play a noticeable role in the render time. The renderer likely still runs at O(n) (albeit a very flat curve) at larger tile-map sizes but unfortunately buffer textures are too limiting in size to test beyond the 1000×1000 tile-map.

Main objections

Shape limitation
The renderer as described works exclusively with square tiles, supporting other shapes such as hexagonal grids would require significant additional work.

Driver limitations
While features such as buffer textures may be supported on all devices that run OpenGL, they can still very well be limited in other ways. The minimum size that a GPU’s OpenGL drivers are required to support is set at 65.536 texels.

The algorithm uses a total of 2 integers per tile, each represented as a separate texel. If the graphics driver implements the minimum amount of texels as required by the standard, a total of 32.768 tiles are supported. This limitation may potentially limit the developer to smaller tile-maps of sizes such as 300×100 (30.000 tiles).

Future improvements

Easing size limits
The buffer texture is limited in size and may potentially be replaced with a SSBO (https://www.khronos.org/opengl/wiki/Shader_Storage_Buffer_Object) which by default supports a much greater minimum size of 128MB. Using SSBOs comes at a trade-off however because some older GPUs and Intel integrated GPUs might not support OpenGL 4.3.

Mip-mapping
The renderer is able to render a large number of tiles without any performance tradeoffs. However, the tile-map renderer loses visual quality at smaller zoom values. This happens because tile-set mipmapping does not work well as tiles blend into each other at lower mip-map levels. This can be solved by altering the mipmapping behavior or by separating the tile-set into separate tile textures upon creation.