tairu - an interactive exploration of 2D autotiling techniques

I remember since my early days doing programming, I’ve been interested in how games like Terraria handle automatically tiling their terrain.
- in Terraria, you can fully modify the terrain however you want, and the tiles will connect to each other seamlessly.
  - TODO: short videos demoing this here
once upon a time I stumbled upon a technique called…
bitwise autotiling
- I learned about it way back when I was just a kid building 2D Minecraft clones using Construct 2, and I wanted my terrain to look nice as it does in Terraria
 - Construct 2 was one of my first programming experiences and the first game engine I truly actually liked
- let’s begin with a tilemap. say we have the following grid of tiles: (the examples are interactive, try editing it!)
 
 <canvas is=”tairu-editor” data-tilemap-id=”bitwiseAutotiling” data-tile-size=”40”> Your browser does not support <canvas>. </canvas>
- for each tile, we can assign a bitset of cardinal directions like so:
 
 <canvas is=”tairu-editor-cardinal-directions” data-tilemap-id=”bitwiseAutotiling” data-tile-size=”40”> Your browser does not support <canvas>. </canvas>
- now given a tileset, such as the one below that I drew a while ago, we can assign each tile to a set of cardinal directions. I’ll indicate where there’s a connection between individual tiles with the letters N, E, S, W, standing for the cardinal directions North, East, South, and West.
 
 <ul class=”tileset-demo”> <li class=”full-image”> <img alt=”a 16-tile tileset of 8x8 pixel metal” src=”/static/pic/01HPHVDRV0F0251MD0A2EG66C4-tilemap-heavy-metal-16+pixel+width160.png”> </li> <li class=”tileset-pieces”> ES ESW SW S ESN ESWN SWN SN EN EWN WN N E EW W </li> </ul>
 - (it’s frustratingly hard to center individual letters like this in CSS. please forgive me for how crooked these are!)
- note that the state of connection for a given cardinal direction can be represented using two values: connected, and not connected. two values make one bit, so we can pack these four connection states into four bits, and use that as an array index!
 - for that to work though, we need to rearrange our tilemap somewhat such that we can index into it easily using our integer. assuming we pack our bits as NWSE (bit 0 is east, each next bit we go clockwise), therefore the final arrangement is this:
 
 <div class=”horizontal-tile-strip”> E S ES W EW SW ESW N EN SN ESN WN EWN SWN ESWN </div>
 
 packing that into a single tilesheet, or rather tile strip, we get this image:
 
 hint: you can actually just use the original image, but use a lookup table from these indices to (x, y) coordinates. this makes creating the assets a lot easier! (at the expense of some CPU time, though it is totally possible to offload tilemap rendering to the GPU - in that case it barely even matters.)
- in JavaScript, drawing on a <canvas> using bitwise autotiling would look like this: javascript for (let y = 0; y < tilemap.height; ++y) { for (let x = 0; x < tilemap.width; ++x) { // Assume `tilemap.at` is a function which returns the type of tile // stored at coordinates (x, y). let tile = tilemap.at(x, y);
 
 // We need to treat some tile as an empty (fully transparent) tile. // In our case that’ll be 0. if (tile != 0) { let tileset = tilesets[tile];
 
 // Now it’s time to represent the tile connections as bits. // For each cardinal direction we produce a different bit value, or 0 if there is // no connection: let connectedWithEast = shouldConnect(tile, tilemap.at(x + 1, y)) ? 0b0001 : 0; let connectedWithSouth = shouldConnect(tile, tilemap.at(x, y + 1)) ? 0b0010 : 0; let connectedWithWest = shouldConnect(tile, tilemap.at(x - 1, y)) ? 0b0100 : 0; let connectedWithNorth = shouldConnect(tile, tilemap.at(x, y - 1)) ? 0b1000 : 0; // Then we OR them together into one integer. let tileIndex = connectedWithNorth | connectedWithWest | connectedWithSouth | connectedWithEast;
 
 // With that, we can draw the correct tile. // Our strip is a single horizontal line, so we can assume let tilesetTileSize = tileset.height; let tilesetX = tileIndex * tilesetTileSize; let tilesetY = 0; ctx.drawImage( tilesets[tile], tilesetX, tilesetY, tilesetTileSize, tilesetTileSize, x * tileSize, y * tileSize, tileSize, tileSize, ); } } }
- and that gives us this result:
 
 <canvas is=”tairu-editor” data-tilemap-id=”bitwiseAutotiling” data-tile-size=”40” > Your browser does not support <canvas>. <img class=”resource” src=”/static/pic/01HPMMR6DGKYTPZ9CK0WQWKNX5-tilemap-heavy-metal-bitwise-16+pixel+width640.png” data-tairu-tileset=”1”> </canvas>
- but if you play around with it (or have already played around with it, and are therefore left with a non-default tilemap)
 
 …something seems awful about it doesn’t it?
 - something’s off about the corners. let me give you a fresh example to illustrate what I mean:
 
 <canvas is=”tairu-editor” data-tilemap-id=”bitwiseAutotilingChapter2” data-tile-size=”40” > Your browser does not support <canvas>. <img class=”resource” src=”/static/pic/01HPMMR6DGKYTPZ9CK0WQWKNX5-tilemap-heavy-metal-bitwise-16+pixel+width640.png” data-tairu-tileset=”1”> </canvas>
 - see that tile in the bottom left corner of the L shape? it’s missing a corner. the top-right corner, to be exact, which makes it visually disjoint from the tiles to the north and the east.
 (I’m totally not trying to say this implementation is an L so far)
 - i’ll cut right to the chase here and say it outright - the issue is that we simply don’t have enough tiles to represent corner cases like this!
 see what I did there?
- the solution to that is to introduce more tiles to handle these edge cases.
 - to represent the corners, we’ll turn our four cardinal directions…
 
 <ul class=”directions-square”> <li class=”east”>E</li> <li class=”south”>S</li> <li class=”west”>W</li> <li class=”north”>N</li> </ul>
 
 into eight ordinal directions:
 
 <ul class=”directions-square”> <li class=”east”>E</li> <li class=”south-east”>SE</li> <li class=”south”>S</li> <li class=”south-west”>SW</li> <li class=”west”>W</li> <li class=”north-west”>NW</li> <li class=”north”>N</li> <li class=”north-east”><a href=”https://github.com/NoiseStudio/NoiseEngine/” title=”NoiseEngine????”>NE</a></li> </ul>
 - you might think that at this point we’ll need 8 bits to represent our tiles, and that would make…
 
 256 tiles!?
 
 nobody in their right mind would actually draw 256 separate tiles, right? RIGHT???
 …right! if you experiment with the bit combinations, you’ll quickly find out that there is no difference if, relative to a single center tile, we have tiles on the corners:
 
 <canvas is=”tairu-editor” data-tilemap-id=”bitwiseAutotilingCorners” data-tile-size=”40” > Your browser does not support <canvas>. <img class=”resource” src=”/static/pic/01HPMMR6DGKYTPZ9CK0WQWKNX5-tilemap-heavy-metal-bitwise-16+pixel+width640.png” data-tairu-tileset=”1”> </canvas>
 
 these should all render the same way, despite technically having some new neighbors.
 what we can do about this is to ignore corners whenever zero or one of the tiles at their cardinal directions is connected - for example, in the case of E | SE | S:
 
 <ul class=”directions-square e-s”> <li class=”east”>E</li> <li class=”south-east”>SE</li> <li class=”south”>S</li> </ul>
 
 we can completely ignore what happens in the northeast, northwest, and southwest, because the tile’s cardinal directions do not fully contain any of these direction pairs.
 we can verify this logic with a bit of code; with a bit of luck, we should be able to narrow down our tileset into something a lot more manageable.
 we’ll start off by defining a bunch of variables to represent our ordinal directions:
 
 javascript ordinal-directions export const E = 0b0000_0001; export const SE = 0b0000_0010; export const S = 0b0000_0100; export const SW = 0b0000_1000; export const W = 0b0001_0000; export const NW = 0b0010_0000; export const N = 0b0100_0000; export const NE = 0b1000_0000; export const ALL = E | SE | S | SW | W | NW | N | NE;
 
 as I’ve already said, we represent each direction using a single bit.
 I’m using JavaScript by the way, because it’s the native programming language of your web browser. read on to the end of this tangent to see why.
 now I don’t know about you, but I find the usual C-style way of checking whether a bit is set extremely hard to read, so let’s take care of that:
 
 javascript ordinal-directions export function isSet(integer, bit) { return (integer & bit) == bit; }
 now we can write a function that will remove the aforementioned redundancies. the logic is quite simple - for southeast, we only allow it to be set if both south and east are also set, and so on and so forth.
 
 javascript ordinal-directions // t is a tile index; variable name is short for brevity export function removeRedundancies(t) { if (isSet(t, SE) && (!isSet(t, S) || !isSet(t, E))) { t &= ~SE; } if (isSet(t, SW) && (!isSet(t, S) || !isSet(t, W))) { t &= ~SW; } if (isSet(t, NW) && (!isSet(t, N) || !isSet(t, W))) { t &= ~NW; } if (isSet(t, NE) && (!isSet(t, N) || !isSet(t, E))) { t &= ~NE; } return t; }
 with that, we can find a set of all unique non-redundant combinations:
 
 javascript ordinal-directions export function ordinalDirections() { let unique = new Set(); for (let i = 0; i <= ALL; ++i) { unique.add(removeRedundancies(i)); } return Array.from(unique).sort((a, b) => a - b); }
 by the way, I find it quite funny how JavaScript’s [Array.prototype.sort] defaults to ASCII ordering for all types. even numbers! ain’t that silly?
 and now it’s time to Let It Cook™:
 
 javascript ordinal-directions let dirs = ordinalDirections(); console.log(dirs.length);
 
 output ordinal-directions 47
 forty seven! that’s how many unique tiles we actually need.
 you may find pixel art tutorials saying you need forty eight and not forty seven, but that is not quite correct - the forty eighth tile is actually just the empty tile! saying it’s part of the tileset is quite misleading IMO.
 phew… the nesting’s getting quite unwieldy, let’s wrap up this tangent and return back to doing some bitwise autotiling!
 - so in reality we actually only need 47 tiles and not 256 - that’s a whole lot less, that’s 81.640625% less tiles we have to draw!
 and it’s even possible to autogenerate most of them given just a few smaller 4x4 pieces - but for now, let’s not go down that path.
 maybe another time.
 - so we only need to draw 47 tiles, but to actually display them in a game we still need to pack them into an image.
 - we could use a similar approach to the 16 tile version, but that would leave us with lots of wasted space!
 think that with this redundancy elimination approach most of the tiles will never even be looked up by the renderer, because the bit combinations will be collapsed into a more canonical form before the lookup.
 - we could also use the approach I mentioned briefly here, which involves introducing a lookup table - which sounds reasonable, so let’s do it!
 - I don’t want to write the lookup table by hand, so let’s generate it! I’ll reuse the redundancy elimination code from before to make this easier.
 we’ll start by obtaining our ordinal directions array again:
 
 javascript ordinal-directions export let xToConnectionBitSet = ordinalDirections();
 then we’ll turn that array upside down… in other words, invert the index-value relationship, so that we can look up which X position in the tile strip to use for a specific connection combination.
 
 remember that our array has only 256 values, so it should be pretty cheap to represent using a Uint8Array:
 
 javascript ordinal-directions export let connectionBitSetToX = new Uint8Array(256); for (let i = 0; i < xToConnectionBitSet.length; ++i) { connectionBitSetToX[xToConnectionBitSet[i]] = i; }
 and there we go! we now have a mapping from our bitset to positions within the tile strip. try to play around with the code example to see which bitsets correspond to which position!
 
 javascript ordinal-directions console.log(connectionBitSetToX[E | SE | S]); output ordinal-directions 4
 
 TODO: The value from the previous output should not leak into this one. how do we do this? do we emit extra pushMessage calls inbetween the editors so that they know when to end? maybe use a classic context instead of a module? or maybe have a way of sharing data between outputs? (return value?)
bitwise autotiling is a really cool technique that I’ve used in plenty of games in the past.
- as I mentioned before, I’ve known it since my Construct 2 days, but when it comes to any released games [Planet Overgamma] would probably be the first to utilize it properly.
  
  TODO video of some Planet Overgamma gameplay showing the autotiling in action
  - this accursed game has been haunting me for years since; there have been many iterations. the autotiling source code of the one in the video can be found here.
but one day I found a really cool project called Tilekit
- (of course it’s really cool, after all rxi made it)
  - for context rxi is the genius behind the Lua-powered, simple, and modular text editor lite that I was using for quite a while
    after a while I switched to a fork - Lite XL, which had better font rendering and more features
    I stopped using it because VS Code was just more feature packed and usable; no need to reinvent the wheel, rust-analyzer just works.
    the LSP plugin for Lite XL had some issues around autocompletions not filling in properly
    
    it’s likely a lot better now, but back then I decided this is too much for my nerves. while tinkering with your editor is something really cool, in my experience it’s only cool up to a point.
the cool thing with Tilekit is that it’s more than just your average bitwise autotiling - of course it can do basic autotiling, but it can also do so much more
- if I had to describe it, it’s basically something of a shader langauge for tilesets. this makes it really powerful, as you can do little programs like
  - autotile using this base tileset
  - if the tile above is empty AND with a 50% chance
    then grass
  - if the tile above is solid AND with a 10% chance
    then vines
  - if the tile above is vines AND with a 50% chance
    then vines
- well… it’s even simpler than that in terms of graphical presentation, but we’ll get to that.
- I mean, after all - bitwise autotiling is basically a clever solution to an if complexity problem, so why not extend that with more logic and rules and stuff to let you build more complex maps?
  - of course Tilekit’s solution is a lot more simple, streamlined, and user-friendly, but you get the gist.