《游戏引擎实现原理》13.3 系统依赖声明与并行调度

// file: src/core/system-scheduler.ts
// tier: L1
// verify: npx vitest run src/core/system-scheduler.test.ts
//
// 系统依赖声明与并行分组。每个系统声明读哪些、写哪些「数据槽」，
// 另可用 after 声明「必须在某系统之后」的显式顺序依赖。
// 两个系统存在「写-读」或「写-写」重叠即冲突，不能同组。
// 分组用最长路径分层：组号 = 与之冲突/需后置的系统的最大组号 + 1。

export interface SystemDecl {
  name: string;
  reads: readonly string[];
  writes: readonly string[];
  /** 显式顺序依赖：这些系统必须先于本系统（须声明在更前面）。 */
  after?: readonly string[];
}

export interface SchedulePlan {
  /** 组内系统可并行，组间必须按顺序（一次同步屏障）。 */
  groups: SystemDecl[][];
  /** 每个系统被分到的组号。 */
  level: Map<string, number>;
  /** 冲突边总数（无向图，每个冲突对记一次）。 */
  conflictEdges: number;
}

function overlaps(a: readonly string[], b: readonly string[]): boolean {
  for (const x of a) if (b.includes(x)) return true;
  return false;
}

/** 两个系统是否冲突：一方写、另一方读或写同一数据槽。 */
export function conflicts(a: SystemDecl, b: SystemDecl): boolean {
  return (
    overlaps(a.writes, b.reads) ||
    overlaps(a.writes, b.writes) ||
    overlaps(b.writes, a.reads)
  );
}

/**
 * 最长路径分层：按声明顺序，每个系统的组号 = 所有「与它冲突或它要后置」
 * 的已处理系统的组号 + 1 的最大值。这样同组内必不冲突，且顺序依赖被满足。
 */
export function planSchedule(systems: readonly SystemDecl[]): SchedulePlan {
  const level = new Map<string, number>();
  const groups: SystemDecl[][] = [];
  for (let i = 0; i < systems.length; i++) {
    const s = systems[i]!;
    let lv = 0;
    for (let j = 0; j < i; j++) {
      const o = systems[j]!;
      const mustAfter = s.after?.includes(o.name) ?? false;
      if (mustAfter || conflicts(s, o)) {
        lv = Math.max(lv, (level.get(o.name) ?? 0) + 1);
      }
    }
    level.set(s.name, lv);
    (groups[lv] ??= []).push(s);
  }
  let edges = 0;
  for (let i = 0; i < systems.length; i++) {
    for (let j = i + 1; j < systems.length; j++) {
      if (conflicts(systems[i]!, systems[j]!)) edges++;
    }
  }
  return { groups, level, conflictEdges: edges };
}

/** 校验：任一组的内部都不存在冲突。 */
export function validatePlan(plan: SchedulePlan): boolean {
  for (const g of plan.groups) {
    for (let i = 0; i < g.length; i++) {
      for (let j = i + 1; j < g.length; j++) {
        if (conflicts(g[i]!, g[j]!)) return false;
      }
    }
  }
  return true;
}

/** 把分组渲染成可读文本，一行一组。 */
export function formatPlan(plan: SchedulePlan): string {
  return plan.groups
    .map((g, i) => `G${i}: ${g.map((s) => s.name).join(', ')}`)
    .join('\n');
}

// file: bench/schedule-demo.ts
// tier: L1
// verify: node bench/schedule-demo.ts
//
// 用《微光岛》的系统声明读写依赖，跑出并行分组。
// 对比「粗粒度槽（transform 整体）」与「细粒度槽（position/rotation 分开）」。

import { formatPlan, planSchedule, validatePlan, type SystemDecl } from '../src/core/system-scheduler.ts';

// 粗粒度：所有变换统一叫 transform，凡是碰变换的系统都互相冲突。
const coarse: SystemDecl[] = [
  { name: 'input', reads: ['device'], writes: ['intent'] },
  { name: 'movement', reads: ['transform', 'intent'], writes: ['transform', 'velocity'] },
  { name: 'physics', reads: ['transform', 'velocity'], writes: ['transform', 'velocity'] },
  { name: 'collision', reads: ['transform'], writes: ['contacts'] },
  { name: 'animation', reads: ['animation'], writes: ['transform'] },
  { name: 'particles', reads: ['particle'], writes: ['particle'] },
  { name: 'audio', reads: ['audio'], writes: ['audio'] },
  { name: 'culling', reads: ['transform'], writes: ['visible'] },
  { name: 'render', reads: ['transform', 'visible'], writes: ['drawlist'] },
  { name: 'ui', reads: ['ui'], writes: ['ui'], after: ['render'] },
];

// 细粒度：把 transform 拆成 position / rotation / velocity，冲突面收窄。
const fine: SystemDecl[] = [
  { name: 'input', reads: ['device'], writes: ['intent'] },
  { name: 'movement', reads: ['position', 'intent'], writes: ['position', 'velocity'] },
  { name: 'physics', reads: ['position', 'velocity'], writes: ['position', 'velocity'] },
  { name: 'collision', reads: ['position'], writes: ['contacts'] },
  { name: 'animation', reads: ['animation'], writes: ['rotation'] },
  { name: 'particles', reads: ['particle'], writes: ['particle'] },
  { name: 'audio', reads: ['audio'], writes: ['audio'] },
  { name: 'culling', reads: ['position', 'rotation'], writes: ['visible'] },
  { name: 'render', reads: ['position', 'rotation', 'visible'], writes: ['drawlist'] },
  { name: 'ui', reads: ['ui'], writes: ['ui'], after: ['render'] },
];

function report(tag: string, systems: SystemDecl[]): void {
  const plan = planSchedule(systems);
  const maxParallel = Math.max(...plan.groups.map((g) => g.length));
  console.log(`\n== ${tag} ==`);
  console.log(`systems=${systems.length} groups=${plan.groups.length} conflictEdges=${plan.conflictEdges} maxParallel=${maxParallel}`);
  console.log(formatPlan(plan));
  console.log(`valid=${validatePlan(plan)}`);
}

report('coarse: transform', coarse);
report('fine: position/rotation', fine);

== coarse: transform ==
systems=10 groups=8 conflictEdges=14 maxParallel=3
G0: input, particles, audio
G1: movement
G2: physics
G3: collision
G4: animation
G5: culling
G6: render
G7: ui
valid=true

== fine: position/rotation ==
systems=10 groups=6 conflictEdges=11 maxParallel=4
G0: input, animation, particles, audio
G1: movement
G2: physics
G3: collision, culling
G4: render
G5: ui
valid=true

// snippet: src/core/system-scheduler.test.ts（节选）
it('写-读链形成逐级分组（c 必须在 b 之后）', () => {
  const p = planSchedule([
    sys('a', [], ['t']),
    sys('b', ['t'], ['u']),
    sys('c', ['u'], ['v']),
  ]);
  expect(p.groups.length).toBe(3);
  expect(p.level.get('c')).toBe(2);
  expect(p.conflictEdges).toBe(2);
});

it('after 显式顺序：无槽冲突也强制后置', () => {
  const p = planSchedule([
    sys('render', [], ['drawlist']),
    sys('ui', [], ['ui'], ['render']),
  ]);
  expect(p.level.get('ui')).toBe(1);
  expect(p.groups.length).toBe(2);
});