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
so to help us learn, I made a little tile editor so that we can experiment with rendering tiles! have a look:
javascript tairu import { Tilemap } from "tairu/tilemap.js"; import { TileEditor } from "tairu/editor.js";
export const tilemapSquare = Tilemap.parse(” x”, [ ” “, ” xxx “, ” xxx “, ” xxx “, ” “, ]);
new TileEditor({ tilemap: tilemapSquare, tileSize: 40, });
output tairu
now, also note that the border around this particular tile is only drawn on its northern edge - therefore we can infer that borders should only be drawn on edges for whom
shouldConnect(thisTile, adjacentTile)
isfalse
(nottrue
!). a tile generally has four edges - east, south, west, north - so we need to perform this check for all of them, and draw our border accordingly.to do that, I’m gonna override the tile editor’s
drawTilemap
function - as this is where the actual tilemap rendering happens!javascript tairu import { TileEditor } from "tairu/editor.js";
export class TileEditorWithBorders extends TileEditor { constructor({ borderWidth, …options }) { super(options);
this.borderWidth = borderWidth; this.colorScheme.borderColor = “#000000”; }
drawTilemap() { // Let the base class render out the infill, we’ll just handle the borders. super.drawTilemap();
this.ctx.fillStyle = this.colorScheme.borderColor;
for (let y = 0; y < this.tilemap.height; ++y) { for (let x = 0; x < this.tilemap.width; ++x) { let tile = this.tilemap.at(x, y); // We only want to draw non-empty tiles, so skip tile 0. if (tile == 0) { continue; }
// Check which of this tile’s neighbors should not connect to it. let disjointWithEast = !shouldConnect(tile, this.tilemap.at(x + 1, y)); let disjointWithSouth = !shouldConnect(tile, this.tilemap.at(x, y + 1)); let disjointWithWest = !shouldConnect(tile, this.tilemap.at(x - 1, y)); let disjointWithNorth = !shouldConnect(tile, this.tilemap.at(x, y - 1));
let { borderWidth, tileSize } = this; let tx = x * tileSize; let ty = y * tileSize;
// For each disjoint neighbor, we want to draw a border between us and them. if (disjointWithEast) { this.ctx.fillRect(tx + tileSize - borderWidth, ty, borderWidth, tileSize); } if (disjointWithSouth) { this.ctx.fillRect(tx, ty + tileSize - borderWidth, tileSize, borderWidth); } if (disjointWithWest) { this.ctx.fillRect(tx, ty, borderWidth, tileSize); } if (disjointWithNorth) { this.ctx.fillRect(tx, ty, tileSize, borderWidth); } } } } }
and here’s the result:
javascript tairu new TileEditorWithBorders({ tilemap: tilemapSquare, tileSize: 40, borderWidth: 4, });
output tairu
we can split this tileset up into 16 individual tiles, each one 8 × 8 pixels; people choose various resolutions, I chose a fairly low one to hide my lack of artistic skill.
<div class=”horizontal-tile-strip”> <span class=”metal x-0 y-0”></span> <span class=”metal x-1 y-0”></span> <span class=”metal x-2 y-0”></span> <span class=”metal x-3 y-0”></span> <span class=”metal x-0 y-1”></span> <span class=”metal x-1 y-1”></span> <span class=”metal x-2 y-1”></span> <span class=”metal x-3 y-1”></span> <span class=”metal x-0 y-2”></span> <span class=”metal x-1 y-2”></span> <span class=”metal x-2 y-2”></span> <span class=”metal x-3 y-2”></span> <span class=”metal x-0 y-3”></span> <span class=”metal x-1 y-3”></span> <span class=”metal x-2 y-3”></span> <span class=”metal x-3 y-3”></span> </div>
the keen eyed among you have probably noticed that this is very similar to the case we had before with drawing procedural borders - except that instead of determining which borders to draw based on a tile’s neighbors, this time we’ll determine which whole tile to draw based on its neighbors!
<div class=”horizontal-tile-strip”> <span class=”metal x-0 y-0”><span class=”east”>E</span><span class=”south”>S</span></span> <span class=”metal x-1 y-0”><span class=”east”>E</span><span class=”south”>S</span><span class=”west”>W</span></span> <span class=”metal x-2 y-0”><span class=”south”>S</span><span class=”west”>W</span></span> <span class=”metal x-3 y-0”><span class=”south”>S</span></span> <span class=”metal x-0 y-1”><span class=”east”>E</span><span class=”south”>S</span><span class=”north”>N</span></span> <span class=”metal x-1 y-1”><span class=”east”>E</span><span class=”south”>S</span><span class=”west”>W</span><span class=”north”>N</span></span> <span class=”metal x-2 y-1”><span class=”south”>S</span><span class=”west”>W</span><span class=”north”>N</span></span> <span class=”metal x-3 y-1”><span class=”south”>S</span><span class=”north”>N</span></span> <span class=”metal x-0 y-2”><span class=”east”>E</span><span class=”north”>N</span></span> <span class=”metal x-1 y-2”><span class=”east”>E</span><span class=”west”>W</span><span class=”north”>N</span></span> <span class=”metal x-2 y-2”><span class=”west”>W</span><span class=”north”>N</span></span> <span class=”metal x-3 y-2”><span class=”north”>N</span></span> <span class=”metal x-0 y-3”><span class=”east”>E</span></span> <span class=”metal x-1 y-3”><span class=”east”>E</span><span class=”west”>W</span></span> <span class=”metal x-2 y-3”><span class=”west”>W</span></span> <span class=”metal x-3 y-3”></span> </div>
now the clever part of bitwise autotiling is that we can use this packed integer as an array index - therefore selecting which tile to draw can be determined using just a single lookup table! neat, huh?
that means we’ll need to arrange our tiles like so, where the leftmost tile is at index 0 (
0b0000
) and the rightmost tile is at index 15 (0b1111
):<div class=”horizontal-tile-strip”> <span class=”metal x-3 y-3”></span> <span class=”metal x-0 y-3”><span class=”east”>E</span></span> <span class=”metal x-3 y-0”><span class=”south”>S</span></span> <span class=”metal x-0 y-0”><span class=”east”>E</span><span class=”south”>S</span></span> <span class=”metal x-2 y-3”><span class=”west”>W</span></span> <span class=”metal x-1 y-3”><span class=”east”>E</span><span class=”west”>W</span></span> <span class=”metal x-2 y-0”><span class=”south”>S</span><span class=”west”>W</span></span> <span class=”metal x-1 y-0”><span class=”east”>E</span><span class=”south”>S</span><span class=”west”>W</span></span> <span class=”metal x-3 y-2”><span class=”north”>N</span></span> <span class=”metal x-0 y-2”><span class=”east”>E</span><span class=”north”>N</span></span> <span class=”metal x-3 y-1”><span class=”south”>S</span><span class=”north”>N</span></span> <span class=”metal x-0 y-1”><span class=”east”>E</span><span class=”south”>S</span><span class=”north”>N</span></span> <span class=”metal x-2 y-2”><span class=”west”>W</span><span class=”north”>N</span></span> <span class=”metal x-1 y-2”><span class=”east”>E</span><span class=”west”>W</span><span class=”north”>N</span></span> <span class=”metal x-2 y-1”><span class=”south”>S</span><span class=”west”>W</span><span class=”north”>N</span></span> <span class=”metal x-1 y-1”><span class=”east”>E</span><span class=”south”>S</span><span class=”west”>W</span><span class=”north”>N</span></span> </div>
…but anyways, here’s the basic bitwise magic function:
javascript tairu export function tileIndexInBitwiseTileset(tilemap, x, y) { let tile = tilemap.at(x, y);
let tileIndex = 0; tileIndex |= shouldConnect(tile, tilemap.at(x + 1, y)) ? E : 0; tileIndex |= shouldConnect(tile, tilemap.at(x, y + 1)) ? S : 0; tileIndex |= shouldConnect(tile, tilemap.at(x - 1, y)) ? W : 0; tileIndex |= shouldConnect(tile, tilemap.at(x, y - 1)) ? N : 0;
return tileIndex; }
we’ll define our tilesets by their texture, tile size, and a tile indexing function. so let’s create an object that will hold our tileset data:
javascript tairu // You'll probably want to host the assets on your own website rather than // hotlinking to others. It helps longevity! const tilesetImage = new Image(); tilesetImage.src = "/static/pic/01HPMMR6DGKYTPZ9CK0WQWKNX5-tilemap-heavy-metal-bitwise-16+pixel+width640.png";
export const heavyMetalTileset = { image: tilesetImage, tileSize: 8, tileIndex: tileIndexInBitwiseTileset, };
with all that, we should now be able to write a tile renderer which can handle textures! so let’s try it:
javascript tairu import { TileEditor } from "tairu/editor.js";
export class TilesetTileEditor extends TileEditor { constructor({ tilesets, …options }) { super(options); this.tilesets = tilesets;
// The image may not be loaded once the editor is first drawn, so we need to request a // redraw for each image that gets loaded in. for (let tileset of this.tilesets) { tileset.image.addEventListener(”load”, () => this.draw()); } }
drawTilemap() { // We’re dealing with pixel tiles so we want our images to be pixelated, // not interpolated. this.ctx.imageSmoothingEnabled = false;
for (let y = 0; y < this.tilemap.height; ++y) { for (let x = 0; x < this.tilemap.width; ++x) { let tile = this.tilemap.at(x, y); if (tile == 0) { continue; }
// Subtract one from the tile because tile 0 is always empty. // Having to specify a null entry at array index 0 would be pretty annoying. let tileset = this.tilesets[tile - 1]; if (tileset != null) { let { tileSize } = this; let tileIndex = tileset.tileIndex(this.tilemap, x, y); this.ctx.drawImage( tileset.image, tileIndex * tileset.tileSize, 0, tileset.tileSize, tileset.tileSize, x * tileSize, y * tileSize, tileSize, tileSize, ); } } } } }
it works! buuuut if you play around with it you’ll quickly start noticing some problems:
javascript tairu import { Tilemap } from "tairu/tilemap.js";
export const tilemapEdgeCase = Tilemap.parse(” x”, [ ” “, ” xxx “, ” x x “, ” xxx “, ” “, ]); new TilesetTileEditor({ tilemap: tilemapEdgeCase, tileSize: 40, tilesets: [heavyMetalTileset], });
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>
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.
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; }
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.
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; }
for my own (and your) convenience, here’s a complete list of all the possible combinations in order.
javascript ordinal-directions function toString(bitset) { if (bitset == 0) return "0";
let directions = []; if (isSet(bitset, E)) directions.push(”E”); if (isSet(bitset, SE)) directions.push(”SE”); if (isSet(bitset, S)) directions.push(”S”); if (isSet(bitset, SW)) directions.push(”SW”); if (isSet(bitset, W)) directions.push(”W”); if (isSet(bitset, NW)) directions.push(”NW”); if (isSet(bitset, N)) directions.push(”N”); if (isSet(bitset, NE)) directions.push(”NE”); return directions.join(” | “); }
for (let x in xToConnectionBitSet) { console.log(
${x} => ${toString(xToConnectionBitSet[x])}
); }
with the capability to render with 47-tile tilesets, our examples suddenly look a whole lot better!
<canvas is=”tairu-editor” data-tilemap-id=”bitwiseAutotiling47” data-tile-size=”40” > Your browser does not support <canvas>. <img class=”resource” src=”/static/pic/01HPW47SHMSVAH7C0JR9HWXWCM-tilemap-heavy-metal-bitwise-48+pixel+width752.png” data-tairu-tileset-47=”1”> </canvas>
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.