云风的 BLOG

寻路模块本身的实现是没有持久状态的，场景地图的障碍信息是独立出去的静态不变数据，全局共享，这是合理的设计。但是一个无状态的 pathfinding 对象却被实例化了很多份，供不同的服务独立使用。

一开始，我很奇怪，一个无状态的寻路函数，为什么需要保存一个全局对象。读了代码后发现，寻路算法的初始化过程需要初始化一大块内存。具体说来，是一个大约 200x200x16 的三维数组，每个单元大约有 16 字节。算法就是很基础的 A* pathfinding ，在这么个三维网格中寻路。需要以开始这个三维数组的内存为全零。大约是 10M 内存。在高频调用下，memset 10M 内存是不小的开销。

实现者为了节省初始化的时间，在每个格子中记录了一个 64bit 的版本号，每次寻路递增版本，使用这些格子时判断一下格子的版本号和当前版本号是否一致，以此为标准来判断这个格子在当前轮次是否有初始化过。

由于真正的寻路过程往往只使用这 10M 内存中的极少空间，所以节约了大量的初始化时间。但这需要全局保留块内存，不能每次寻路都重新构造这么一个对象。

我想了一下这个问题。它本质上的需求是一个 3d 稀疏矩阵。原本我们用一个 hash 表也可以做到，只需要用三个维度的索引连接起来做 key 即可。但是实现者认为这样可能会有不确定的性能问题，宁愿使用空间换时间的方式以巨大的平坦内存结构来让操作这个稀疏矩阵的时候可以以 O(1) 的代价访问。但是，就带来了这一大块内存每次使用的初始化问题。

表达空间的稀疏矩阵除了 hash 表，还有很多方法，比如 KD tree ，八叉树等等，但无论从实现复杂度和访问效率上恐怕都没有说服力。我想，既然服务器上没有空间开销问题，那么能不能从根本上实现一个惰性初始化的内存结构呢？

这里是我随手写的几行代码，我认为可以解决这个问题。

假设 cpu 的 cacheline 是 64 字节，字长是 64bit ，我想以 64 字节为单位去初始化内存是最有效的（把一个字节清零和把 64 字节清零速度是一样的）。那么，10M 内存就可以划分成大约 156K 个段落。我们可以用 1 bit 记录每个段是否有初始化，在访问内存前查看对应的标记位就可以决定是否应该先把对应段落清为零。

156K 个标记位大约需要 2400 个 64bit 的字，也就是将近 20K 的内存来保存。如果也不想初始化这 20K 内存的话（因为大部分格子不会访问到），那么可以依法炮制一个 2 级标记。这一级，我们把这 20K 内存分成 64 段，每段 300 字节左右。最终，我们就用一个 64bit 的字来控制它们的初始化。

最后，用 gcc 开 O2 优化看了下最终生成的汇编代码，感觉编译器优化的结果很好。

这个项目使用的地图高达 4000x4000x16 格。里面保存了网格状的障碍信息。而服务器这个寻路模块要解决的是 NPC 在地图中攻击附近的玩家时能够绕过障碍物的问题。

也就是说，这个寻路模块并不需要解决长距离寻路，要处理的也仅仅是绕开附近的障碍物。且障碍物是静态不变的。

这些场景并不是特别复杂的迷宫，障碍的拓扑结构很有限，所以这个巨大的障碍数组中的信息密度非常之低。我认为，既然花了这么大的空间代价去保存障碍信息，无非就是想让寻路算法简单高效。但其实，这么大的空间，已经足够把 "地图上每个点到附近不太远距离内的任意目标点的路径" 全部记录下来了。

只要经过预运算，用合适的数据结构储存，我们完全可以在 O(1) 时间查询出任意一条路径。具体怎么操作，我下篇 blog 再写。