《游戏引擎实现原理》12.2 组件存储：稀疏集与 archetype

// file: src/ecs/sparse-world.ts
// tier: L1
// verify: npx vitest run src/ecs/sparse-world.test.ts
//
// 组件存储方案 A：稀疏集。每种组件一个 SparseSet，用实体下标当稀疏 ID。
// 增删是 O(1)；查询要跨多个组件的 SparseSet 求交集（这里用最小的那个当基准）。
// 优点：组件可随时单独增删，存储紧凑；缺点：查询要按「组件集合」现场求交。

import { SparseSet } from '../core/sparse-set.ts';

export type ComponentId = number;

export class SparseWorld {
  #stores = new Map<ComponentId, SparseSet<unknown>>();
  #live = new SparseSet<true>();

  get entityCount(): number {
    return this.#live.size;
  }

  #store(id: ComponentId): SparseSet<unknown> {
    let s = this.#stores.get(id);
    if (s === undefined) {
      s = new SparseSet<unknown>();
      this.#stores.set(id, s);
    }
    return s;
  }

  spawn(index: number): void {
    this.#live.add(index, true);
  }

  destroy(index: number): boolean {
    if (!this.#live.has(index)) return false;
    for (const s of this.#stores.values()) s.remove(index);
    return this.#live.remove(index);
  }

  add<T>(index: number, id: ComponentId, value: T): void {
    this.#store(id).add(index, value);
  }

  get<T>(index: number, id: ComponentId): T | undefined {
    return this.#store(id).get(index) as T | undefined;
  }

  /** 取同时拥有全部组件的实体下标；以最小集合为基准，其余做成员检查。 */
  query(ids: ComponentId[]): number[] {
    let smallest: SparseSet<unknown> | undefined;
    for (const id of ids) {
      const s = this.#store(id);
      if (smallest === undefined || s.size < smallest.size) smallest = s;
    }
    if (smallest === undefined) return [];
    const out: number[] = [];
    for (const index of smallest.ids()) {
      if (!this.#live.has(index)) continue;
      let ok = true;
      for (const id of ids) {
        if (!this.#store(id).has(index)) {
          ok = false;
          break;
        }
      }
      if (ok) out.push(index);
    }
    return out;
  }
}

// file: src/ecs/archetype-world.ts
// tier: L1
// verify: npx vitest run src/ecs/archetype-world.test.ts
//
// 组件存储方案 B：archetype。把「组件集合完全相同」的实体分到同一组，
// 组内每种组件一个连续的列（SoA）。查询只要挑出包含所需组件的组，直接整列遍历。
// 代价：给实体增删组件要在组之间「搬迁」（逐列拷贝），比稀疏集重。

export type ComponentId = number;

export class Archetype {
  readonly ids: readonly ComponentId[];
  readonly key: string;
  readonly cols = new Map<ComponentId, unknown[]>();
  readonly rows: number[] = []; // 每行对应的实体下标

  constructor(ids: ComponentId[]) {
    this.ids = ids;
    this.key = ids.join(',');
    for (const id of ids) this.cols.set(id, []);
  }

  get count(): number {
    return this.rows.length;
  }

  push(index: number, values: Map<ComponentId, unknown>): number {
    for (const id of this.ids) this.cols.get(id)!.push(values.get(id));
    this.rows.push(index);
    return this.rows.length - 1;
  }

  column<T>(id: ComponentId): T[] {
    return this.cols.get(id) as T[];
  }

  /** swap-remove 第 row 行；返回被搬进 row 的实体下标，row 本就是末行时返回 -1。 */
  swapRemove(row: number): number {
    const last = this.rows.length - 1;
    for (const id of this.ids) {
      const c = this.cols.get(id)!;
      c[row] = c[last];
      c.pop();
    }
    const moved = this.rows[last];
    this.rows[row] = moved;
    this.rows.pop();
    return row === last ? -1 : moved;
  }
}

interface Loc {
  arch: Archetype;
  row: number;
}

export class ArchetypeWorld {
  #archetypes = new Map<string, Archetype>();
  #loc = new Map<number, Loc>();

  get entityCount(): number {
    return this.#loc.size;
  }

  get archetypeCount(): number {
    return this.#archetypes.size;
  }

  #archetypeFor(ids: ComponentId[]): Archetype {
    const sorted = [...ids].sort((a, b) => a - b);
    const key = sorted.join(',');
    let a = this.#archetypes.get(key);
    if (a === undefined) {
      a = new Archetype(sorted);
      this.#archetypes.set(key, a);
    }
    return a;
  }

  /** 建实体：给出它当前拥有的全部组件（一次性落到对应 archetype）。 */
  spawn(index: number, values: Map<ComponentId, unknown>): void {
    const arch = this.#archetypeFor([...values.keys()]);
    this.#loc.set(index, { arch, row: arch.push(index, values) });
  }

  destroy(index: number): boolean {
    const loc = this.#loc.get(index);
    if (loc === undefined) return false;
    const moved = loc.arch.swapRemove(loc.row);
    if (moved !== -1) this.#loc.get(moved)!.row = loc.row;
    this.#loc.delete(index);
    return true;
  }

  /** 取包含全部所需组件的 archetype，供整列遍历。 */
  matching(ids: ComponentId[]): Archetype[] {
    const out: Archetype[] = [];
    for (const a of this.#archetypes.values()) {
      if (a.count === 0) continue;
      let ok = true;
      for (const id of ids) {
        if (!a.cols.has(id)) {
          ok = false;
          break;
        }
      }
      if (ok) out.push(a);
    }
    return out;
  }
}

// snippet: bench/ecs-storage-bench.ts 的核心——同一组操作跑两种存储
// 建 N 个都有 POS+VEL+SPR 的实体；查 POS+VEL 并原地更新；各跑 REPS 次取中位数。
function buildSparse(): SparseWorld {
  const w = new SparseWorld();
  for (let i = 0; i < N; i++) {
    w.spawn(i);
    w.add<Vec2>(i, POS, { x: i, y: 0 });
    w.add<Vec2>(i, VEL, { x: 1, y: 0 });
    w.add<number>(i, SPR, i & 7);
  }
  return w;
}

function buildArchetype(): ArchetypeWorld {
  const w = new ArchetypeWorld();
  for (let i = 0; i < N; i++) {
    w.spawn(i, new Map([[POS, { x: i, y: 0 }], [VEL, { x: 1, y: 0 }], [SPR, i & 7]]));
  }
  return w;
}

function updateSparse(w: SparseWorld): number {
  const ids = w.query([POS, VEL]);        // 求交：拿最小集合当基准
  for (const i of ids) {
    const p = w.get<Vec2>(i, POS)!;
    const v = w.get<Vec2>(i, VEL)!;
    p.x += v.x;
    p.y += v.y;
  }
  return ids.length;
}

function updateArchetype(w: ArchetypeWorld): number {
  let n = 0;
  for (const a of w.matching([POS, VEL])) { // 组即结果：直接整列扫
    const px = a.column<Vec2>(POS);
    const py = a.column<Vec2>(VEL);
    for (let r = 0; r < a.count; r++) {
      px[r].x += py[r].x;
      px[r].y += py[r].y;
      n++;
    }
  }
  return n;
}