moyuta

兴趣管理的连接预算：可见实体不等于可发送实体

· 3 分钟阅读 · 1295 字

大世界战斗服在同一 Tick 内可能看见首领、玩家、投射物与普通 NPC。把空间查询结果直接序列化，会让最拥挤的连接决定服务器出口峰值。本文把“可见”限定为候选资格，把“可发送”限定为连接预算内的确定性裁决：

// .tmp/daily-labs/2026-07-30-2000/interest-budget.js
export class InterestBudget {
  constructor(bytesPerTick) {
    if (!Number.isInteger(bytesPerTick) || bytesPerTick <= 0) {
      throw new RangeError("bytesPerTick must be a positive integer");
    }
    this.bytesPerTick = bytesPerTick;
  }

  select(observer, entities) {
    const candidates = entities.map((entity) => {
      if (!Number.isInteger(entity.bytes) || entity.bytes <= 0) {
        throw new RangeError(`invalid byte cost: ${entity.id}`);
      }
      const dx = entity.x - observer.x;
      const dy = entity.y - observer.y;
      return { ...entity, distance2: dx * dx + dy * dy };
    }).filter((entity) => entity.distance2 <= observer.radius ** 2);

兴趣管理从空间范围进入连接预算的主视觉

所有权边界

空间索引拥有位置到候选集合的映射；连接发送器拥有 bytesPerTick、排序和延后集合；实体仍拥有自身快照及编码成本。两个不变量由此成立：空间命中不能绕过连接预算，单 Tick 已用字节不能超过硬上限。预算器不修改实体，也不把延后解释为不可见，因此下一 Tick 可以重新裁决。

输入 固定值
观察点与半径 (0, 0), r=10
连接预算 152 B/tick
输入实体 5
空间候选 4

稳定裁决

候选按优先级降序、距离平方升序、实体 ID 升序排列。最后一个键不是业务优先级，而是在前两项相等时消除容器遍历顺序差异。装不下的对象进入 deferred，但不能阻塞后面更小的对象；否则一个 80 字节对象会浪费仍可容纳 16 字节状态的尾部空间。

// .tmp/daily-labs/2026-07-30-2000/interest-budget.js
    candidates.sort((left, right) => {
      const stableIdOrder = left.id < right.id ? -1 : left.id > right.id ? 1 : 0;
      return right.priority - left.priority ||
        left.distance2 - right.distance2 ||
        stableIdOrder;
    });

    let usedBytes = 0;
    const selected = [];
    const deferred = [];
    for (const entity of candidates) {
      if (usedBytes + entity.bytes <= this.bytesPerTick) {
        usedBytes += entity.bytes;
        selected.push(entity.id);
      } else {
        deferred.push(entity.id);
      }
    }
    return {
      selected,
      deferred,
      visible: candidates.length,
      usedBytes,
      remainingBytes: this.bytesPerTick - usedBytes,
    };
  }
}

固定实体成本在 152 字节预算内的裁决结果

失败语义

非法编码成本若在循环中途才被发现，调用方可能已经拿到部分包并误以为裁决成功。实现先映射和验证全部实体，再排序装包；任一 bytes <= 0 都让本次调用整体抛错。恢复路径是丢弃该 Tick 的候选结果、记录实体 ID，并由上游修复编码元数据，不能用零成本继续发送。

// .tmp/daily-labs/2026-07-30-2000/interest-budget.test.js
test("defers a large entity without blocking a later fitting entity", () => {
  const input = [
    { id: "large", x: 1, y: 0, priority: 100, bytes: 80 },
    { id: "medium", x: 2, y: 0, priority: 90, bytes: 56 },
    { id: "small", x: 3, y: 0, priority: 10, bytes: 16 },
  ];
  const result = new InterestBudget(96).select(observer, input);
  assert.deepEqual(result.selected, ["large", "small"]);
  assert.deepEqual(result.deferred, ["medium"]);
  assert.equal(result.usedBytes, 96);
});

test("rejects invalid byte cost before producing a partial packet", () => {
  const invalid = [
    { id: "valid", x: 1, y: 0, priority: 1, bytes: 16 },
    { id: "broken", x: 2, y: 0, priority: 2, bytes: 0 },
  ];
  assert.throws(
    () => new InterestBudget(96).select(observer, invalid),
    /invalid byte cost: broken/
  );
});

运行证据

固定输入中，半径外的 far-loot 不进入预算竞争；预算器依次选中 72、48、32 字节的三个实体，恰好使用 152 字节，40 字节的 npc 延后。正常时序是空间筛选、稳定排序、预算装包、提交结果；失败时序在排序前终止，不产生可提交结果。

$ cd $WORK_DIR/.tmp/daily-labs/2026-07-30-2000
$ npm test && npm run probe
✔ packs visible entities by priority within one connection budget
✔ defers a large entity without blocking a later fitting entity
✔ rejects invalid byte cost before producing a partial packet
tests 3
pass 3
fail 0
skipped 0
duration_ms 169.511
exit_code 0
{"budgetBytes":152,"inputEntities":5,"selected":["boss","player",
"projectile"],"deferred":["npc"],"visible":4,"usedBytes":152,
"remainingBytes":0}

容量边界

当前实现对每个连接的 V 个可见候选排序，时间复杂度为 O(V log V)，额外空间为 O(V)；本文没有吞吐实测，因此不声称性能提升。直接按距离截断看似简单，却会让近处低价值装饰挤掉远处首领状态；只按优先级又可能长期饿死普通实体。当前取舍是硬预算优先，饥饿问题留给 age 加权或保底配额，但这些策略仍不得突破字节上限。

当单连接候选持续增长，或大量连接重复扫描同一区域时，应先共享空间桶与候选缓存；只有延后队列的年龄分布持续恶化时，才引入跨 Tick 公平调度。无论如何演进，空间系统只交付候选，连接始终拥有最终字节裁决权。

架构结论

兴趣管理不是“距离内就发送”的布尔过滤器，而是空间资格与传输容量之间的两阶段合同。把硬预算放在连接边界，才能让每条连接独立承受拥挤；稳定排序保证相同输入得到相同选择；预验证保证错误不会泄漏部分包。下一阶段若增加公平性，应扩展排序权重，而不是把预算所有权退回空间索引。

相关阅读