Skip to content

A fast 2D and 3D game engine — TypeScript SDK, C++/WebAssembly core, visual editor. Ship one project to web, desktop, WeChat MiniGames, playable ads, and native Android / iOS.

8.3 KB
Raw Blame
// SPDX-License-Identifier: Apache-2.0
// SPDX-FileCopyrightText: Copyright (c) 2024-present ESEngine Team
/**
 * @file    autotile.ts
 * @brief   Terrain autotiling: pick a tile from a `.estileset` terrain set by how a cell
 *          peers with its same-terrain neighbours. Pure (no engine deps) so the painter
 *          and tests share one resolver.
 *
 * Two modes (see {@link TerrainMode}): `edge` matches the 4 sides (N/E/S/W → 16 tiles),
 * `corner` is the 8-bit "corners and sides" blob — a corner peering bit only counts when
 * both of its adjacent sides also peer (the classic 47-tile reduction). When no tile has
 * the exact mask, the nearest by Hamming distance is used, so a partial set still paints.
 */

import type { TilesetAsset, TerrainMode } from './tilesetAsset';

// Peering-direction bits. Sides are the low nibble so `& SIDE_BITS` keeps edge masks.
export const TB_N = 1;
export const TB_E = 2;
export const TB_S = 4;
export const TB_W = 8;
export const TB_NE = 16;
export const TB_SE = 32;
export const TB_SW = 64;
export const TB_NW = 128;

const SIDE_BITS = TB_N | TB_E | TB_S | TB_W;

/**
 * The 8 neighbour offsets (tile grid, y down) paired with their peering bit. Index order
 * is the contract for {@link resolveAutotile}'s `neighbors` argument.
 */
export const TERRAIN_NEIGHBORS: ReadonlyArray<{ dx: number; dy: number; bit: number }> = [
    { dx: 0, dy: -1, bit: TB_N },
    { dx: 1, dy: -1, bit: TB_NE },
    { dx: 1, dy: 0, bit: TB_E },
    { dx: 1, dy: 1, bit: TB_SE },
    { dx: 0, dy: 1, bit: TB_S },
    { dx: -1, dy: 1, bit: TB_SW },
    { dx: -1, dy: 0, bit: TB_W },
    { dx: -1, dy: -1, bit: TB_NW },
];

/** Drop corner bits whose two adjacent sides don't both peer (the blob rule). */
export function normalizeCornerMask(mask: number): number {
    let m = mask;
    if ((m & TB_N) === 0 || (m & TB_E) === 0) m &= ~TB_NE;
    if ((m & TB_S) === 0 || (m & TB_E) === 0) m &= ~TB_SE;
    if ((m & TB_S) === 0 || (m & TB_W) === 0) m &= ~TB_SW;
    if ((m & TB_N) === 0 || (m & TB_W) === 0) m &= ~TB_NW;
    return m;
}

/** Canonicalize a raw peering mask for a mode (edge → sides only, corner → blob rule). */
export function canonicalMask(mode: TerrainMode, mask: number): number {
    return mode === 'corner' ? normalizeCornerMask(mask) : mask & SIDE_BITS;
}

/** A terrain set's resolver table: canonical peering mask → the tile id to draw. */
export interface TerrainIndex {
    mode: TerrainMode;
    byMask: Map<number, number>;
}

/** Built lookup over a tileset's terrains: per-set resolver + reverse tile→set. */
export interface TerrainIndices {
    /** setIndex → its {@link TerrainIndex}. */
    sets: Map<number, TerrainIndex>;
    /** tile id → the terrain set it belongs to (for reverse-deriving a painted cell's terrain). */
    tileTerrain: Map<number, number>;
}

/** Build the terrain resolver tables for a tileset (first tile wins a duplicated mask). */
export function buildTerrainIndices(asset: TilesetAsset): TerrainIndices {
    const sets = new Map<number, TerrainIndex>();
    const tileTerrain = new Map<number, number>();
    const terrains = asset.terrains ?? [];
    for (const key of Object.keys(asset.tiles)) {
        const id = Number(key);
        const t = asset.tiles[id].terrain;
        if (!t) continue;
        const mode: TerrainMode = terrains[t.set]?.mode ?? 'edge';
        // Peering (edge/corner) only — wang sets carry per-corner colors, not a mask, and
        // resolve through buildWangIndices; skip them (and any tile missing a mask).
        if (mode === 'wang' || t.mask === undefined) continue;
        tileTerrain.set(id, t.set);
        let index = sets.get(t.set);
        if (!index) {
            index = { mode, byMask: new Map() };
            sets.set(t.set, index);
        }
        const mask = canonicalMask(mode, t.mask);
        if (!index.byMask.has(mask)) index.byMask.set(mask, id);
    }
    return { sets, tileTerrain };
}

function popcount(n: number): number {
    let c = 0;
    for (let v = n; v !== 0; v &= v - 1) c++;
    return c;
}

/**
 * Pick the tile for a cell given which of its 8 neighbours are the same terrain.
 * `neighbors` is indexed by {@link TERRAIN_NEIGHBORS} order. Returns 0 if the set is empty.
 */
export function resolveAutotile(index: TerrainIndex, neighbors: readonly boolean[]): number {
    return resolveAutotileMatch(index, neighbors).tileId;
}

/** Keep the requested combination visible to authoring diagnostics, including fallback. */
export function resolveAutotileMatch(index: TerrainIndex, neighbors: readonly boolean[]): { tileId: number; exact: boolean; mask: number } {
    let mask = 0;
    for (let i = 0; i < TERRAIN_NEIGHBORS.length; i++) {
        if (neighbors[i]) mask |= TERRAIN_NEIGHBORS[i].bit;
    }
    mask = canonicalMask(index.mode, mask);
    const exact = index.byMask.get(mask);
    if (exact !== undefined) return { tileId: exact, exact: true, mask };
    let best = 0;
    let bestDist = Infinity;
    for (const [m, id] of index.byMask) {
        const d = popcount(m ^ mask);
        if (d < bestDist) {
            bestDist = d;
            best = id;
        }
    }
    return { tileId: best, exact: false, mask };
}

// ── Corner (Wang) terrain ────────────────────────────────────────────────────
// The modern model: a tile carries a COLOR at each of its 4 corners. A cell is resolved
// from the 4 colors on its corners (a half-cell "corner grid"), so one set blends many
// terrains. Corner order everywhere is [top-left, top-right, bottom-right, bottom-left].

/** Pack 4 corner color indices into one lookup key (8 bits each; up to 255 colors). */
export function packCorners(tl: number, tr: number, br: number, bl: number): number {
    // The low 3 bytes stay in int32 range; ADD the top byte (a plain multiply) so the OR's
    // int32 coercion can't wrap the key negative.
    return ((tl & 0xff) | ((tr & 0xff) << 8) | ((br & 0xff) << 16)) + ((bl & 0xff) * 0x1000000);
}

/** A wang set's resolver: packed 4-corner key → the tile id to draw. */
export interface WangIndex {
    byKey: Map<number, number>;
}

/** Built lookup over a tileset's wang terrains: per-set resolver + reverse tile→set. */
export interface WangIndices {
    sets: Map<number, WangIndex>;
    tileTerrain: Map<number, number>;
}

/** Build the corner-match resolver tables for a tileset's `wang` sets (first tile wins a dup). */
export function buildWangIndices(asset: TilesetAsset): WangIndices {
    const sets = new Map<number, WangIndex>();
    const tileTerrain = new Map<number, number>();
    const terrains = asset.terrains ?? [];
    for (const key of Object.keys(asset.tiles)) {
        const id = Number(key);
        const t = asset.tiles[id].terrain;
        if (!t || !t.corners || (terrains[t.set]?.mode ?? 'edge') !== 'wang') continue;
        tileTerrain.set(id, t.set);
        let index = sets.get(t.set);
        if (!index) { index = { byKey: new Map() }; sets.set(t.set, index); }
        const k = packCorners(t.corners[0], t.corners[1], t.corners[2], t.corners[3]);
        if (!index.byKey.has(k)) index.byKey.set(k, id);
    }
    return { sets, tileTerrain };
}

/** How many of the 4 corners differ between two packed keys. */
function cornerDist(a: number, b: number): number {
    let d = 0;
    for (let s = 0; s < 32; s += 8) {
        if (((a >>> s) & 0xff) !== ((b >>> s) & 0xff)) d++;
    }
    return d;
}

/**
 * Pick the tile whose 4 corner colors match `corners` ([TL, TR, BR, BL]); when no tile has
 * the exact combination, the nearest by corner-mismatch count is used, so a partial wang
 * set still paints. Returns 0 if the set is empty.
 */
export function resolveWang(index: WangIndex, corners: readonly number[]): number {
    return resolveWangMatch(index, corners).tileId;
}

export function resolveWangMatch(index: WangIndex, corners: readonly number[]): { tileId: number; exact: boolean; key: number } {
    const key = packCorners(corners[0] ?? 0, corners[1] ?? 0, corners[2] ?? 0, corners[3] ?? 0);
    const exact = index.byKey.get(key);
    if (exact !== undefined) return { tileId: exact, exact: true, key };
    let best = 0;
    let bestDist = Infinity;
    for (const [k, id] of index.byKey) {
        const d = cornerDist(k, key);
        if (d < bestDist) { bestDist = d; best = id; }
    }
    return { tileId: best, exact: false, key };
}