So, we have a procedurally generated biome map, where each pixel is an individual biome. If we zoom in, it's obviously quite pixelated. If we add sprites, it just doesn't look right (besides the lighting and colors)

We have reasonably detailed sprites on a single-colored squares. It's just ugly. We need to add some texture/detail.

Auto-tiling

 

Enter auto-tiling (or transition tiles): a method to automatically place tiles with texture so that each tile matches perfectly with their neighbours. It's a bit of a wild west out there in terms of approaches, so here are some resources (or resource lists) that I found useful:

https://pixelation.org/index.php?topic=9865.msg107117#msg107117
https://gamedevelopment.tutsplus.com/tutorials/how-to-use-tile-bitmasking-to-auto-tile-your-level-layouts--cms-25673
http://www.cr31.co.uk/stagecast/wang/blob.html
https://www.codeproject.com/Articles/106884/Implementing-Auto-tiling-Functionality-in-a-Tile-M

https://gamedev.stackexchange.com/questions/32583/map-tile-terrain-transitions-with-3-4-different-types
https://www.gamedev.net/forums/topic/606520-tile-transitions/
https://gamedev.stackexchange.com/questions/26152/how-can-i-design-good-continuous-seamless-tiles
http://allacrost.sourceforge.net/wiki/index.php/Video_Engine_Visual_Effects#Transition_Tiles
https://web.archive.org/web/20161023185925/http://www.saltgames.com/article/awareTiles/
https://www.gamedev.net/search/?q=tile%20transitions&fromCSE=1#gsc.tab=0&gsc.q=tile%20transitions&gsc.page=1
https://www.gamedev.net/articles/programming/general-and-gameplay-programming/tilemap-based-game-techniques-handling-terrai-r934/
http://www-cs-students.stanford.edu/~amitp/gameprog.html#tiles
http://playtechs.blogspot.co.uk/2007/04/tileset-design-tip.html
https://opengameart.org/forumtopic/auto-tiling-standardization
https://forums.tigsource.com/index.php?topic=21237.0
http://www.pascalgamedevelopment.com/showthread.php?22862-Tilemaps-and-autotiles
https://gamedev.stackexchange.com/questions/125284/what-is-the-term-for-a-3x3-tile-set-used-to-create-larger-areas/125285
https://forum.unity.com/threads/2d-tile-mapping-in-unity-demystified.441444/

Quite a few.

There are two main ways to consider art when using autotiles: using masks, or using premade textures. A good example is shown here:

Autotiling example

Showing image /sigil-of-kings-website/assets/2018/02/Autotileex.gif

Blend masks example

http://allacrost.sourceforge.net/wiki/images/3/34/Blendmaskex.gif

The premade tiles have the obvious benefit that they can be very nicely done, but of course they are tied to the content they represent.  The blend masks do not look as good, but are easier to develop, and they are more flexible in terms of what textures we want to seamlessly mix. I decided to use masks as I want transitions between any biome: for 16 biome types, that's 120 unique combinations. It's not an option to ask an artist to develop 120 different autotiles, that needs quite a bit of money and time. And also, that would have no variation; each autotile would be replicated all over the place, so it would be easy to distinguish patterns.

 

Grid shifting

The first naive thought that comes to mind (and I went with it for a while actually) is "ok, we have a tile, it is neighbour to 4 or 8 other tiles, so generate masks according to that relationship". Example here. As one can see, the 4-connected version is less interesting than the 8-connected version (and we don't want less-interesting), but the 8-connected version results in a lot of combinations! So what do we do? Well, we shift the grid. This way, we always have 4 potentially different tiles (quarters of them anyway)

Below, we shift the whole grid top-left by half a tile. Now, each grid cell (red) always contains parts of 4 tiles.

While this is mentioned in a few articles, it's demonstrated perfectly in a non-technical article, here. That's what sold me, as I find the results amazing!

 

Reducing unique combinations

So, that's what I mostly found so far in reference material. Now, a 2x2 grid as described can contain 4 different biomes. That's 4 bits, therefore 16 possible total combinations/arrangements. Here's how they look like (Showing image /sigil-of-kings-website/assets/2018/02/APGraYf_thumb740.gif

 

In the "16 most basic tiles" above, we can observe the following:

  • No 16 can be expressed by transforming 15 (180 deg rotation)
  • No 11,13,14 can be expressed by transforming 10 ( 90,180, 270 deg rotation)
  • No 3,9,7 can be expressed by transforming 1 ( 90,180, 270 deg rotation)
  • No 2,6,8 can be expressed by transforming 4 ( 90,180, 270 deg rotation)
  • No 5,12 contains no spatially varying data

This implies that the only unique tiles are 1,4,10,15,5,12. Furthermore, the only unique tiles with spatially varying data are 1,4,10,15. So, that is 4 tiles instead of 16. We can arrange such a mask of 4 tiles like this:

This has a nice continuous shape, if for example we want to ask an artist to draw some of those. Note that with this arrangement, the transformation will differ, as now the masks are already transformed compared to what I showed above. What's really important is that the amount of white vs black at the borders that contain both needs to always match, so that tiles are seamlessly combined. In my case above, I'm splitting them at 50%, but that's of course configurable. What I'm not going to cover, as I've given it some thought and gets very complicated, is to support variable black/white border percentages, ensuring that they match There are many more complications involved and I'm not sure if it's worth it in the end.

So, now we have 4 unique combinations. These can be nicely stored in an RGBA texture (one mask per channel) by converting the above 1x4 tile image. In the shader, given a mask value in [0,15], we effectively do the following:

mask = ... // obtain mask value from 4 underlying biome map tiles. Value in [0,15]
(mask_unique, transform) = get_transform(mask); // use a lookup table to get the unique mask index [0,3] and the transform needed
uv2 = apply_transform(uv, transform); // transform the texture coordinates
mask_rgba = sample_mask_texture(uv2); // sample the mask values
mask_value = -1;
switch(mask_unique)
{
    case 4:  mask_value = 0; break; // whole mask is empty
    case 5:  mask_value = 1; break; // whole mask is full
    default: mask_value = mask_rgba[mask_unique]; // get the component that we need
}

Most of the above can be done in the vertex shader, whereas the last two steps (sampling the texture and getting the component) need to be done in the pixel shader. So, it's quite cheap.

Rendering tiles

So, we have a method to render tiles given a very small number of masks. How do we render the tiles? Here's the naive approach, for a 512x512 biome map:

  • We have 16 biome layers, so I assign each a priority. E.g. shallow water covers coast. Water covers shallow water and coast. Deep water covers water, shallow water and coast. And so on.
  • For each layer, we generate tile render data as follows:
    • For each tile corner in the biome (513x513 grid of points)
      • Sample the 4 adjacent biome types (clamp to border if out of bounds)
      • Create the mask where we set 1 if the layer is equal or higher priority than current, or 0 if the layer is of lower priority than current
      • Based on the mask value, calculate unique mask index and transform, and store in this tile's render data

So, now we have a list of 513x513x16 tiles = 4.21 million. That's quite a lot. But as I said, that's the naive version. Observations:

  • When the unique mask index corresponds to constant 0 (mask_unique index == 4), we don't need to consider the tile for rendering.
  • When all of the four biome values in a tile are of higher priority than the  current layer, this means that the tile will be completely covered by higher priority layer tiles, and therefore we don't need to render it.

By applying these two, for my test map I reduced the number of tiles to 0.4 million, which is 10x better. Of course, that's still a lot, but it doesn't take into account any spatial hierarchy and other optimisations that could be done.

Here are some examples using the above un-nice mask. Zoomed-out:

Showing image /sigil-of-kings-website/assets/2018/02/noautotile_zoomout.webp

Zoomed-in

Ok, so my mask looks bad, and there's little to none variation, so you can see patterns everywhere.

Increasing variation

Using 256x256 masks, a single RGBA texture needs 256K of memory. We can have a texture array of such masks, using however many layers we can afford memory-wise. In runtime, we can select the layer based on various conditions. E.g. some texture layers could contain transition masks for particular biomes, or more generally, we can select a layer based on a function of the tile coordinates.

Next...

Next post will be about procedurally-generating lots of masks, using distance fields versus using binary masks, and also determination of locations for placement of props.