A technique for automatically selecting the correct tile from a tilemap.

I originally wrote this as a reply to a question on TIGSource and I figure it’s worthy of expanding and repeating here.

The problem: We have generated a neat platformer level, and want to be able to automatically lay neighbour-sensitive tiles over it so that they fit properly.

**Neighbour Sensitive Tiles**

Super Mario’s tiles are not neighbour sensitive; the stone block always looks the same if it’s floating alone or if it’s part of a wall.

That’s fine for many games, but can look out of place if you’re trying to create a more organic feel in a level, or just wanting to cut down on repeated patterns. Neighbour sensitive tiles overcome this by matching their appearance to the presence of their neighbours.

**A 1-bit Map**

Let’s imagine that with some clever techniques we have generated a level layout for a platformer game that consists of either stone or empty air at each grid location. This can be represented as a 1-bit image – that is each pixel’s state will be determined by a single bit, so either on indicating rock or off to indicate open air. Here’s a section of such a map, greatly enlarged and with grid lines added:

**A Tileset**

A tile set is simply a collection of the graphics that may be used to fill in a map. Mario’s tileset is quite small, consisting of just a few different types of block and scenery, whilst ours will have many graphics for the same type of tile:

**Valuing Neighbours**

To determine which tile should go at each spot on the map, we shall examine that spot’s immediate neighbours (for now we’ll ignore diagonal neighbours.) Rather than writing a huge if/else-if statement to handle all the possible combinations of neighbours, we will use a system that assigns values to each direction.

A value is found for each location by looking at its neighbours and adding up the values for whichever ones have stone present. So if the spot we’re examining has a neighbour above it that is also filled with stone then it is given the value 1. If it has stone-filled neighbours above and below then the value is 1 + 4, so 5.

You may notice that the values assigned to the directions are the same as the values of the positions in a binary number and this is no surprise; both are ways of representing possible combinations of 4 units which can each be in an on or off (stone or air) state.

Here is the map segment with the value of each tile filled in. You might like to manually work out the value for a couple of the tiles yourself so you’re clear on how it works.

**Adding the Tiles**

The order in which the tileset is laid out above is not arbitrary; it is laid out so that each tile matches what would be expected of a tile in the map that would be assigned that value. Once we have a value assigned for each spot on the map we just need to look up that number in the tileset and place the correct tile there:

Wonderful!

**Taking it Further**

**Part One – Removing Air**

Whilst the above works very neatly for platforms floating in air, it doesn’t yet fully handle two tile types.

Instead of a platformer imagine we’re working on a top-down 2D RTS with two tile types of grass and water. In such a case we would expect every spot on the map to have a tile graphic present; there’s no open spaces like in our platformer. This means that every spot on the map will need to have a value generated from its neighbours to determine which tile fits there.

We can use exactly the same neighbour valuing system as before, but we now need a way to differentiate between there being grass or water at the spot being examined itself. This is actually very simply done – just add an extra value for the location itself, following the same 2 to the power of n pattern from the other values:

Let’s decide that the presence of water means you do add on that position’s value, whilst the presence of grass means you do not. So a grass tile surrounded on all sides by grass would be numbered at 0. A grass tile with water to the top and left would be 1 + 8 = 9. A water tile surrounded on all sides by grass would be 16. A water tile with water on all sides would be 1 + 2 + 4 + 8 + 16 = 31

**Part Two – Greater Variety**

How do we handle adding additional types of terrain?

Let’s say we have three types of terrain in our top-down game: water, grass, and forest. As well as water and grass meeting, we must now also deal with water and forest meeting as well as grass and forest meeting.

Previously there was two possibilities for each neighbour position (grass or water) so we used a **bi**nary counting system. There’s now three possibilities so we shall use a **tri**nary counting system. Our neighbour valuing system needs to be adjusted to match the new counting system:

Just as the binary counting system followed the pattern of 2 to the power of n, this follows the pattern of 3 to the power of n.

Using a trinary system each position has three possible states: grass, water, forest; or 0, 1, 2. When there is grass in a given position, we ignore the value (multiply it by 0). When there is water in the position we add on the value given (multiply it by 1). When there is forest in the we add on twice the value (multiply it by 2.)

So if we had a tile that was forest with water above it, water to the right, forest below and grass to the left: 81 * 3 + 1 * 2 + 3 * 1 + 9 * 3 + 27 * 0 = 275

You might notice at this point that you’ll need to draw 324 tile graphics to cover all the possible combinations in a three-terrain map. This is a lot of tiles to draw by hand. I would strongly advise looking into at least partially automated methods of producing the multitude of tile combinations.

Of course the system can be extended in just the same way for greater numbers of terrain types, but the number of tile graphics you would need would be even more huge. Instead I would recommend placing some limits on what tiles are allowed to neighbour one-another. For instance if forest and water tiles are never allowed to directly touch then the above example will need several hundred less tile graphics.

Thanks, this is a really elegant solution – fantastic.

This helped so much, I implemented this with a couple extra if statements when I did need to check the diagonals, instead of makinga huge tileset. This method really is brilliant though.

Pingback: Procedural terrain generation « a bag of bugs

Pingback: Light using PixelBender with Normal-, Specular- and Occlusion Mapping | Andrew van der Westhuizen

Pingback: Dev diary number seventeen : Bitwise Tilemapping ‹ Sauropod Studio

You might want to have a read of this article

http://www.gamedev.net/page/resources/_/technical/game-programming/tilemap-based-game-techniques-handling-terrai-r934

… which discusses how to dramatically reduce your combinations of tiles by defining a fixed order the different types of terrain overlap with.

How do you deconstruct this? For instance, using your example of a tile resulting in the hash 275, how would I got about breaking that down to get the individual neighbor type information?

Easier to first explain with the simpler “binary” version from the start of the post. As this pseudocode shows you start with the largest value direction and see if the hash code is greater or equal to that value, if it is then we know there’s a solid tile in that direction. If there is a solid tile in that direction we then subtract that direction’s value from the hash before proceeding to the next highest value direction.

if (hash >= 8) {

isSolidToLeft = true;

hash = hash – 8;

}

if (hash >= 4) {

isSolidBelow = true;

hash = hash – 4;

}

if (hash >= 2) {

isSolidToRight = true;

hash = hash – 2;

}

if (hash >= 1) {

isSolidAbove = true;

}

In the “trinary” (or any higher order of magnitude you might like) version each direction can contribute its value multiple times so we need to do some division to see how many times its value has been contributed. This code would deconstruct the grass-water-forest example given:

if (floor(hash / 81) >= 2) {

tileHere = forest;

} else if (floor(hash / 81) >= 1) {

tileHere = water;

} else {

tileHere = grass;

}

hash = hash % 81;

if (floor(hash / 27) >= 2) {

tileToLeft = forest;

} else if (floor(hash / 27) >= 1) {

tileToLeft = water;

} else {

tileToLeft = grass;

}

hash = hash % 27;

// etc. for the other directions

If you’ve not met it before, the “%” modulo operator gives the remainder from a division. So (82 % 81) evaluates to 1, as does (163 % 81) and (1 % 81). It neatly removes the “influence” that the 81-valued direction has had on the hash value.

i found this very insightful, and it inspired me to investigate my own techniques and certainly helped my image naming conventions

i wanted to point out it doesn’t cover the “inside” squares as i call them, this is useful for tile mapping

so say you have a square block, 9×9, but then you make it hollow:

xxx

x0x

xxx

The corners will end up looking odd, the only solution of course, another set of variations, backwards corners, I loose count, I’m seriously trying to find some sort of alpha overlay method for my game to save time

For “inside squares” you need to extend the bitwise method to also cover the tile corners.

So, again counting clockwise from the top, you have 1, 2, 4, 8, 16, 32, 64 and 128, where 2, 8, 32 and 128 are the corners.

This results in a tileset of 256 tiles (instead of 16 for just edges). Quite a lot.

However, if you use a ‘Blob’ tileset, you only need 47 tiles. This will cover carpet-like areas with external and your required internal “inside” corners.

See my website ‘cr31’ for information on Wang tiles, Blob tilesets as well as a tile explorer etc etc.