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.

21.9 KB
Raw Blame
// SPDX-License-Identifier: Apache-2.0
// SPDX-FileCopyrightText: Copyright (c) 2024-present ESEngine Team
/**
 * @file    chunks.ts
 * @brief   The one owner of procedural chunks: what is made round the streaming sources, in what order, within the frame's budget,
 *          and when it is let go.
 *
 * @details A cooked world's cells are scenes, brought in by the WorldStreamer. What a game makes as it runs (the ground's collision
 *          round what moves, plants round the eye, and later what stands in a biome) is chunks of layers, and this is the single
 *          author of their lifetime, as the streamer is of cells. A layer says how it is cut, how far round its sources it is wanted
 *          and how one chunk is made, published and released; the layer never decides on its own that a chunk exists.
 *
 *            - Every frame the chunks within a layer's load radius of a source are wanted, nearest first across every layer; the
 *              ones a source stands in are made at once, the rest while the frame's budget (Bakes) lasts.
 *            - A chunk past every source's unload radius is released: whatever it published (meshes, colliders, entities) goes with
 *              it, so a source walking for ever holds a bounded number of chunks.
 *            - A layer's `generation` names its inputs. When it changes every chunk is made again; until a chunk's new version is
 *              published its old one stays, so nothing standing on it falls, and an answer that arrives for an older generation (a
 *              provider still working on the planet just left) is thrown away, never published.
 *            - A chunk whose making throws is failed until the generation changes, and says why.
 */
import { createAbort, type AbortHandle } from '../util/abort';
import type { App } from '../app/app';
import { defineResource } from '../ecs/resource';
import { defineSystem, Schedule } from '../ecs/system';
import { Camera, Transform, type CameraData, type TransformData } from '../ecs/component';
import { EditorView, editorViewpoint } from '../camera/EditorView';
import { WorldStreamingSource, type WorldStreamingSourceData } from './components';
import { bakesOf } from '../runtime/bakes';
import { log } from '../util/logger';

/** A place a layer is wanted round, on the layer's plane (the ground by default), in world units. */
export interface ChunkSource { x: number; z: number; /** Its height, where a layer is not on a plane (a planet's collision reads the whole position). */ y?: number }

/** One kind of chunk: how it is cut, where it is wanted and how it is made. */
export interface ChunkLayer<T> {
    /** What the layer is, for the progress shown while its chunks are made. */
    readonly label: string;
    /**
     * The world plane the chunk grid lies on. `'xz'` (the default) is the ground of a 3D world and chunks are cut along world x and z. `'xy'` is a 2D
     * world, whose ground is the screen plane: chunks are cut along world x and y, and every place below called z is world y. It decides how the world's own
     * streaming sources (and the camera) are read; a layer's own `sources()` already answer in the layer's plane.
     */
    plane?: 'xz' | 'xy';
    /** The world position of chunk (0, 0)'s corner, and the side of a chunk along the plane's two axes (x, then z, or y on 'xy'). */
    originX: number;
    originZ: number;
    sizeX: number;
    sizeZ: number;
    /** The chunks there are, [x0, z0, x1, z1) in chunk coordinates; null for no end. */
    extent: readonly [number, number, number, number] | null;
    /** Chunks within this of a source are wanted; one is let go once past `unloadRadius` of every source. */
    loadRadius: number;
    unloadRadius: number;
    /** Names the layer's inputs: when it changes every chunk is made again, and answers for an older one are thrown away. */
    generation: number | string;
    /** Where the layer is wanted round; absent, the world's streaming sources (or the eye, where there are none). */
    sources?(): Iterable<ChunkSource>;
    /** True when `make` answers later, off the main thread: the layer is then asked for every chunk it wants, at once, and is not held to the frame's time. */
    async?: boolean;
    /** Makes a chunk. Null is "not yet" (what it stands on is not ready) and is asked again later; a promise answers later. */
    make(cx: number, cz: number, signal: AbortSignal): T | null | Promise<T | null>;
    /** Puts a made chunk into the world. An older version of it, if one was published, has just been released. */
    publish(cx: number, cz: number, value: T): void;
    /** Takes a published chunk out of the world: everything it put there. */
    release(cx: number, cz: number, value: T): void;
}

/** Where one chunk stands: being made, published (for the layer's generation now, or an older one), or failed. */
export type ChunkState = 'making' | 'ready' | 'stale' | 'failed';

/** A layer's chunks, counted. */
export interface ChunkLayerStatus {
    /** Published for the generation now. */
    ready: number;
    /** Published for an older generation, waiting to be made again. */
    stale: number;
    /** Wanted and not published yet (including those being made). */
    pending: number;
    making: number;
    failed: number;
    /** Why the first failed chunk failed. */
    reason?: string;
}

interface Chunk<T> {
    cx: number;
    cz: number;
    /** What is published now, and for which generation. */
    value: T | null;
    publishedFor: number | string | null;
    /** Being made: for which generation, and how to stop it. */
    making: { generation: number | string; abort: AbortHandle } | null;
    failedFor: number | string | null;
    reason?: string;
}

interface Layer<T> {
    def: ChunkLayer<T>;
    chunks: Map<string, Chunk<T>>;
    /** The chunks within the load radius of a source, as of the last frame. */
    wanted: Set<string>;
    /** The last walk of the cells round the sources, kept while they stand where they stood: see {@link WALK_SLACK}. */
    walk?: { from: string; at: readonly ChunkSource[]; near: Map<string, number>; keep: Set<string>; settledFor?: number | string };
}

/**
 * How far a source may move, as a share of a cell, before the cells round it are walked again. The walk is every cell within the
 * larger radius, each with a key and a distance, and then every one of them asked whether it is made: 9 ms a frame for six fields
 * of 8 m cells reaching 260 m, with the camera standing still and nothing left to make. A source that has not left its cell and
 * has moved less than this is where it was; and a layer with every chunk it wants made, for the generation it is at, is not asked.
 */
const WALK_SLACK = 1 / 16;

/** At most this many chunks of a layer are answered later at once. */
const MAX_IN_FLIGHT = 16;

const keyOf = (cx: number, cz: number): string => `${cx},${cz}`;

/** What a published chunk's generation is set to when it is made out of date by hand: no layer's generation. */
const OUTDATED = Symbol('outdated') as unknown as string;

/** The procedural chunks of every layer. Read {@link ProceduralChunks.status} for where they stand. */
export class ProceduralChunks {
    private readonly layers_ = new Map<string, Layer<unknown>>();
    /** @internal Set by the plugin: the world's own sources, sampled once a frame. */
    sources_: () => ChunkSource[] = () => [];
    /** True while something else is showing this world (the editor's play realm has its own): no place is wanted, so every chunk is let go. */
    suspended = false;

    /** Adds a layer under `id`, or takes the new definition of one already there (its chunks stay and follow the new generation). */
    set<T>(id: string, def: ChunkLayer<T>): void {
        const had = this.layers_.get(id);
        if (had) had.def = def as ChunkLayer<unknown>;
        else this.layers_.set(id, { def: def as ChunkLayer<unknown>, chunks: new Map(), wanted: new Set() });
    }

    /** Takes a layer away, releasing every chunk it published and stopping what is being made. */
    remove(id: string): void {
        const layer = this.layers_.get(id);
        if (!layer) return;
        for (const c of layer.chunks.values()) this.drop(layer, c);
        this.layers_.delete(id);
    }

    has(id: string): boolean {
        return this.layers_.has(id);
    }

    /** Where the chunk of layer `id` at world (x, z) (x, y on an 'xy' layer) stands, or null when it is not wanted, not made, or there is no such layer. */
    stateAt(id: string, x: number, z: number): ChunkState | null {
        const layer = this.layers_.get(id);
        if (!layer) return null;
        const d = layer.def;
        const c = layer.chunks.get(keyOf(Math.floor((x - d.originX) / d.sizeX), Math.floor((z - d.originZ) / d.sizeZ)));
        return c ? stateOf(c, d.generation) : null;
    }

    /** Layer `id`'s chunks counted, or null when there is no such layer. */
    status(id: string): ChunkLayerStatus | null {
        const layer = this.layers_.get(id);
        if (!layer) return null;
        const s: ChunkLayerStatus = { ready: 0, stale: 0, pending: pendingOf(layer), making: 0, failed: 0 };
        for (const c of layer.chunks.values()) {
            if (c.making) s.making++;
            if (stateOf(c, layer.def.generation) === 'failed') { s.failed++; s.reason ??= c.reason; }
            if (c.value !== null) { if (c.publishedFor === layer.def.generation) s.ready++; else s.stale++; }
        }
        return s;
    }

    /** How many chunks every layer still wants made. */
    get pending(): number {
        let n = 0;
        for (const layer of this.layers_.values()) n += pendingOf(layer);
        return n;
    }

    /**
     * Makes the published chunks of layer `id` that touch the world square [x0, x1] by [z0, z1] again, each keeping its old version
     * until the new one replaces it: what changed there (a zone, a felled tree) changed only them.
     */
    invalidate(id: string, x0: number, z0: number, x1: number, z1: number): void {
        const layer = this.layers_.get(id);
        if (!layer) return;
        const d = layer.def;
        const cx0 = Math.floor((x0 - d.originX) / d.sizeX), cx1 = Math.floor((x1 - d.originX) / d.sizeX);
        const cz0 = Math.floor((z0 - d.originZ) / d.sizeZ), cz1 = Math.floor((z1 - d.originZ) / d.sizeZ);
        // What was settled is not any more: the layer is asked again from the next step.
        if (layer.walk) layer.walk.settledFor = undefined;
        for (const c of layer.chunks.values()) {
            if (c.cx < cx0 || c.cx > cx1 || c.cz < cz0 || c.cz > cz1) continue;
            if (c.value !== null) c.publishedFor = OUTDATED;
            c.failedFor = null;
            c.making?.abort.abort();
            c.making = null;
        }
    }

    /** Lets go of every chunk of every layer. */
    clear(): void {
        for (const id of [...this.layers_.keys()]) this.remove(id);
    }

    /**
     * One frame: releases what no source is near, then makes what is wanted, nearest first across every layer: the chunks a source
     * stands in at once, and the rest while `hasTime` says so (an `async` layer's, all of them).
     */
    step(hasTime: () => boolean): boolean {
        const world = this.suspended ? [] : this.sources_();
        const wanted: { layer: Layer<unknown>; cx: number; cz: number; dist: number }[] = [];
        for (const layer of this.layers_.values()) {
            const d = layer.def;
            const sources = d.sources ? [...d.sources()] : d.plane === 'xy' ? world.map((s) => ({ x: s.x, z: s.y ?? 0 })) : world;
            // What decides the walk beside the sources: a layer that changes its reach or its cells is walked again.
            const from = `${d.loadRadius},${d.unloadRadius},${d.sizeX},${d.sizeZ},${d.originX},${d.originZ},${d.extent ? d.extent.join(',') : ''}`;
            const slack = Math.min(d.sizeX, d.sizeZ) * WALK_SLACK;
            const was = layer.walk;
            const stood = was !== undefined && was.from === from && was.at.length === sources.length && sources.every((s, i) => {
                const o = was.at[i]!;
                return Math.abs(s.x - o.x) <= slack && Math.abs(s.z - o.z) <= slack
                    && Math.floor((s.x - d.originX) / d.sizeX) === Math.floor((o.x - d.originX) / d.sizeX)
                    && Math.floor((s.z - d.originZ) / d.sizeZ) === Math.floor((o.z - d.originZ) / d.sizeZ);
            });
            const near = stood ? was.near : new Map<string, number>();
            const keep = stood ? was.keep : new Set<string>();
            if (stood && was.settledFor === d.generation) continue;
            if (!stood) layer.walk = { from, at: sources.map((s) => ({ x: s.x, z: s.z })), near, keep };
            for (const s of stood ? [] : sources) {
                const reach = Math.max(d.loadRadius, d.unloadRadius);
                const x0 = Math.floor((s.x - reach - d.originX) / d.sizeX), x1 = Math.floor((s.x + reach - d.originX) / d.sizeX);
                const z0 = Math.floor((s.z - reach - d.originZ) / d.sizeZ), z1 = Math.floor((s.z + reach - d.originZ) / d.sizeZ);
                // A layer with an extent is walked over the part of the radius that lies in it, not over a radius that may be a thousand times the area.
                const ex = d.extent;
                const cx0 = ex ? Math.max(x0, ex[0]) : x0, cx1 = ex ? Math.min(x1, ex[2] - 1) : x1;
                const cz0 = ex ? Math.max(z0, ex[1]) : z0, cz1 = ex ? Math.min(z1, ex[3] - 1) : z1;
                for (let cz = cz0; cz <= cz1; cz++) for (let cx = cx0; cx <= cx1; cx++) {
                    const mx = d.originX + cx * d.sizeX, mz = d.originZ + cz * d.sizeZ;
                    const dist = Math.hypot(Math.max(mx - s.x, 0, s.x - mx - d.sizeX), Math.max(mz - s.z, 0, s.z - mz - d.sizeZ));
                    const key = keyOf(cx, cz);
                    if (dist <= d.unloadRadius) keep.add(key);
                    if (dist <= d.loadRadius && dist < (near.get(key) ?? Infinity)) near.set(key, dist);
                }
            }
            for (const [key, c] of layer.chunks) {
                if (near.has(key) || keep.has(key)) continue;
                this.drop(layer, c);
                layer.chunks.delete(key);
            }
            if (!stood) layer.wanted = new Set(near.keys());
            let unsettled = false;
            for (const [key, dist] of near) {
                const c = layer.chunks.get(key);
                const state = c ? stateOf(c, d.generation) : null;
                if (c?.making) unsettled = true;
                if (state === 'ready' || state === 'failed' || c?.making) continue;
                const [cx, cz] = key.split(',').map(Number) as [number, number];
                wanted.push({ layer, cx, cz, dist });
                unsettled = true;
            }
            // Nothing to make and nothing on its way: until its sources move or its generation does, this layer has nothing to say.
            layer.walk!.settledFor = unsettled ? undefined : d.generation;
        }
        wanted.sort((a, b) => a.dist - b.dist);
        const inFlight = new Map<Layer<unknown>, number>();
        for (const layer of this.layers_.values()) {
            let n = 0;
            for (const c of layer.chunks.values()) if (c.making) n++;
            inFlight.set(layer, n);
        }
        let nearLeft = false;
        let spent = false;
        for (const w of wanted) {
            // A layer whose chunks are answered later (off the main thread) takes no time from the frame: it is not held to the frame's budget.
            // Once the frame has said no it is not asked again for every chunk still wanted: there can be a thousand of them.
            if (w.dist > 0 && !w.layer.def.async && (spent || (spent = !hasTime()))) {
                if (w.dist <= Math.max(w.layer.def.sizeX, w.layer.def.sizeZ)) nearLeft = true;
                continue;
            }
            if ((inFlight.get(w.layer) ?? 0) >= MAX_IN_FLIGHT) continue;
            if (this.make(w.layer, w.cx, w.cz)) inFlight.set(w.layer, (inFlight.get(w.layer) ?? 0) + 1);
        }
        return nearLeft;
    }

    /** Makes one chunk; true when it is now being answered later. */
    private make(layer: Layer<unknown>, cx: number, cz: number): boolean {
        const key = keyOf(cx, cz);
        let c = layer.chunks.get(key);
        if (!c) {
            c = { cx, cz, value: null, publishedFor: null, making: null, failedFor: null };
            layer.chunks.set(key, c);
        }
        const chunk = c;
        const generation = layer.def.generation;
        const abort = createAbort();
        let made: unknown;
        try {
            made = layer.def.make(cx, cz, abort.signal);
        } catch (e) {
            this.fail(layer, chunk, generation, e);
            return false;
        }
        if (!(made instanceof Promise)) {
            if (made !== null) this.publish(layer, chunk, made, generation);
            else if (chunk.value === null) layer.chunks.delete(key);
            return false;
        }
        chunk.making = { generation, abort };
        made.then((value) => {
            // Thrown away if the chunk was let go, made again, or the layer moved on while this was being made.
            if (chunk.making?.abort !== abort || abort.signal.aborted) return;
            chunk.making = null;
            if (layer.chunks.get(key) !== chunk || generation !== layer.def.generation) return;
            if (value !== null) this.publish(layer, chunk, value, generation);
        }, (e: unknown) => {
            if (chunk.making?.abort !== abort || abort.signal.aborted) return;
            chunk.making = null;
            if (generation === layer.def.generation) this.fail(layer, chunk, generation, e);
        });
        return true;
    }

    private publish(layer: Layer<unknown>, c: Chunk<unknown>, value: unknown, generation: number | string): void {
        if (c.value !== null) layer.def.release(c.cx, c.cz, c.value);
        c.value = value;
        c.publishedFor = generation;
        c.failedFor = null;
        c.reason = undefined;
        layer.def.publish(c.cx, c.cz, value);
    }

    private fail(layer: Layer<unknown>, c: Chunk<unknown>, generation: number | string, e: unknown): void {
        c.failedFor = generation;
        c.reason = e instanceof Error ? e.message : String(e);
        log.error('chunks', `making chunk ${c.cx},${c.cz} of ${layer.def.label} failed`, e);
    }

    /** Releases what a chunk published and stops what it is making. */
    private drop(layer: Layer<unknown>, c: Chunk<unknown>): void {
        c.making?.abort.abort();
        c.making = null;
        if (c.value !== null) layer.def.release(c.cx, c.cz, c.value);
        c.value = null;
        c.publishedFor = null;
    }

    /** @internal The labels and progress of the layers still making chunks, for the bakes list. */
    progress_(): { label: string; progress: number; owner: object }[] {
        const out: { label: string; progress: number; owner: object }[] = [];
        for (const layer of this.layers_.values()) {
            const pending = pendingOf(layer);
            if (pending === 0) continue;
            const ready = layer.wanted.size - pending;
            out.push({ label: layer.def.label, progress: ready / layer.wanted.size, owner: layer });
        }
        return out;
    }
}

/** The wanted chunks not yet published for the generation now (nor failed for it). */
function pendingOf(layer: Layer<unknown>): number {
    let n = 0;
    for (const key of layer.wanted) {
        const c = layer.chunks.get(key);
        const state = c ? stateOf(c, layer.def.generation) : null;
        if (state !== 'ready' && state !== 'failed') n++;
    }
    return n;
}

function stateOf(c: Chunk<unknown>, generation: number | string): ChunkState {
    if (c.failedFor === generation) return 'failed';
    if (c.value !== null) return c.publishedFor === generation ? 'ready' : 'stale';
    return 'making';
}

/** The resource; {@link chunksOf} installs it where it is missing. @experimental */
export const ProceduralChunksRes = defineResource<ProceduralChunks>(new ProceduralChunks(), 'ProceduralChunks');

export function streamingSourcesOf(app: App): ChunkSource[] {
    const world = app.world;
    if (app.hasResource(EditorView)) {
        const at = editorViewpoint(app.getResource(EditorView));
        if (at) return [{ x: at.x, y: at.y, z: at.z }];
    }
    world.ensureTransformsComposed();
    const out: ChunkSource[] = [];
    for (const e of world.getEntitiesWithComponents([WorldStreamingSource, Transform])) {
        if (!(world.get(e, WorldStreamingSource) as WorldStreamingSourceData).enabled) continue;
        const p = (world.get(e, Transform) as TransformData).worldPosition;
        out.push({ x: p.x, y: p.y, z: p.z });
    }
    if (out.length > 0) return out;
    for (const e of world.getEntitiesWithComponents([Camera, Transform])) {
        if (!(world.get(e, Camera) as CameraData).isActive) continue;
        const p = (world.get(e, Transform) as TransformData).worldPosition;
        out.push({ x: p.x, y: p.y, z: p.z });
    }
    return out;
}

/** The App's procedural chunks, installed (with the system that steps them, after Update) on first use. */
export function chunksOf(app: App): ProceduralChunks {
    if (!app.hasResource(ProceduralChunksRes)) {
        const chunks = new ProceduralChunks();
        chunks.sources_ = () => streamingSourcesOf(app);
        app.insertResource(ProceduralChunksRes, chunks);
        const bakes = bakesOf(app);
        const shown = new Set<object>();
        app.addSystemToSchedule(Schedule.PostUpdate, defineSystem([], () => {
            // Chunks beside a source that are still to be made here are a hole the player is standing next to: the frame gives more.
            app.measureFrameScope('chunks.step', () => bakes.urge(chunks, chunks.step(() => bakes.hasTime(chunks))));
            const now = new Set<object>();
            for (const p of chunks.progress_()) { bakes.mark(p.owner, p.label, p.progress); now.add(p.owner); }
            for (const owner of shown) if (!now.has(owner)) bakes.clear(owner);
            shown.clear();
            for (const owner of now) shown.add(owner);
        }, { name: 'ProceduralChunkSystem' }));
    }
    return app.getResource(ProceduralChunksRes);
}