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:
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, });
Tilemap
is a class wrapping a flatUint8Array
with awidth
and aheight
, so that we can index it using (x, y) coordinates.console.log(tilemapSquare.at(0, 0)); console.log(tilemapSquare.at(3, 1));
0 1
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!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:
new TileEditorWithBorders({ tilemap: tilemapSquare, tileSize: 40, borderWidth: 4, });
…but anyways, here’s the basic bitwise magic function:
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:
// You'll probably want to host the assets on your own website rather than // hotlinking to others. It helps longevity! let tilesetImage = new Image(); tilesetImage.src = "https://liquidex.house/static/pic/01HPMMR6DGKYTPZ9CK0WQWKNX5-tilemap-heavy-metal-bitwise-16+pixel+width640.png?v=b3-a250c9e5"; 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:
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:
import { Tilemap } from "tairu/tilemap.js"; export const tilemapEdgeCase = Tilemap.parse(" x", [ " ", " xxx ", " x x ", " xxx ", " ", ]); new TilesetTileEditor({ tilemap: tilemapEdgeCase, tileSize: 40, tilesets: [heavyMetalTileset], });
thing is, it was never good in the first place
to represent the corners, we’ll turn our four cardinal directions…
- E
- S
- W
- N
into eight ordinal directions:
- E
- SE
- S
- SW
- W
- NW
- N
- NE
at this point with the four extra corners 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! let’s stick with the 16 tile version for a moment. if we arrange the tiles in a diagnonal cross like this, notice how the tile in the center would have the bits
SE | SW | NW | NE
set, which upon first glance would suggest us needing a different tile - but it looks correct!import { Tilemap } from "tairu/tilemap.js"; new TilesetTileEditor({ tilemap: Tilemap.parse(" x", [ " ", " x x ", " x ", " x x ", " ", ]), tileSize: 40, tilesets: [heavyMetalTileset], });
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 redefining our bits to be ordinal directions instead. I still want to keep the nice orderliness that comes with arranging the bits clockwise starting from east, so if we want that we can’t just extend the indices with an extra four bits at the top.
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;
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.
// t is an existing 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:
export function ordinalDirections() { let unique = new Set(); for (let i = 0; i <= 0b1111_1111; ++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?
I don’t want to write the lookup table by hand, so let’s generate it!
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
]: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.
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])}`); }
0 => 0 1 => E 2 => S 3 => E | S 4 => E | SE | S 5 => W 6 => E | W 7 => S | W 8 => E | S | W 9 => E | SE | S | W 10 => S | SW | W 11 => E | S | SW | W 12 => E | SE | S | SW | W 13 => N 14 => E | N 15 => S | N 16 => E | S | N 17 => E | SE | S | N 18 => W | N 19 => E | W | N 20 => S | W | N 21 => E | S | W | N 22 => E | SE | S | W | N 23 => S | SW | W | N 24 => E | S | SW | W | N 25 => E | SE | S | SW | W | N 26 => W | NW | N 27 => E | W | NW | N 28 => S | W | NW | N 29 => E | S | W | NW | N 30 => E | SE | S | W | NW | N 31 => S | SW | W | NW | N 32 => E | S | SW | W | NW | N 33 => E | SE | S | SW | W | NW | N 34 => E | N | NE 35 => E | S | N | NE 36 => E | SE | S | N | NE 37 => E | W | N | NE 38 => E | S | W | N | NE 39 => E | SE | S | W | N | NE 40 => E | S | SW | W | N | NE 41 => E | SE | S | SW | W | N | NE 42 => E | W | NW | N | NE 43 => E | S | W | NW | N | NE 44 => E | SE | S | W | NW | N | NE 45 => E | S | SW | W | NW | N | NE 46 => E | SE | S | SW | W | NW | N | NE
since we already prepared the bulk of the framework before, it should be as simple as writing a new
tileIndex
function:export function tileIndexInBitwiseTileset47(tilemap, x, y) { let tile = tilemap.at(x, y); let tileBitset = 0; tileBitset |= shouldConnect(tile, tilemap.at(x + 1, y)) ? E : 0; tileBitset |= shouldConnect(tile, tilemap.at(x + 1, y + 1)) ? SE : 0; tileBitset |= shouldConnect(tile, tilemap.at(x, y + 1)) ? S : 0; tileBitset |= shouldConnect(tile, tilemap.at(x - 1, y + 1)) ? SW : 0; tileBitset |= shouldConnect(tile, tilemap.at(x - 1, y)) ? W : 0; tileBitset |= shouldConnect(tile, tilemap.at(x - 1, y - 1)) ? NW : 0; tileBitset |= shouldConnect(tile, tilemap.at(x, y - 1)) ? N : 0; tileBitset |= shouldConnect(tile, tilemap.at(x + 1, y - 1)) ? NE : 0; return connectionBitSetToX[removeRedundancies(tileBitset)]; }
now we can write a new tileset descriptor that uses this indexing function and the larger tile strip:
// Once again, use your own link here! let tilesetImage = new Image(); tilesetImage.src = "https://liquidex.house/static/pic/01HPW47SHMSVAH7C0JR9HWXWCM-tilemap-heavy-metal-bitwise-48+pixel+width752.png?v=b3-df25f372"; export const heavyMetalTileset47 = { image: tilesetImage, tileSize: 8, tileIndex: tileIndexInBitwiseTileset47, };