Bitwise Tilemapping
“Intelligently” generating tilemaps
September 20, 2017
I’ve read a few posts on bitwise tilemapping and I think they kind of over complicate the idea so I wanted to take a whack at explaining it.
The basic idea is that, instead of needing to meticulously place every tile for a given map (slow, manual), you can mathematically calculate what tile should go where (fast, automatic!) depending on its surrounding tiles. This means you can basically say “land here” on a map and it will place the proper land tile by accounting for the surrounding tiles. This is how most level editors with “brushes” work. The “brush” is just calculating the proper tile to use for a given connection. It may seem like magic but this is pretty easy to do on your own!
Imagine you have a single tile and imagine a data structure that says whether a tile exists in a given direction from that tile. So if I’m checking the North, South, East, and West directions, my data structure would be “NSEW”. For each of those directions, a tile can either exist at that position or not, meaning each direction can be either True (tile exists) or False (no tile).
So a tile with only a tile to the north of it would be “TFFF”. To only the south and the west would be “FTFT”. Look familiar? This is just binary! So TFFF = 1000 = 8 and FTFT = 0101 = 5. Hence, every unique combination directions yields a unique number from 1 to 15. You can also rearrange your “data structure” to make the values different — so instead of NSEW you could use SENW or something like that. Note that your bitwise numbers would change, but as long as you are consistent with how you “encode” the directions you’ll be fine.
With a direct mapping of unique directions to unique number, you can build a simple look up table to tell your game what sprite should go where. So for the following tile map:
A calculated bitwise index then maps to a sprite. Note that you can also easily check corners by just expanding your data structure to include those checks, something like N|S|E|W|NE|NW|SE|SW
Why “Bitwise”?
Although what I presented suggests that you just convert from binary to integer, the term “bitwise” comes from the fact that older ways in which you did this likely used actual bitwise operators for determining the correct tile (to conserve memory). So “North” was likely hardcoded as 1000, South as 0100, East as 0010, and West as 0001. If a tile existed in those directions, you would “logical or” combine them, so NORTH | SOUTH = 1100 = 12, which then maps to a sprite value. You could also still do it this way!
Why not just count?
In doing the operation “bitwise”, you’re assigning unique powers of 2 to every possible neighbor tile, and hence ensuring that (bitwise) combinations of the neighbors are unique and non-repeatable. If you just assigned random numbers, you run into two issues:
Tile direction combinations aren’t guaranteed to be unique. If you just used the numbers 1-4 for directions North(1), South(2), East(3), West(4), different directional combinations would yield the same result in the created lookup table. For this example, a tile with a neighbor to the North(1) and South(2) would yield a lookup value of 3, the same value as a tile with a neighbor only to the East(3).
If you were smarter about your assignment and did something like North(12), South(13), East(18), West(45), you would generate unique table lookup values, but they wouldn’t necessarily have any meaningful relationship to each other. Assigning directional values in a bitwise manner allows them to maintain a small memory footprint and be deterministic and open for operations — if you want to check if a tile exists to the North of a tile with a bitwise value (and you’re storing the bitwise value), you can just use if(value & NORTH > 0).
Published on September 20, 2017.