Rasterloom · auto-tiling

Why an auto-tiling terrain set has exactly 47 tiles

Not 16, not 256. Forty-seven, and the number falls out of the geometry rather than out of anyone's patience.

The naive count

A tile in a blob auto-tiler looks at its eight neighbours and asks, for each one, "same terrain or not?". Eight yes/no answers is one byte, so there are 2⁸ = 256 possible neighbourhoods. Draw one tile per neighbourhood and you are done - and also finished as an artist, because 256 hand-drawn variants per terrain is not a set anyone ships.

The good news is that most of those 256 are the same picture.

The reduction

Take the top-left corner of a tile. Which neighbours can possibly change what it looks like? Only three: north, west, and north-west. The east and south neighbours are on the other side of the tile; they cannot reach it.

Now the key observation. If north is empty, the corner is an outside corner and the north-west neighbour changes nothing - there is already a gap there. The same if west is empty. The diagonal only matters when both of its adjacent edges are filled, because that is the only case where the corner would otherwise be solid and the diagonal can punch a notch into it.

So each corner has three distinguishable states, not eight:

1. both edges empty — an outside corner,
2. one edge filled — an edge running past,
3. both edges filled, diagonal empty — an inside corner.

Plus the fully filled case, which is what "both edges filled, diagonal filled" draws. Enumerate the four corners under that rule, throw away the neighbourhoods that produce an identical picture, and 256 collapses to 47. That is the whole derivation. The number is not a convention; it is a count of distinguishable drawings.

ignore = []
for mask in range(256):
    n, e, s, w  = bit(mask, N), bit(mask, E), bit(mask, S), bit(mask, W)
    nw, ne, se, sw = bit(mask, NW), bit(mask, NE), bit(mask, SE), bit(mask, SW)
    # A diagonal that is not braced by both of its edges is invisible.
    if nw and not (n and w): mask &= ~NW
    if ne and not (n and e): mask &= ~NE
    if se and not (s and e): mask &= ~SE
    if sw and not (s and w): mask &= ~SW
    ignore.append(mask)

len(set(ignore))   # 47

Why this is the part worth buying

The forty-seven drawings are the easy half. The half that eats an afternoon is the lookup: given the eight-neighbour bitmask a game computes at runtime, which of the forty-seven tiles goes in that cell? That is a 256-entry table, and it is the same table for every terrain set on earth, and almost every tileset on the market makes the buyer write it.

Shipping the table with the art is not generosity, it is the difference between an asset that drops in and an asset that costs a day.

Why the seams line up

There is a second reason to generate the tiles rather than draw them. Every quarter of a tile touches exactly one lattice point - the place where four map cells meet - and the drawing inside that quarter is a pure function of those four cells. Two neighbouring tiles therefore compute their shared edge from the same four values, so the edge is identical on both sides by construction. Nothing has to be lined up by eye, and nothing drifts when a terrain is re-rendered at a different size.