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.

5.8 KB
Raw Blame
// SPDX-License-Identifier: Apache-2.0
// SPDX-FileCopyrightText: Copyright (c) 2024-present ESEngine Team
/**
 * @file  Systems whose order nobody decided.
 *
 *        A schedule runs its systems in topological order, and for two systems
 *        with no edge between them that order falls out of registration and a
 *        depth-first walk. That is fine while they touch different data. When
 *        one writes what the other reads, the result depends on which happened
 *        to come first — so adding a third system, or moving a plugin in the
 *        build list, can change what the game does with nothing to point at.
 *
 *        Naming those pairs is also the prerequisite for ever running them at
 *        the same time: a pair that must not be reordered cannot be a batch.
 */
import type { SystemDef } from '../ecs/system';
import { accessOf, conflicts, conflictBetween, type SystemAccess } from './access';

/** A system with the ordering it declared, as a schedule holds it. */
export interface OrderedSystem {
    system: SystemDef;
    runBefore?: readonly string[];
    runAfter?: readonly string[];
}

/** Resolves an ordering name to the indices it refers to (a system, or a set). */
export type ResolveTargets = (name: string) => readonly number[];

/**
 * `edges[i]` lists the indices that must run BEFORE `i`. `runBefore` is folded
 * in symmetrically, so both spellings of one relationship produce one edge.
 */
export function dependencyEdges(
    systems: readonly OrderedSystem[],
    resolveTargets: ResolveTargets,
): number[][] {
    const edges: number[][] = systems.map(() => []);
    const addEdge = (from: number, to: number): void => {
        if (from === to) return;
        const list = edges[to];
        if (!list.includes(from)) list.push(from);
    };
    for (let i = 0; i < systems.length; i++) {
        for (const name of systems[i].runAfter ?? []) {
            for (const j of resolveTargets(name)) addEdge(j, i);
        }
        for (const name of systems[i].runBefore ?? []) {
            for (const j of resolveTargets(name)) addEdge(i, j);
        }
    }
    return edges;
}

/** Two systems that touch the same data with nothing saying which goes first. */
export interface Ambiguity {
    /** The two system names, in registration order. */
    a: string;
    b: string;
    /** The components and resources they disagree over. */
    over: string[];
}

/**
 * Everything that must run before each index, transitively.
 *
 * Exported because the schedule needs it for a second reason: a system may only
 * start beside an unfinished one if it does not depend on it, and "depends on"
 * has to include the edge it inherited rather than declared.
 */
export function ancestors(edges: readonly number[][]): Set<number>[] {
    const out: Set<number>[] = edges.map(() => new Set<number>());
    const done = new Uint8Array(edges.length);
    const visit = (i: number, stack: Set<number>): void => {
        if (done[i] || stack.has(i)) return;
        stack.add(i);
        for (const dep of edges[i]) {
            visit(dep, stack);
            out[i].add(dep);
            for (const t of out[dep]) out[i].add(t);
        }
        stack.delete(i);
        done[i] = 1;
    };
    for (let i = 0; i < edges.length; i++) visit(i, new Set<number>());
    return out;
}

/**
 * Every pair of systems in one schedule that conflicts and is unordered.
 *
 * Reported in registration order and deduplicated, so a schedule's ambiguities
 * are a stable list something can be held to.
 */
export function detectAmbiguities(
    systems: readonly OrderedSystem[],
    resolveTargets: ResolveTargets,
): Ambiguity[] {
    if (systems.length < 2) return [];
    const edges = dependencyEdges(systems, resolveTargets);
    const before = ancestors(edges);
    const access: SystemAccess[] = systems.map((s) => accessOf(s.system));

    const found: Ambiguity[] = [];
    for (let i = 0; i < systems.length; i++) {
        for (let j = i + 1; j < systems.length; j++) {
            if (before[i].has(j) || before[j].has(i)) continue;
            if (!conflicts(access[i], access[j])) continue;
            found.push({
                a: systems[i].system._name,
                b: systems[j].system._name,
                over: conflictBetween(access[i], access[j]),
            });
        }
    }
    return found;
}

/**
 * Systems grouped into batches that could run at the same time: a batch is free
 * of conflicts within itself and its dependencies are met by the batches before
 * it.
 *
 * A measurement, not the plan: the schedule starts systems in sorted order and
 * overlaps by this same rule, which shows on the clock only where a system
 * awaits — a synchronous one finishes before the next can start.
 */
export function parallelBatches(
    systems: readonly OrderedSystem[],
    resolveTargets: ResolveTargets,
): string[][] {
    const edges = dependencyEdges(systems, resolveTargets);
    const access: SystemAccess[] = systems.map((s) => accessOf(s.system));
    const placed = new Int32Array(systems.length).fill(-1);
    const batches: number[][] = [];

    let remaining = systems.length;
    while (remaining > 0) {
        const batch: number[] = [];
        for (let i = 0; i < systems.length; i++) {
            if (placed[i] >= 0) continue;
            if (edges[i].some((dep) => placed[dep] < 0)) continue;
            if (batch.some((k) => conflicts(access[i], access[k]))) continue;
            batch.push(i);
        }
        // A cycle in the edges would leave nothing runnable; the sort reports
        // that with the path, so here it only has to stop.
        if (batch.length === 0) break;
        for (const i of batch) placed[i] = batches.length;
        batches.push(batch);
        remaining -= batch.length;
    }
    return batches.map((b) => b.map((i) => systems[i].system._name));
}