《游戏引擎实现原理》13.1 查询匹配与缓存命中

// file: src/core/query-cache.ts
// tier: L1
// verify: npx vitest run src/core/query-cache.test.ts
//
// ECS 查询匹配与结果缓存：实体用位掩码表示「拥有哪些组件」，
// 查询用 all / none 两个掩码描述「必须都有 / 必须都没有」。
// 缓存按查询键存结果，用一个全局 revision 判断是否失效。

export type EntityId = number;

/** 把组件类型 id 列表压成一个位掩码；位 i 置位表示拥有组件 i。 */
export function maskOf(types: readonly number[]): number {
  let m = 0;
  for (const t of types) m |= 1 << t;
  return m >>> 0;
}

export interface Query {
  /** 必须全部拥有的组件掩码。 */
  all: number;
  /** 必须一个都不拥有的组件掩码。 */
  none: number;
}

export function makeQuery(all: readonly number[], none: readonly number[] = []): Query {
  return { all: maskOf(all), none: maskOf(none) };
}

/** 单个实体是否满足查询：all 全置位、none 全清位。 */
export function matches(mask: number, q: Query): boolean {
  return (mask & q.all) === q.all && (mask & q.none) === 0;
}

interface CacheEntry {
  entities: EntityId[];
  revision: number;
}

export interface QueryStats {
  hits: number;
  misses: number;
  rebuilds: number;
}

/**
 * 查询引擎：持有实体掩码表，提供带缓存与不带缓存两种查询。
 * 任何一次组件增删都会把 revision 加一，使所有缓存条目同时失效——
 * 这是最保守、也最容易证明正确的失效策略。
 */
export class QueryEngine {
  #masks = new Map<EntityId, number>();
  #revision = 0;
  #cache = new Map<string, CacheEntry>();
  #hits = 0;
  #misses = 0;
  #rebuilds = 0;

  get revision(): number {
    return this.#revision;
  }

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

  get stats(): QueryStats {
    return { hits: this.#hits, misses: this.#misses, rebuilds: this.#rebuilds };
  }

  /** 直接设置一个实体的组件掩码；掩码为 0 视为移除该实体。 */
  setMask(id: EntityId, mask: number): void {
    if (mask === 0) this.#masks.delete(id);
    else this.#masks.set(id, mask >>> 0);
    this.#revision++;
  }

  addComponent(id: EntityId, type: number): void {
    this.setMask(id, (this.#masks.get(id) ?? 0) | (1 << type));
  }

  removeComponent(id: EntityId, type: number): void {
    this.setMask(id, (this.#masks.get(id) ?? 0) & ~(1 << type));
  }

  getMask(id: EntityId): number {
    return this.#masks.get(id) ?? 0;
  }

  #key(q: Query): string {
    return `${q.all}:${q.none}`;
  }

  /** 无缓存查询：每次从头扫描全部实体。遍历顺序 = 插入顺序（稳定）。 */
  queryUncached(q: Query): EntityId[] {
    const out: EntityId[] = [];
    for (const [id, mask] of this.#masks) {
      if (matches(mask, q)) out.push(id);
    }
    return out;
  }

  /**
   * 带缓存查询：revision 未变则直接返回上次结果（命中），
   * 变了则重扫一次并覆盖缓存（失效重建）。
   */
  query(q: Query): EntityId[] {
    const key = this.#key(q);
    const e = this.#cache.get(key);
    if (e !== undefined && e.revision === this.#revision) {
      this.#hits++;
      return e.entities;
    }
    this.#misses++;
    this.#rebuilds++;
    const entities = this.queryUncached(q);
    this.#cache.set(key, { entities, revision: this.#revision });
    return entities;
  }

  /** 需要一份可安全修改的拷贝时用它——缓存返回的是共享数组。 */
  queryCopy(q: Query): EntityId[] {
    return [...this.query(q)];
  }
}

// snippet: bench/query-cache-bench.ts（节选）
function runUncached(e: QueryEngine): number {
  const t0 = performance.now();
  for (let r = 0; r < ROUNDS; r++) {
    for (const q of QUERIES) sink += e.queryUncached(q).length;
  }
  return performance.now() - t0;
}

function runCachedStatic(e: QueryEngine): { ms: number; hits: number; rebuilds: number } {
  e.query(QUERIES[0]!); // 预热一次，让缓存填满
  for (const q of QUERIES) e.query(q);
  const t0 = performance.now();
  for (let r = 0; r < ROUNDS; r++) {
    for (const q of QUERIES) sink += e.query(q).length;
  }
  const ms = performance.now() - t0;
  const s = e.stats;
  return { ms, hits: s.hits, rebuilds: s.rebuilds };
}

N = 20000, TYPES = 8, QUERIES = 8, ROUNDS = 200
[A static] uncached  219.11 ms
[A static] cached    0.20 ms
[A static] speedup   1096.26x
[A static] hits = 1601, rebuilds = 8
[B churn ] cached    225.59 ms
[B churn ] hits = 0, rebuilds = 1600

// snippet: src/core/query-cache.test.ts（节选）
it('缓存命中：同一 revision 下第二次调用不重建', () => {
  const e = new QueryEngine();
  e.setMask(1, maskOf([0]));
  e.setMask(2, maskOf([0]));
  const q = makeQuery([0]);
  const a = e.query(q);
  const b = e.query(q);
  expect(b).toBe(a); // 返回同一数组引用
  expect(e.stats.hits).toBe(1);
  expect(e.stats.rebuilds).toBe(1);
});

it('失效重建：组件变更后结果更新', () => {
  const e = new QueryEngine();
  e.setMask(1, maskOf([0]));
  const q = makeQuery([0]);
  expect(e.query(q)).toEqual([1]);
  e.addComponent(2, 0);
  expect(e.query(q)).toEqual([1, 2]);
  expect(e.stats.rebuilds).toBe(2);
});