最近一段时间，lua 的邮件列表中有好几个主题讨论 hash 表的设计。我读下来受益匪浅。比如 前两周的这个主题 中，有同学主张去掉 lua hash table 中的链表指针，而改成固定步长的冲突链表。具体这里就不展开了，有兴趣的同学可以自己看。
这两天的讨论是围绕 lua 的 hash 函数的，暂时还没有固定链接，我把我的理解和思考记录下来，不一定正确，如有行家发现错误，请不吝赐教。
unsigned int
luaS_hash (const char *str, size_t l, unsigned int seed, size_t step) {
unsigned int h = seed ^ cast_uint(l);
for (; l >= step; l -= step)
h ^= ((h<<5) + (h>>2) + cast_byte(str[l - 1]));
return h;
}
来看这样一个 hash 函数：
Lua 中的短字符串做了 string interning 的处理，即在同一个虚拟机内，值相同的字符串只存在一份。这可以极大的提高用字符串做 key 的 hash 表的查询速度。因为字符串比较的时间复杂度从 O(n) 下降到 O(1) ，比较查询的 key 和 hash 表内的 key 是否一致，只需要对比一下对象的指针是否相同即可。
我在解决多 Lua 虚拟机共享字符串对象这个问题时，合并了不同的 Lua 虚拟机中的短字符串表。让同一进程所有虚拟机共享一个短字符串表（ SSM ）。
我最初在实现 SSM 的时候，考虑到多虚拟机 GC 的复杂性，采用了只增不减的方案。即让部分短字符串进入 SSM ，设置一个上限，避免 SSM 无线膨胀。但 Lua 并没有把经过 interning 处理的字符串作为独立类型，目前只用字符串长度作为区分，也就是无法和不 interning 的短字符串共存。所以，那些已存在本地虚拟机短字符串表中的字符串，就不从 SSM 中获取对象。
修改过 Lua 的 string interning 算法是这样的：
查看字符串是否存在于本地字符串表 (LSM) 如果存在，就立刻返回。这一步和原版 Lua 一致。
查看字符串是否存在于 SSM ，如果存在，就返回。
检查是否 SSM 上限已到，如果不能再增加新字符串，把字符串添加到 LSM ，返回。
将字符串添加到 SSM ，返回。
昨天读了几篇文章，讲解了一种新的抗锯齿字体渲染的方法 。
我觉得颇有意思，就试着实现了一版 CPU 版本，想看看针对中文的效果。虽然最后觉得这个算法对游戏领域的实用性不大，不过还是挺有启发的。这里写写我对这个算法的理解，以及我所理解的算法局限性。
今天一个同事反应，在使用 recastnavigation 库时，判断一个点是否在一个三角形内，遇到了精度问题，而且精度误差很大。
具体是 dtClosestHeightPointTriangle 这个函数。
他给出了一组测试参数，abc 三点为 {261.137939, 8.13000488} , {73.6379318, 8.13000488}, {76.9379349, 10.2300053} ，测试 p 为 {74.4069519 , 8.6093819 } 应该在这个三角形内，但是这个函数计算出来并不是。
我为 3d engine 项目设计的向量运算库 已经用了一段时间了。在使用过程中也一直在改进 。从一开始，我就考虑过，这个库的设计主要考量是减少 lua 和 C 交互间的开销，提高内聚性。而易用性方面，计划再上面再做封装。这段时间继续在想怎样从更自然的表达形式转换到这个库的逆波兰指令流上。
大致的方向有两个：
其一，实现一个小语言，用字符串输入表达式组。
其二，利用 Lua 已有的语法解析设施，把 lua 的一个函数翻译成对应的数学运算指令流。
两者都可以看成是一种 jit 的过程，在第一次运行的时候，做一些翻译工作，把要进行的数学运算打包成 C 代码可以处理的指令流，或翻译成现有数学库支持的指令流；或者，增加一个 lua 源码的预处理流程，在预处理阶段做好编译工作（aot）。
这个需求可以分解成三个问题：
首先，如何把更易用的的源码对接到 lua 原生代码。
其次，如何转换为正确的数学运算指令流。
最后，为以上过程选择 jit 或 aot 集成。
最近在做新引擎 UI 模块的工作。汉字字体纹理需要占比较大的一张贴图，考虑到这张贴图只需要用一个通道就够了，所以我决定使用压缩贴图。在手机设备上，GL_COMPRESSED_R11_EAC 是一个不错的选择。
EAC 是 Ericsson 提出的对单通道贴图的压缩方案，现已进入 OpenGL 的官方标准。它通常会结合 ETC2 一起使用。ETC2 负责 RGB 部分，EAC 负责 Alpha 通道。偶尔也可以单独使用。它会将每个像素解码为 [0,2047] 的整数，有 11bits 的精度，故而被称为 R11_EAC 。不过，我阅读文档后发现，其实有效精度是 8 bits ，一般也是从 8bits 的原始数据中编码得到的。压缩后，每 4 * 4 = 16 个像素会被编码为 64 bits ，压缩比 2 : 1 。用于字体纹理的话，可以节省一半的显存空间。
因为图形引擎中的对象天然适合用树 (n-ary tree) 表达，所以它在图形引擎中被广泛使用。通常，子节点会继承父节点的一些状态，比如变换矩阵，在渲染或更新的时候，可以通过先序遍历逐级相乘。
在 PC 内存充裕的条件下，我们通常不必考虑树结构储存的开销，所以大多数图形引擎通常会为每个渲染对象独立生成一个树结构，比如 Unity 中的 GameObject 就是这么一个东西。在 Ejoy2D 中，从节约内存的角度考虑，把树节点上的一部分可共享的状态信息（不变的矩阵、纹理坐标等）移到了资源数据块中，但是树结构的拓扑关系还是在新创建出每个 sprite 时复制了一份。
随着游戏制作的工艺提高，而大众使用的移动设备的内存增长有限，这部分的开销慢慢变得显著。在我们正在开发的几个项目中，渲染对象本身，而不算图形资源（贴图、模型等），也占据了以 M 为单位计算的可用内存。比如在一个项目中，某个巨型对象由多达 2000+ 个节点构成，创建速度和内存开销都成为一个不可忽视的问题。由于是于自研引擎，所以同事尝试过一些优化的尝试。
图形引擎处理的大多数的树结构对象，其实仅在编辑环境会对树的拓扑关系进行调整：增加、移动、复制节点。而运行环境下，树结构本身几乎是不变的。一般的树结构的实现是用指针来相互引用，编辑好的资源是树结构的序列化结果，而创建过程是一个反序列化过程，在内存中重建整棵树，并用指针重新建立节点间的联系。比如在 Unity 中，就把这种编辑好的树对象叫做 prefab 预制件。如果预制件比较复杂，加载预制件和从预制件中构建对象的时间成本都不算低。
一个优化方法是去掉运行时内存中的指针，改用 id 或资源数据块中的偏移量，这样，预制件可以直接从资源文件中成块读入，创建内存对象时也只需要用指针引用即可。可以节省大量在内存中重建的时间。Ejoy2D 现在就是这么做的。去掉指针的额外好处是在 64 位系统下，可以从 8 字节的引用开销减少到 4 字节（或更少）。Ejoy2D 当初做此修改，为一个项目一举减少了 10M+ 的运行期内存占用。而且资源文件可以在暂时不用的时候移出内存，等需要的时候再加载回来，而不用担心数据的内存地址发生了变化。
这几天 AlphaGo 4:1 战胜了李世石，围棋积分网站 给了 AlphaGo 一个世界排名。在 3:1 的时候是世界第四，4:1 后上升到了世界第二。
我很好奇这个网站是如何给棋手打分的，便顺着链接指引翻了下 wikipedia 读了几篇 paper 。
下面是我的一些理解，由于我的数学基本功不太扎实，难免有错误，所以有兴趣的同学最好自己读论文 。
首先，如何定义等级分这个东西？
在一对一竞技类游戏中，假设规则是公平的，对战双方如果都能给出最优策略，那么胜负概率是完全均等的 50% 。如果我们假定冥冥之中存在一个绝对实力值，而实力高的人可以少犯错误，那么他就能以超过 50% 的概率战胜对手。
简化胜负结果背后复杂的过程，我们把全体选手按绝对实力值排名，排名靠前的选手对排名靠后的选手，胜率都是大于 50% 的。
由于实力强的人不一定对实力弱的人必胜，所以这个绝对实力值其实是一个概率相关数。胜率的高低可以看成是实力差异大小。根据若干比赛的结果，我们可以推算出代表实力值得后验概率。
比如有两个选手的实力为 A 和 B ，则 A 胜过 B 的概率就为 A / (A+B) 。（不考虑平局的情况）
有一组选手和足够的他们相互之间的比赛成绩的话，我们就可以根据 Bradley Terry 模型 推算出一组实力值，尽可能的符合他们之间的对战结果。
从周末开始, 我一直在忙一个想法。我希望给 skynet 中的 lua 服务定制一个内存分配器。
倒不是为了提升性能。如果可以单独为每个 lua vm 配置一个内存分配器，自己调用 mmap 映射虚拟内存，就可以为独立的服务制作快照了。这样可以随时 fork 出子进程，只保留关心的 vm 的内存快照。主要可以有三个用途：
可以在快照上做序列化，并把结果返还父进程。通常做序列化有一定的时间代价，如果想定期保存的话，这个代码很可能导致服务暂停。
可以利用快照监控检查泄露。定期做快照相比较，就能找到累积的对象。我曾经做过这样的工具 。
可以在镜像上对快照做一些调试工作而不会影响主进程。
skynet 中使用了一个 hash 表结构来保存服务和 32bit 数字地址的映射关系。
一个 skynet 的服务，其实是一个 C 对象。在有沙盒的系统中，尤其是并行构架，我们很少直接用 C 对象指针来标识一个 C 对象，而是采用数字 id 。用数字做 handle 可以让系统更健壮，更容易校验一个对象是否还有效，还可以减少悬空指针，多次释放对象等潜在问题。比如，操作系统为了把用户程序隔离在用户态，像文件对象就是用数字 id 的形式交给用户程序去用的。
和操作系统通常管理文件句柄的方式不同，skynet 尽量不复用曾经用过的 id 。这样，当你持有了一个已经不存在的 id ，不太会误当作某个新的对象。（操作系统的文件 handle 很容易造成这样的问题：你记住了一个文件，在别的流程中关闭了它，然后又打开了新文件，结果复用了过去的 handle ，导致你操作了错误的文件。很多年前，我就在自己的线上产品中碰到过这样的 bug 。）
但是，一旦尽量不复用 id 。用简单的数组来做映射就很难了。必须使用 hash 表来保证映射效率。在 skynet 中我是这样做的：
每次分配新的 id 时，首先递增上次分配出去的 id （允许回绕，但会跳过 0 。0 被当成无效 id ）。然后检查 hash 表中对应的 slot 是否有冲突，若有冲突就继续递增。如果 hash 表的池不够用了，则成倍扩大池，并将内部的数据重新 hash 一次。
这样虽然会浪费一些 id ，但是可以保证 hash 表类的 key 永远不发生碰撞，这样可以让查询速度最快。hash 表的实现也相对简单一些。
我觉得这样的一个数据结构有一定的通用性，今天花了一点时间把 skynet 的这个部分单独抽出来，当成一个独立开源项目重新写了一遍。有兴趣的同学可以在 github 上查看。
2d 游戏通常都用到很多图素，由于显卡硬件特性，我们又不会把单个图素放在独立贴图中。这样会导致渲染批次过多。在移动设备上，非常影响渲染效率。
所以，游戏运行时，这些图素一般都会合并在很少几张贴图上。要么采用离线合并的方式（利用 texture packer 这样的工具），或者在运行时使用装箱算法。
最近，朱光同学一直在为 ejoy2d 编写运行时合并图素的模块。今天我们讨论了一下他做的诸多尝试。
去赌场参观过的同学应该都见过那种押大小的骰子游戏。庄家投掷三枚骰子，把骰盅盖住，玩家可以押大或小。开盅后，如果发现三个数字之和大于等于 11 就算大，小于等于 10 就算小。如果你猜对了，庄家就 1 赔 1 算给你筹码；否则输掉筹码。另外，还可以以不同赔率压数字，或压三个相同。
为了保障庄家利益，三个相同的数字算不大不小。从概率上讲，这让长时间内庄家必胜。概率分析见这里。
如果把这个游戏搬到网络上如何呢？（注意：网上赌博在很多国家是被禁止的，这里只做技术分析而已）
如何让玩家相信庄家没有作弊，真的产生了随机的骰子呢？
这篇文章是在大半年前, 我们的手游 刚刚做预研的时候写给公司内部分享的。由于这个项目公司不希望在开发阶段对外暴露信息，所以文章也没有在 blog 贴出来。
现在游戏已经上线 就没有消息保密的需求了，我就可以把当初开发时写的一些东西逐步贴出来。
所谓类似 COC 这样的斜视角引擎，在英文社区中叫作 Isometric Tileset Engine。它在早期计算资源匮乏的年代用的很多，后来内存不是问题了后，就很少有人用了。由于没有 Z-Buffer ，这种引擎的绘制次序其实很讲究。比如下图：
/\
/ \
/ \
/ / /\
/\ / B / /C \
/A \ / / \ /
\ / / / \/
\/ / /
\ /
\ /
\/
最近抽时间在读 Milo Yip 翻译的《游戏引擎架构》。书还没有出版，我应邀给这个译本写序，所以先拿到了电子版，正在加紧读一遍。全书接近 800 页，我已经读了 600 页左右，希望这个周末可以抽时间读完。
这本书是由顽皮狗的主程之一 Jason Gregory 写的，内容很精彩，Milo Yip 翻译的也相当不错。有很多章节我读的很有共鸣，想先挑一点来写写。
由于作者的主要技术背景是 Console game 开发，而 Console 目前内存非常有限，且没有虚拟内存，对内存的管理和使用就非常苛刻。很多 PC 平台上几乎被忽视的问题到了 Console 平台上就需要仔细考虑了。我很有共鸣是因为 10 多年前在开发大话西游时，要求在 64M 内存上跑起来，同样写了好多内存管理相关的代码。
比如栈式内存管理，就是在堆上模拟一个栈，只管分配，然后记住一个标记点一起释放。
又比如双端分配器，自己管理一大块内存，根据需求不同从两端向中间分配，这个还可以配合上面的分配器一起工作。
把对象的生命期绑定在渲染帧上，在一帧渲染完后把当帧的临时内存全部释放；或者做的更复杂一点，做一个乒乓开关，临时内存可以保留到下一帧结束。呵呵，这些以前都写过。
04 年的时候在网易公司内部做个一个比赛，就是在一块固定大小的内存内实现自己的内存管理器。用我们从梦幻西游，以及大话西游的客户端中实际采集来的数据做比赛评分，分别按允许速度和碎片率打分。我自己虽然没有参赛，但当时也写过一份程序拿到了最高分 :) 当时比赛的前三名现在都是网易项目（或离职后是新公司的主程）的主程。
前两天阿楠同学想用链表实现一个消息队列，虽说是链表，但是没有从中间删除节点或添加节点的需求。只需要先压入的消息先处理。为了完成这个需求，最后实现了一个双向链表。
当然这个东西是用 Lua 写的，做一个双向链表也不算复杂。采用单向链表也可以做到，只需要多记录一个尾节点。不过今天想说的是，如果这个玩意在 C 里实现的话，其实只需要用一个指针的空间就可以搞定一个双向队列，可以从任意一头进出数据，可以以两个方向遍历，而实现需要的代码量却和单向链表类似。因为算法非常有趣，在 C 语言之外很少见到，知道并使用过的人也就不太多了。这就是所谓的 XOR Linked List 。
今天吃晚饭的时候想到，我需要一个定制的内存分配器。主要是为了解决 共享内存 中的字符串池的管理。
这个内存分配器需要是非入侵式的，即不在要分配的内存块中写 cookie 。
而我的需求中，需要被管理的内存块都是很规则的，成 2 的整数次幂的长度。buddy memory allocation 刚好适用。
算法很简单，就是每次把一个正内存块对半切分，一直切到需要的大小分配出去。回收的时候，如果跟它配对的块也是未被使用的，就合并成一个大的块。标准算法下，分配和释放的时间复杂度都是 O(log N) ，N 不会特别大。算法的优点是碎片率很小。而且很容易做成非入侵式的，不用在被管理的内存上保存 cookie 。只需要额外开辟一个二叉树记录内存使用状态即可。
我吃完饭简单 google 了一下，没有立刻找到满足我要求的现成代码。心里估算了一下，C 代码量应该在 200 行以下，我大概可以在 1 小时内写完。所以就毫不犹豫的实现了一份。
然后，自然是开源了。有兴趣的同学可以去 github 拿一份。这样就省得到再需要时再造轮子了。嘿嘿。
昨天读到了 Bitcoin 的中文介绍，觉得非常有意思。不过上面这篇文章解释的非常不靠谱，我花了一晚上去Bitcoin的官方网站 仔细研究了一下，总算理解了其原理。感觉非常有启发，尤其是对虚拟货币的流通和发行有许多借鉴意义。今天写这篇 Blog 理一下。
什么是货币呢？货币就是商品(包括服务)交换的媒介。现在我们通行的货币是由有信誉的银行发行的，基本上是由其信誉来担保的。只要用的人都认可，那么我们就可以用它来交易。货币有一定的保值特性，我把我的劳动/服务/所有的商品换成货币后，银行担保我在日后的某一天，我还可以用它交换会差不多等值的东西。这个保证的前提是，银行不会滥发新的货币以及大家都信任这一点。
数据结构的序列化是个很有用的东西。这几天在修改原来的资源管理模块，碰到从前做的几个数据文件解析的子模块，改得很烦，就重新思考序列化的方案了。
Java 和 .Net 等，由于有完整的数据元信息，语言便提供了完善的序列化解决方案。C++ 对此在语言设计上有所缺陷，所以并没有特别好的，被所有人接受的方案。
现存的 C++ serialization 方案多类似于 MFC 在二十年前的做法。而后，boost 提供了一个看起来更完备的方案（ boost.serialization ）。所谓更完备，我指的是非侵入。 boost 的解决方案用起来感觉更现代，看起来更漂亮。给人一种“不需要修改已有的 C++ 代码，就能把本不支持 serialize 的类加上这个特性”的心理快感。换句话说， 就是这件事情我能做的，至于真正做的事情会碰到什么，那就不得而知了。
好吧，老实说，我不喜欢用大量苦力（或是高智慧的结晶？）堆积起来的代码。不管是别人出的力，还是我自己出的。另外，我希望有一个 C 的解决方案，而不是 C++ 的。
所以从昨天开始，就抽了点时间来搞定这件事。
去年写过几篇过于 AOI 模块的设计。将 AOI 服务独立出来的设计早就确定，并且一定程度上得到了其他项目组的认可。（在公司内部交流中，已经有几个项目打算做此改进）
最近一段时间，我在这方面做进一步的工作。（主要是实现上的）
首先，基于 KISS 的考虑，删除了原有协议中的一些不必要的细节。比如，不再通知 AOI 模块，对象的移动速度。移动速度虽然对优化很有意义，但毕竟是一冗余数据。考虑这些，容易掉入提前优化的陷阱。
其次，增加了一条设置默认关心区域的协议。这是出于实用性考虑。
几年前我曾经写过一篇 blog 介绍我发明的一种高度图压缩算法 。最近几天，我将这个算法用于目前正在开发的 engine ，如之前所料，效果不错。由于数据被压缩，更改善了资源加载的速度。并在同等内存条件下，让用户得到更高的体验。（这是因为，现代操作系统，都会把暂时不用的物理内存全部用于磁盘缓存，更小的文件体积同时意味着在同等内存条件下能缓存更多的数据）
因为我们需要做动态地形数据的加载，所以地形高度数据也被切割成了一小块一小块。采用这个算法后带来的一个问题是：由于压缩有数据损失，两个相临块之间不能严丝合缝的衔接在一起。
为了解决这个问题，这两天想了好几个方法。
曾经看过这样一种赌徒的策略：假设在一场赌大小的赌博游戏中，赔率是 1:1 ，而庄家不会出千，开大和开小的概率均等（皆为 50%）。赌徒一开始压一块钱，如果他压错了，那么下一次就压两块，再错继续加倍。一旦压对，赌徒永远可以保证有一块钱的进帐。并且从 1 块钱重新开始。
看起来，这种策略能保证永远包赚不赔。但实际上为什么没有人用这个方案发财呢？
放到现实中，试图采用这个策略去赌博的人，几乎都会赔的倾家荡产（当然只要是赌博，差不多都是这个结局）。不要怪运气，不要怪庄家出千，因为这个策略从一开始就注定了失败。
今天从 svn 中取下一个同事的代码，浏览了一下。其中一段是关于洗牌的。感觉实现的很乱，算法也没有选好。自己重新写了一个。
因为国庆的缘故，负责这块代码的同事提前回家了。我只好自己读代码实现。看完后，发现旧的实现是这样的：对于 N 张牌，每次随机抽出一张来，检查这张牌是否抽过。如果被抽取过，就重复抽取过程，直到不重复。然后记录下抽取的牌的位置。重复这个过程，直到得到一个随机序列。最后用这个序列将原始排列打乱。
这个方案给我的第一感觉并不好，因为当 N 较大时，最后需要重复抽取多次才可以成功。我估算了整个的时间复杂度大约是 O(N^2)
当然，洗牌这件事情可以有许多算法来解决。我重新写了一个，采用了最简单实现的方案。
缘起：听天下组的同事谈起，游戏的资源数据量太大，导致了加载时间过长，影响到了操作感。最终不得不对数据进行压缩。
当玩家配置的物理内存足够大时，往往资源数据压缩会适得其反。因为多出来的数据解压缩的过程会占用掉太多的 CPU 时间。物理内存够大的话，操作系统会尽量的拿出物理内存做磁盘 IO 的 cache ，即使你的程序不占用太多的逻辑内存，而反复从硬盘加载大块数据，也不会感觉到磁盘速度的影响。当数据量大一个一个临界时，被迫做不断的外存内存的数据交换，这个时候，数据压缩就会体现出优势。因为解压缩的 CPU 时间消耗是远远小于硬盘 IO 所消耗的时间的。
btw, 玩现在的 MMORPG 往往配置更大的物理内存得到的性能提升，比升级 CPU 或显卡要划算的多，就是源于这个道理。通常 MMORPG 都需要配置海量的资源数据，来应付玩家的个性化需求。
天下组的同事暂时只做了骨骼动作信息的压缩。这个这里暂且不谈，我想写写关于模型顶点数据的压缩。记录下这两天在思考的一个有损压缩算法。
估计是因为我在上大学时在网上留过一篇文章，里面有一个简单的使用 A* 算法寻路的源程序，导致了这近七年来，不段的收到 email 和我讨论这个算法。
对，毫不夸张。那个简陋的代码。在七年前我随手写出来扔在网上后，已经遍布中文网络世界的犄角旮旯，让我在痛恨那段代码的时候，想收回都不可能。
我最大的困惑在于，为什么课堂上最为基础的算法知识，却有如此多的人行入误区。难道写游戏的程序员都不去读读基本的课本？
A* ，读作 A-Star 。它仅仅是一个启发式搜索算法。就是说在一个可以被穷举的有限解空间集中，用比较有效的方法（主要是利用估价函数）求出最优解的算法。A* 跟寻路算法没有太多关系，我们只是借助了这个方法来解决寻路这个问题，正如四则运算对于数学题一样，它只是一个基本工具。寻路算法本身有很多种，我们找到算法后，借助 A* 这个工具实现这个算法而已。
3d游戏中的室外场景通常用高度图来表示，用一个二维数组来描述对应平面坐标的高度信息。
如果每个高度信息用一个 byte 来表示，很多情况下不太够用。因为对于很大的场景， 256 级的高度是远远不够的。通常我们会选择用 word 或者 float 来表示。
相比较而言，float 最为合适。这样，我们不太需要考虑缩放因子这个问题。但是 float 需要 4 个字节，这导致数据量很大。这里云风给出一个有损压缩方案用于压缩这些信息。