Adventures in Bitmasking

I decided to go with a bit of a different format today. I’m not sure what gave me the idea to make an infographic but I was making a lot of images for the post anyway and I thought “Hey, why not?”  Hopefully that image mostly speaks for itself but in case it doesn’t here’s a quick rundown of the process:

In order to know which graphical tile we need to render for a particular space we need to somehow take a look at the spaces around it.  Now this could be accomplished by lots of if or case statements but using a little math it’s much easier to handle.  We’re using a 4 bit number to create a hash for each space that identifies what the tiles around it look like. If the space has a value of 14 that means there is no tile above it but one to it’s left, one to it’s right and one below it. This will always be the case for a tile of value 14, and all tiles in this situation will have a value of 14. Once we have this value, you know which graphic tile it needs and if you designed your graphics well it will all fit together for any combination. The graphic set I made here is just designed to illustrate which of the 4 sides have a connection and which don’t.

Moving to 8 Bit

This is great for some cases but it can be graphically kind of limiting.  What happens if you care about the corners? Well that’s what I had to deal with for my digging game.  The graphics for this game are actually inverted from how I drew them on the info graphic because you’re cutting out tunnels from otherwise solid land.  Luckily we can just use 8 bits (4 for NSEW and 4 for the corners) and have every case available! Now for those of you good at binary math you might have realized that would lead to 256 different combinations! That’s way too many graphics to make but we can cut it down to 48 unique tiles because not every situation cares about all the corners.  In fact if you just draw some examples out for yourself you’ll notice that we only care about a corner with both sides adjacent to the corner are empty.  Take a look at this example:

Here you can see how in the first and second pictures you can see how the lower right corner matters for the center piece’s shape. On the other hand between the second and third picture you can see how the other corners don’t affect the shape of the center piece at all.  That simplifies from 256 case to just the 48 cases you can see here in my tilemap: (Plus some other tiles for various other things)

There’s still two problems.
1. I made the tilemap art in the way that was easiest from the art side, not the coding side or the order is all over the place.
2. We need to somehow map the 256 possibilities to the correct 48 graphic values.

Both of these problems can be dealt with at the same time by using a look-up table.  The job of this look-up table is to map from 0-255 -> 0-47 depending conditionally on the corner pieces. You can implement this however you want, probably an array where the indexes 0-255 correspond to the result of the bitmasking and it spits out the graphic tile value 0-47.  So, first lets talk about the bitmask we’re going to use for the 8-bit case.

The way I’ve broken it up is so if you just look at the non-corner bits (4 most significant) you’ll get a base case, then you add the corner case to it and you end up with a unique value. This makes it easier to come up with the look-up table because the non-corner cases are largely what defines the tile’s shape and they will be next to each other.  Next I made a table which defined how all 256 values translate:

You can see how some bits have an X instead of 0 or 1. These are the corners that don’t matter for that particular base case.  The “Lower Bits Sum” column shows all values that row accounts for when you do all combinations of 0 and 1 for any x’s.  Hopefully this table makes sense, the first 4 numbers (including x’s) give the 0-256 value that results from bitmasking and the final value column is the index on the tileset graphic I posted above.  You can see they are all out of order because like I said I made them before really thinking about this.

Hopefully this helps people if you need to use something like this in the future. It’s not too complicated once you lay it all out and it’s much easier and cleaner than having all kinds of branching and crazy logic in your code.

Beta testing

The mole digging game I’m making is almost ready to have people start beta testing. It’s very much a prototype at the moment, the core functions are mostly in there but there’s no real aspects to make it a game at this point, I suppose it’s a mole digging simulation.  I want to start getting feedback early and try to be really iterative in the game design process so if you want to help follow this link to sign up on testflight:

(Edit: I took the link out because I’m pretty sure bots were spamming it. If you’re interested e-mail me)

2 Responses to “Adventures in Bitmasking”

  1. Mike says:

    Very useful – thanks for taking the time to write it up!

  2. Ryan says:

    Great post! Thanks for sharing this info. It’s always fun to see how a bit of logic and math can condense a complex problem.