《游戏引擎实现原理》6.3 稀疏集、句柄回收与 ECS 的接缝

// file: src/core/sparse-set.ts
// tier: L1
// verify: npx vitest run src/core/sparse-set.test.ts
//
// 稀疏集（sparse set）：sparse 数组把「稀疏 ID」映射到 dense 下标，
// dense 数组紧凑存值。O(1) 增删查 + 紧凑遍历（dense 连续，缓存友好）。
// 删除用 swap-remove：把 dense 末尾元素搬到被删位置，保持 dense 无空洞。

export class SparseSet<T> {
  #sparse: number[] = []; // sparse[id] = dense 下标，-1 表示不存在
  #dense: T[] = [];
  #denseIds: number[] = [];

  get size(): number {
    return this.#dense.length;
  }

  has(id: number): boolean {
    const d = this.#sparse[id];
    return (
      d !== undefined &&
      d >= 0 &&
      d < this.#dense.length &&
      this.#denseIds[d] === id
    );
  }

  get(id: number): T | undefined {
    return this.has(id) ? this.#dense[this.#sparse[id]] : undefined;
  }

  /** 插入：id 已存在则返回 false（不覆盖）。 */
  add(id: number, value: T): boolean {
    if (this.has(id)) return false;
    this.#sparse[id] = this.#dense.length;
    this.#denseIds.push(id);
    this.#dense.push(value);
    return true;
  }

  /** 删除：swap-remove，O(1)，dense 始终保持紧凑。 */
  remove(id: number): boolean {
    if (!this.has(id)) return false;
    const d = this.#sparse[id];
    const last = this.#dense.length - 1;
    const lastId = this.#denseIds[last];
    this.#dense[d] = this.#dense[last];
    this.#denseIds[d] = lastId;
    this.#sparse[lastId] = d;
    this.#dense.pop();
    this.#denseIds.pop();
    this.#sparse[id] = -1;
    return true;
  }

  /** 紧凑遍历：直接按 dense 顺序走，无空洞、无分支。 */
  *values(): Generator<T> {
    for (let i = 0; i < this.#dense.length; i++) yield this.#dense[i];
  }

  ids(): number[] {
    return [...this.#denseIds];
  }

  /** 暴露内部 dense 数组本身，用于断言「连续、无空洞」。 */
  denseView(): readonly T[] {
    return this.#dense;
  }
}

// file: src/core/sparse-set.test.ts
// tier: L1
// verify: npx vitest run src/core/sparse-set.test.ts

import { describe, expect, it } from 'vitest';
import { SparseSet } from './sparse-set.ts';

describe('SparseSet 基本操作', () => {
  it('增删查 O(1) 语义正确', () => {
    const s = new SparseSet<string>();
    expect(s.add(3, 'three')).toBe(true);
    expect(s.add(1000, 'grand')).toBe(true);
    expect(s.add(3, 'dup')).toBe(false); // 重复 id 不覆盖
    expect(s.size).toBe(2);
    expect(s.get(3)).toBe('three');
    expect(s.get(1000)).toBe('grand');
    expect(s.get(999)).toBeUndefined();
    expect(s.has(3)).toBe(true);
    expect(s.remove(3)).toBe(true);
    expect(s.remove(3)).toBe(false); // 二次删除无效
    expect(s.has(3)).toBe(false);
    expect(s.size).toBe(1);
  });

  it('稀疏 id 不撑大 dense（大 id 也只用 1 个槽）', () => {
    const s = new SparseSet<number>();
    s.add(1_000_000, 42);
    expect(s.size).toBe(1);
    expect(s.denseView().length).toBe(1); // dense 只有 1 个元素
  });
});

describe('dense 紧凑性（缓存友好）', () => {
  it('删除后 dense 无空洞：length === size，且无 undefined', () => {
    const s = new SparseSet<number>();
    for (let i = 0; i < 100; i++) s.add(i, i * 10);
    // 删掉一半（偶数 id）
    for (let i = 0; i < 100; i += 2) s.remove(i);
    expect(s.size).toBe(50);
    const dense = s.denseView();
    expect(dense.length).toBe(50); // 与 size 严格相等 => 无空洞
    expect(dense.includes(undefined as never)).toBe(false);
  });

  it('swap-remove：被删位置填入 dense 末尾元素', () => {
    const s = new SparseSet<string>();
    s.add(10, 'a');
    s.add(20, 'b');
    s.add(30, 'c');
    // dense 顺序 = ['a','b','c']，删 'a'（下标 0）
    s.remove(10);
    // 末尾 'c' 被搬到下标 0
    expect([...s.values()]).toEqual(['c', 'b']);
    expect(s.ids()).toEqual([30, 20]);
  });

  it('遍历次数恒等于 size（紧凑遍历，无分支跳过）', () => {
    const s = new SparseSet<number>();
    for (let i = 0; i < 1000; i++) s.add(i * 7, i);
    for (let i = 0; i < 500; i++) s.remove(i * 7);
    let visited = 0;
    for (const _ of s.values()) visited++;
    expect(visited).toBe(s.size);
    expect(visited).toBe(500);
  });

  it('内部 dense 是真正的 packed 数组（无 hole）', () => {
    const s = new SparseSet<number>();
    for (let i = 0; i < 64; i++) s.add(i, i);
    for (let i = 0; i < 64; i += 3) s.remove(i);
    const dense = s.denseView();
    // packed 数组：Object.keys 的数量等于 length（hole 不会产生 key）
    expect(Object.keys(dense).length).toBe(dense.length);
  });
});