Tilemaps and autotiling

Why you need this

Every technique in this cluster ends by writing tile ids into a 2D array, and most start by reading which tiles exist and how they may touch. That array, and the sheet the ids point into, is the tilemap. Autotiling turns a grid of "grass here, sand there" into the correct edge and corner art without anyone placing 47 kinds of shoreline by hand. Get the data format right once and every generator can share it.

The idea

Tile sheets and tile ids

A tile sheet is one image holding many small square tiles in a grid. The tile size is the side length of one tile in pixels, 16 or 32 in most purchased top-down sets. A sheet 256 pixels wide with 16-pixel tiles has 16 columns; if it is also 256 tall it holds $16 \times 16 = 256$ tiles.

A tile id is the index of one tile in the sheet, counting left to right, top to bottom, starting at 0. With $C$ columns in the sheet, tile id $i$ sits at column $i \bmod C$ and row $\lfloor i / C \rfloor$. For $C = 16$, tile 35 is at column $35 \bmod 16 = 3$, row $\lfloor 35 / 16 \rfloor = 2$. Its top-left pixel is at $(3 \times 16, 2 \times 16) = (48, 32)$.

A game with several sheets gives each sheet a first id so that ids stay unique. If the ground sheet starts at 1 and holds 256 tiles, the forest sheet starts at 257. Id 0 is conventionally "empty".

Tilemaps and layers

A tilemap is a 2D array of tile ids, $W$ wide and $H$ tall, stored flat so that cell $(x, y)$ is at index $y \cdot W + x$ (the same convention as Graphs and grids). Real maps have several arrays of the same size stacked as layers, drawn bottom to top.

Layer	Holds	Drawn
ground	grass, sand, water, dungeon floor	first
decor	flowers, rocks, barrels, rugs	on top of ground
walls	cliff faces, building walls, tree trunks	on top of decor, often on top of the player when behind them
collision	0 or 1, not drawn	never; the physics reads it

Layer order matters: a flower drawn under the grass is invisible. Collision is its own layer so a generator can mark "solid" without caring which tile made it solid.

Autotiling with a 4-bit mask

Suppose a region of grass sits on sand. The interior is plain grass, but every border cell needs a different tile: grass with a sand edge on the left, grass with sand edges on the top and left, and so on. Autotiling computes which one from the cell's neighbors.

For edges only, look at the four von Neumann neighbors (up, right, down, left) and ask "is that neighbor the same terrain as me?" Each answer is one bit:

Neighbor	Bit value
Up	1
Right	2
Down	4
Left	8

Add up the bits for neighbors that match. The sum, 0 to 15, is the bitmask, an index into a strip of 16 tiles laid out in that order. Mask 15 (all four match) is the interior tile, mask 0 is a lone island, and mask 3 (up and right match) shows sand along its bottom and left edges.

function edgeMask(same, x, y) {
  return (same(x, y - 1) ? 1 : 0)
       | (same(x + 1, y) ? 2 : 0)
       | (same(x, y + 1) ? 4 : 0)
       | (same(x - 1, y) ? 8 : 0);
}

The same function should treat out-of-bounds as "matches" if you want the map edge to look like the terrain continues, or "does not match" if you want a shoreline along the border.

The 47-tile blob

Edges alone leave a gap at inside corners: a grass cell with grass above and to the right but sand on the diagonal between them needs a small sand notch in its upper-right corner, and the 4-bit strip has no tile for that. The fix reads all eight Moore neighbors (see Graphs and grids) for 8 bits and 256 raw masks. Most are redundant, because a diagonal only matters when both edges beside it match; otherwise the edge art already covers the corner. Collapsing the redundant masks leaves 47 distinct tiles, which is how purchased "blob" autotile sheets are laid out. Compute the 8-bit mask, then look it up in a 256-entry table that maps each mask to one of the 47 tiles.

Edge signatures

Autotiling asks "does my neighbor match me?" A generator such as Wave Function Collapse needs the finer question "may tile $a$ sit directly left of tile $b$?" Answer it by labelling each of a tile's four sides with an edge signature, a short string describing what that side shows.

Tile	Top	Right	Bottom	Left
grass interior	grass	grass	grass	grass
grass, sand on right	grass	sand	grass	grass
grass, sand on right and bottom	grass	sand	sand	grass
sand interior	sand	sand	sand	sand

Two tiles may be horizontal neighbors when the left tile's right signature equals the right tile's left signature. In the table, "grass, sand on right" may sit left of "sand interior" (sand meets sand) but not left of "grass interior" (sand meets grass). An edge that runs grass on top to sand on the bottom must meet a neighbor whose edge runs the same way, so grass-sand and sand-grass are distinct signatures. This table is the data that Constraint satisfaction and Wave Function Collapse consume: each allowed pair is one constraint.

Palette variants

Purchased sets usually ship the same shapes in several colors: summer, autumn, and snow grass; stone and mossy dungeon. These palette variants share every edge signature and autotile mask, so a generator picks shapes once and chooses a variant afterwards, as a per-region id offset or a "palette" field in the manifest. The regime stage uses this to shift a region from green to brown without regenerating anything.

Worked example

A 4 by 3 patch where G is grass and s is sand, with out-of-bounds counted as "matches":

G G s s
G G G s
s G G G

Edge masks for the grass cells, using Up = 1, Right = 2, Down = 4, Left = 8:

Cell	Up	Right	Down	Left	Mask
(0, 0)	edge, 1	G, 2	G, 4	edge, 8	15
(1, 0)	edge, 1	s, 0	G, 4	G, 8	13
(0, 1)	G, 1	G, 2	s, 0	edge, 8	11
(1, 1)	G, 1	G, 2	G, 4	G, 8	15
(2, 1)	s, 0	s, 0	G, 4	G, 8	12
(1, 2)	G, 1	G, 2	edge, 4	s, 0	7
(2, 2)	G, 1	G, 2	edge, 4	G, 8	15
(3, 2)	s, 0	edge, 2	edge, 4	G, 8	14

Cell $(1, 1)$ is interior grass even though it is surrounded on the diagonal by sand at $(2, 0)$ and $(0, 2)$, which is exactly the gap the 47-tile blob closes. Cell $(2, 1)$ gets mask 12, the tile with sand showing along its top and right edges.

Minimal export shape

Everything above fits in one JSON object. This is the smallest shape a game loader needs.

{
  "width": 4,
  "height": 3,
  "tileSize": 16,
  "tilesets": [
    { "name": "ground", "image": "ground.png", "firstId": 1, "columns": 16 },
    { "name": "forest", "image": "forest.png", "firstId": 257, "columns": 16 }
  ],
  "layers": [
    { "name": "ground", "data": [16, 14, 40, 40, 12, 16, 13, 40, 40, 8, 16, 15] },
    { "name": "decor", "data": [0, 0, 0, 0, 0, 261, 0, 0, 0, 0, 0, 0] },
    { "name": "collision", "data": [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] }
  ]
}

Each data array has exactly width * height entries in $y \cdot W + x$ order. The ground ids are the worked example above, firstId 1 plus each grass cell's mask, so $(0, 0)$ with mask 15 is id 16 and the sand cells all use id 40. firstId tells the loader which sheet an id belongs to: 261 is in forest, at local index $261 - 257 = 4$. Add seed and a parameter file version at the top level and the manifest is reproducible, which is what the export stage on the hub page asks for.

In a map generator

• Catalog: slice each purchased sheet into ids, tag every id (terrain, decor, wall, walkable), and record its four edge signatures. Once per asset library, not once per map.
• Layout: works in coarse cells, one per chunk, and hands down a biome tag that selects which ids the fill stage may use.
• Fill: writes terrain tags into a grid, then an autotile pass converts tags into ids using the masks above. Wave Function Collapse skips that pass because it places final ids directly, using edge signatures as constraints.
• Regime over time: swaps palette variants and decor ids in place. The shapes do not change, so nothing is re-solved.
• Export: the JSON above, one object per chunk or one for the whole map.

Side-scroller platform tiles use the same machinery with a twist: a platform is a run of tiles in one row, so only the Left and Right bits matter (mask 0 lone block, 2 left cap, 8 right cap, 10 middle), and the backdrops are parallax images rather than tiles.

Common mistakes

• Off-by-one on firstId. Every tile in the second sheet renders as its neighbor in the strip. Symptom: shorelines come out rotated one step around the whole map.
• Wrong bit order. Your mask says Up = 1 but the purchased strip assumes Up = 8. Symptom: edge art appears on the opposite side from the sand.
• Autotiling against the wrong layer. Reading the decor layer to compute grass edges puts shoreline in the middle of a meadow wherever a flower sits.
• Collision derived from art. Marking a cell solid because the tile "looks like" a wall breaks the moment a palette variant is swapped in. Collision is its own layer, written by the generator.
• Row-major here, column-major there. The loader reads $x \cdot H + y$, the generator wrote $y \cdot W + x$. Symptom: diagonal shreds.
• Interior is mask 15, not mask 0. Symptom: every interior cell shows a lone island tile with edges on all four sides.

Cost

Storing a map takes one id per cell per layer, $O(L \cdot W \cdot H)$ for $L$ layers on a $W \times H$ grid; a $256 \times 256$ map with three layers is about 197 thousand ids, under 400 kilobytes as 16-bit integers. Autotiling is one pass reading 4 or 8 neighbors per cell, $O(W \cdot H)$ time, and the 47-tile lookup table is 256 bytes. None of this hurts until the map is thousands of cells per side, at which point you generate chunks on demand instead, as Layered generation describes.

Going further

• Wave Function Collapse, which consumes the edge signature table directly.
• Cellular automata, whose wall-or-floor output is the simplest possible tag grid for autotiling.
• The Tiled map editor's JSON format, a widely used superset of the export shape above.
• Wang tiles, the mathematical version of edge signatures: square tiles with colored edges that must match.
• Dual-grid autotiling, which places tiles at the offset lattice between cells and needs only 16 tiles for full corner coverage.