《游戏引擎实现原理》12.3 实体生命周期与句柄复用

// file: src/ecs/entity-registry.ts
// tier: L1
// verify: npx vitest run src/ecs/entity-registry.test.ts
//
// 实体生命周期管理：直接复用第 6 章的世代句柄 SlotMap。
// 句柄 = 「槽位索引 + 世代」，销毁时世代自增，旧句柄立刻失效；
// 新实体复用同一槽位时拿到的是新世代，因此不会和旧句柄混淆。
// 另附「延迟销毁」命令缓冲：本帧内先标记，帧末统一 flush。

import { SlotMap, handleGeneration, handleIndex, type Handle } from '../core/slotmap.ts';

/** 实体上挂的最小身份信息（真正的组件在组件存储里）。 */
interface EntityTag {
  serial: number;
}

export class EntityRegistry {
  #slots = new SlotMap<EntityTag>();
  #pending: Handle[] = [];
  #serial = 0;

  get count(): number {
    return this.#slots.size;
  }

  get pendingCount(): number {
    return this.#pending.length;
  }

  spawn(): Handle {
    return this.#slots.insert({ serial: this.#serial++ });
  }

  alive(h: Handle): boolean {
    return this.#slots.has(h);
  }

  /** 句柄的槽位号——组件存储用它当稀疏 ID。 */
  slotOf(h: Handle): number {
    return handleIndex(h);
  }

  /** 句柄的世代号——同一槽位的第几任住户。 */
  generationOf(h: Handle): number {
    return handleGeneration(h);
  }

  serialOf(h: Handle): number {
    return this.#slots.expect(h).serial;
  }

  /** 立即销毁：槽位进空闲栈，世代自增。 */
  destroy(h: Handle): boolean {
    return this.#slots.remove(h);
  }

  /** 延迟销毁：本帧内只入队，帧末由 flush 统一执行。 */
  queueDestroy(h: Handle): void {
    this.#pending.push(h);
  }

  /** 执行所有排队的销毁；对同一句柄重复排队只会销毁一次（第二次已失效）。 */
  flush(): number {
    let done = 0;
    for (const h of this.#pending) {
      if (this.#slots.remove(h)) done++;
    }
    this.#pending.length = 0;
    return done;
  }

  handles(): Handle[] {
    return [...this.#slots.entries()].map(([h]) => h);
  }
}

// file: src/ecs/entity-registry.test.ts
// tier: L1
// verify: npx vitest run src/ecs/entity-registry.test.ts

import { describe, expect, it } from 'vitest';
import { EntityRegistry } from './entity-registry.ts';

describe('EntityRegistry 生命周期', () => {
  it('spawn 后 alive，destroy 后旧句柄立即失效', () => {
    const reg = new EntityRegistry();
    const e = reg.spawn();
    expect(reg.alive(e)).toBe(true);
    expect(reg.destroy(e)).toBe(true);
    expect(reg.alive(e)).toBe(false);
    expect(reg.count).toBe(0);
  });

  it('槽位复用：新实体沿用旧槽位号，但世代不同', () => {
    const reg = new EntityRegistry();
    const old = reg.spawn();
    reg.destroy(old);
    const fresh = reg.spawn();
    expect(reg.slotOf(fresh)).toBe(reg.slotOf(old)); // 同一槽位
    expect(reg.generationOf(fresh)).toBe(reg.generationOf(old) + 1); // 世代 +1
    expect(reg.alive(old)).toBe(false);
    expect(reg.alive(fresh)).toBe(true);
    expect(() => reg.serialOf(old)).toThrow(/Stale handle/); // 旧句柄取不到身份
  });

  it('延迟销毁：flush 之前实体仍活着', () => {
    const reg = new EntityRegistry();
    const a = reg.spawn();
    const b = reg.spawn();
    reg.queueDestroy(a);
    expect(reg.pendingCount).toBe(1);
    expect(reg.alive(a)).toBe(true); // 尚未真正销毁
    expect(reg.flush()).toBe(1);
    expect(reg.alive(a)).toBe(false);
    expect(reg.alive(b)).toBe(true);
    expect(reg.pendingCount).toBe(0);
  });

  it('同一句柄重复排队只销毁一次', () => {
    const reg = new EntityRegistry();
    const e = reg.spawn();
    reg.queueDestroy(e);
    reg.queueDestroy(e);
    expect(reg.flush()).toBe(1); // 第二次已失效，不计入
  });

  it('churn 之后槽位数组不无限增长（复用生效）', () => {
    const reg = new EntityRegistry();
    let peak = 0;
    for (let i = 0; i < 1000; i++) {
      const e = reg.spawn();
      if (reg.count > peak) peak = reg.count;
      reg.destroy(e);
    }
    expect(peak).toBe(1); // 永远只有一个活跃实体，槽位被复用
  });

  it('特征化：世代 12 位在复用第 4096 次回绕到 0，与 NULL_HANDLE 撞车', () => {
    // 记录既有行为（非理想行为）：同一槽位复用 4095 次后世代归 0，
    // 生成的句柄等于 NULL_HANDLE(0)，SlotMap.remove 会把它当空句柄而拒绝释放。
    const reg = new EntityRegistry();
    let nullAt = -1;
    for (let i = 0; i < 5000; i++) {
      const e = reg.spawn();
      if (e === 0 && nullAt < 0) nullAt = i;
      reg.destroy(e);
    }
    expect(nullAt).toBe(4095);
  });
});

// file: bench/entity-lifecycle-bench.ts
// tier: B
// 运行：node --expose-gc bench/entity-lifecycle-bench.ts
// 对照「句柄复用」与「单调递增不复用」在 churn 场景下的代价。
// 场景：始终维持 K 个实体存活，做 N 次「销毁一个 + 新建一个」。
//   A 复用：EntityRegistry（世代句柄，槽位进空闲栈复用）
//   B 不复用：每次新建都往数组尾部 push 一个新下标，销毁只留墓碑
// 量：N 次 churn 耗时、用过的最大槽位下标（≈ 槽位数组长度）。

import { EntityRegistry } from '../src/ecs/entity-registry.ts';
import type { Handle } from '../src/core/slotmap.ts';

const K = 1024;
const N = 1_000_000;
let sink = 0;

function churnReuse(): { ms: number; maxIndex: number } {
  const reg = new EntityRegistry();
  const ring: Handle[] = [];
  for (let i = 0; i < K; i++) ring.push(reg.spawn());
  let maxIndex = 0;
  for (const h of ring) maxIndex = Math.max(maxIndex, reg.slotOf(h));
  const t0 = performance.now();
  for (let i = 0; i < N; i++) {
    const slot = i % K;
    reg.destroy(ring[slot]!);
    const h = reg.spawn(); // 复用刚释放的槽位
    ring[slot] = h;
    maxIndex = Math.max(maxIndex, reg.slotOf(h));
  }
  return { ms: performance.now() - t0, maxIndex };
}

function churnMonotonic(): { ms: number; maxIndex: number } {
  const ring: number[] = [];
  const slots: number[] = [];
  for (let i = 0; i < K; i++) {
    const idx = slots.length;
    slots.push(1);
    ring.push(idx);
  }
  const t0 = performance.now();
  for (let i = 0; i < N; i++) {
    const slot = i % K;
    const idx = slots.length; // 单调递增，永不复用
    slots.push(1);
    sink += ring[slot]! & 0;
    ring[slot] = idx;
  }
  return { ms: performance.now() - t0, maxIndex: slots.length - 1 };
}

function median(xs: number[]): number {
  const s = [...xs].sort((a, b) => a - b);
  const mid = s.length >> 1;
  return s.length % 2 ? s[mid]! : (s[mid - 1]! + s[mid]!) / 2;
}

const REPS = 9;
const reuseT: number[] = [];
const reuseMax: number[] = [];
const mono: { ms: number; maxIndex: number }[] = [];
for (let r = 0; r < REPS; r++) {
  const a = churnReuse();
  reuseT.push(a.ms);
  reuseMax.push(a.maxIndex);
  mono.push(churnMonotonic());
}

console.log(`K = ${K}, N = ${N}`);
console.log(`[reuse]     ${median(reuseT).toFixed(2)} ms, 最大槽位下标 = ${Math.max(...reuseMax)}`);
console.log(`[monotonic] ${median(mono.map((m) => m.ms)).toFixed(2)} ms, 最大槽位下标 = ${mono[0]!.maxIndex}`);
console.log(`sink = ${sink}`);