最近在做新引擎 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 个字节，这导致数据量很大。这里云风给出一个有损压缩方案用于压缩这些信息。