Bitmasking

Posted on Jul 3, 2020

The game I was working on (Unexpected Orcs, sadly unfinished) used tile-based terrain, and in an effort to give it more visual appeal, my team and I thought “wouldn’t it be cool if we could give the walls a bit of perspective and have borders between different tile types”. Of course, we weren’t the first to think this and we almost certainly won’t be the last. We did a bit of research and came across the technique of bitmasking tile textures, this article was particularly helpful (I highly recommend reading that article first if you don’t know what tile bitmasking is, it explains it much better than me and has pretty pictures. I do, however, give it a red hot go below if you don’t want to read it).

Tile bitmasking automates the laborious process of hand placing border tiles where one or more tile types comes together, or in our case, allows us to have borders at all on generated terrain. Unfortunately, to do tile bitmasking you need A LOT of textures for each type of tile, 48 to be exact. Due to this, we ended making a system that only needs two textures for each terrain type and can generate all the required tiles for us.

This article will first go over what bitmasking is and how it applies to tiles and textures. Following that I will discuss our approach to it and how our tile texture generation works. I would suggest that now is the prefect time to go and make yourself a hot beverage as I tend to ramble on a tad.

Note: Many engines have this set up for you, usually under a name like “auto-tiling” so you might want to look into that! Unexpected Orcs uses a custom engine, so we had to implement it ourselves. Even if your engine supplies this feature for you, it might intrest you to know how it works under the hood!


What is bitmasking?

Bitmasking is fairly common technique used in the computing world and applies to much more than just tiled textures. The basic premise behind it is that you can store a group of binary values as a single value by using each storage bit individually. For example if you had a 4-bit integer, you could define the bits to be:

Bit 3 2 1 0
Value Boss room unlocked Mini-boss killed Chest opened Has key

If the value of the integer was 12 (1100 in binary), it would show that the player has unlocked the boss room and killed the mini-boss but hasn’t opened the chest or found the key. This is because the 3rd and 2nd bits are both 1 indicating TRUE while the 1st and 0th bits are 0, meaning FALSE.

If you want to know the state of a single boolean, you can create a mask for the desired bit (a bitmask, this is where the name is from!) and perform a bit-wise AND on the value. For the example above, the mask for the mini-boss being killed would be 0100. When you bit-wise AND the state (1100) and the mask (0100) you are left with 0100, indicating that the mini-boss is dead. If you wanted to know whether or not the chest was open, you would use the mask 0010. 1100 bit-wise AND 0010 gives you 0000, therefore the chest is still closed.
Generating the mask is straight foward when using bit-shifting. Take a look at this psuedo code example:

// returns if the nth bit of value is on or off (starts from 0)
function getBit(value, n) {
  // the << operator is called a left shift
  // the value to the left of the operator is the one being shifted
  // the one to the right indicates by how much
  // eg. 5 << 2 would return 20
  // this makes little sense until you look at the binary
  // 5 = 101, 20 = 10100. The 101 as been shifted left by 2 bits
  mask = 1 << n
  return (val & mask) > 0
}

state = 6 // 1100

getBit(state, 2) // true, mini-boss is dead
getBit(state, 1) // false, chest is NOT open

How do we apply it

In order to place tiles with the correct border texture, we need to know what the surrounding tiles are and how they are placed. Each tile has eight neighbours (four directly adjacent and four on the diagonals) and we need to know whether or not each of those neighbours is the same tile type as the centre one or not. Sounds like the perfect application for bitmasking eh?

Using an 8-bit number we can describe every possible combination of the surrounding eight neighbours, 1-bit per neighbour. We simply check each neighbour in turn and set its corresponding bit to be either 1 if it is the same as current tile, or 0 if it’s not. What we are left with is a value (we will call this the bitmask even though it’s not a bit-mask) maps directly to the shape of the border. Pretty simple!

It was at about this point that I realised that something being simple defintely does not make it easy. We are left with 256 possible bitmask values! I don’t know about you, but I defintely don’t want to be drawing that many tiles per tile type! Thankfully there are multiple values that end up with the same border shape which whittles the number down to 48 unique tiles and this ican be improved further to 16 when you factor in rotations. Even so, that’s a lot of tiles to draw (especially when you posses the artistc talent of a wet towel and need to keep updating your textures. I don’t want to have to change 16 textures just because I improved the stone texture!).

I quickly came to the conclusion that doing that by hand simply would not do. Time for more automation!


Automatic texture creation

I want to quickly preface this section by saying we managed to simplify this problem a lot by the fact that we only ever have flat borders between textures. A lot of the pixel art textures out there have have really nice transations between tile types. They’ll have ripples where the ocean meets the land and tufts of grass where the dirt path winds through. Not only does this require art skills we don’t have, it also drastically increases the complexity of generating these textures (it’s something I’d like to explore someday, but it’s out of scope of what we’re doing here).

Now that’s out of the way, let’s jump in! As I alluded to earlier, there are only 16 border shapes when you ignore rotations so we need to create a mask for each of these shapes which you can see below:

Bitmasking border shapes

For reference, we only use the black part, but it was kind of hard to tell what was going on so I added in the blue to make it a bit clearer. The blue mimicks the shape that the 3x3 area of tiles would make for any given mask to apply, ie you’d use the third mask when there is only one tile that is the same type as the centre one adjacent to it. If you’d like to see how I derived these shapes (yes, for some reason I decided to figure them out for myself instead of just googling it), you can download the spreadsheet I used here.

How do we use these masks? I’m glad you asked.

  1. Get the bitmask of a tile from the tile data
  2. Figure out which of the 16 border shapes we need
  3. Figure out how the shape needs to be rotated for the bitmask
  4. Rotate the border shape mask, colour it, and slap it over the top of the base texture

The most difficult part of all this was figuring how all 256 possible bitmask values translated into the 16 shapes and their rotations. You had better believe that I made a big ol’ spreadsheet of every single bitmask to figure it out. I probably could have drawn all the tiles I’d ever need in the time it took me to do it, but now that I’ve done it, you don’t have to.

We could just create a map that points from the 256 values directly to a border shape and rotation to use but due to the way our game handles caching textures this was not optimal. Instead we opted for an intermediate step where we first reduce the bitmask to one of the 48 values we mentioned earlier (where we treat rotations of the same border mask as separate entites. Our textures are rotation-specific so we can’t rotate the final texture, only the border mask can be rotated so we need to know the pre-rotation bitmask value). We then map these 48 values to a border shape and a rotation. Since we wanted some perspective, our walls need two textures each. To know which one we need to use we can use the bitmask to see if the tile directly below is the same type or not. All that’s left to do is combine the border mask with the base texture and we are done!

I’m not sure how well all of that came across in text, so here is some psuedo code to fill in the gaps:

function getTileTexture(tileType, bitmask) {
  // 1st reduction to one of the 48 values
  bitmask = bitmaskMap.get(bitmask)
  if(isCached(tileType, bitmask)) {
    // don't generate if we've already generated it
    return getCached(tileType, bitmask)
  }
  // the magic happens in here
  texture = generateTexture(tileType, bitmask)
  return texture
}

function generateTexture(tileType, bitmask) {
  // 2nd reduction into one of 16 values
  borderMask = bitmaskImage.get(bitmask)
  // get the border rotation
  rotation = bitmaskRotation.get(bitmask)

  // rotate and colour the border
  borderMask = rotate(borderMask, rotation)
  borderMask = colour(borderMask, borderColour(tileType))

  baseTexture = getTexture(tileType, bottom=isBottom(bitmask))

  // smack the borderMask over the top of the bas texture
  texture = combine(baseTexture, borderMask)

  cache(texture, tileType, bitmask)

  return texture;
}

Conclusion

Bitmasking is a really great technique for a number of things and bitmasking the tile textures allows us to do some cool stuff and certianly helps break up repatative textures. Our solution was a tad on the clunky side but it got the job done and, if I ever implement this technique again I’m sure I’ll do a better job at it.
One of the hardest desicions to make was whether to generate all the textures before hand and save them or to generate them at runtime as they’re needed. There are certainly pros and cons to both approaches. In our case, we were constantly tweaking the tile textures so it was simpler for us to have the generation done at run time rather than have to run the tile generation each time we updated the textures. The performance overhead is also pretty minimal, but if you were struggling for speed you might prefer to pre-generate the textures.

If you have any questions, feel free to get in touch! I’m more than happy to answer any questions you might have.