短 ID hash 映射的问题

今天解决了一个问题，觉得很有趣。本来想发到推特，发现一两句话说不清。所以写一篇 blog 记录一下。

我们正在开发的游戏中，会用一个 id 来表示一个游戏对象到底是什么。比如，“铁片” 是 1 ，“煤” 是 2 ，“采矿机” 是 3 …… 这样，在运行时，C 代码可以根据对象的类型方便的查询对象的属性。而对象的属性则是用 Lua 配置好，在运行期不变的。例如每燃烧一个单位的“煤”，可以产生 100KJ 的热量；一箱“铁片”有 100 个。

为了在 C 和 Lua 间快速共享这些配置数据，我还专门写了一个 cache 模块 。

问题出在 ID 的持久化上。因为游戏中的物品种类并不是特别多，出于时间以及空间性能的考量，我把 ID 设计为 16bits 。64K 种物品种类的上限看起来足够了。但 ID 的分配却比较麻烦。

最简单的做法是，在程序运行时，用一个自增 ID 分配给每个物品类型。但这会导致 ID 极不稳定，考虑到 ID 需要持久化，在开发过程中，持久化的存档也变得很不稳定。所以我选择了用物品的名称以及一些内在的参数（例如版本号）一起计算 hash 值当作 ID 使用。

但 16bits 的 ID 显然会发生 hash 冲突，所以最终还是结合了一个自增算法为每种物品赋予 ID 。这个方法在很长时间相安无事。大多数小版本更新都没有破坏老版本的存档，偶尔的版本更迭导致存档失效也是可以接受的。我们开发人力有限，暂时也没有把游戏版本升级同时升级存档数据这个机制的开发优先级列得很高。

但最近开发迭代周期变短，游戏可以玩的时长也越来越长。即使是开发测试，游戏存档失效后需要从头玩起，也变得越来越影响开发了。所以今天我们又重新审视这个问题。导致存档失效大大部分原因都在于新的版本（因为新增或删除修改了老物品）重新排列了物品类别的 ID ，导致旧存档中持久化的 ID 相关信息过期。

我和同事讨论了几种最容易想到的解决方案：

1. 改成人工指定 ID 。这个方案更为传统，我参于的很多游戏都是这么做的。所谓由策划配表，由人来保证尽量不要变更过去的映射表。

2. 把 ID 位数增长，变为 32bits 甚至 64/128 bits 。只用 hash 来生成 ID 。

3. 把存档数据升级机制纳入日程。加载老存档时，先预处理一遍数据，修正过期的 ID 。

方案一快速被否决了。我们项目没有全职策划。唯一一个挂策划名头的同事还要兼任 UI 制作、测试、项目管理等多项工作。而且我们的游戏类型决定了这个表会相当庞大，很多部分也不只是策划一人来决定的，具体实现的程序也会经常增加或删除其中的类型。人力维护一个稳定的映射关系不现实。

方案二的问题在于，从长期看，完全避免 hash 冲突可能需要 128bits ID 。这可能造成较大的性能浪费。而较短的 ID ，例如 32bits ，依然需要一个中心机构来记录历史上我们曾经使用的 ID 。这个中心机构维护起来并不轻松。尤其在我们现在的快速迭代阶段也不显示。

方案三看起来只是把未来要做的事情提前了。但做起来并不容易。现在的存档缺少不少元信息用来做新旧版本过度。这些信息或许以后还是要补上的，工作量却不小。我还是倾向于等版本再稳定一点时考虑具体方案。即便是像 Factorio Stellaris 这样已经迭代了好多年，单局游戏时间很长，有着存档升级机制的游戏。它们也没有做到可以从任意老版本的存档升级到最新版本。

最后的解决方案出人意料的简单。

我们在存档中额外放了一份 ID 映射表：记录每个 ID 具体是什么东西，也就是用来 hash 生成 ID 的那些元素：名称、成分、版本号等等。

虽然我们在 16bits 内无法避免 hash 冲突，但我们可以延迟生成 id 的时机。也就是说，程序在构造每种物品时，并不为它们生成 ID 。而是在加载存档时，根据这张表，动态绑定 ID 。如果存档中有 “铁片” 这种物品，标记为 42 ，那么在加载存档后，内存中的“铁片”这种物品的属性表中才赋予它 42 这个 id 。

而存档中不存在，但系统中已经创建出来的物品类型，再按 hash 算法生成独有的 id 。

​Read More