我需要一个接口简单的寻路模块，所以今天写了一个 。其实之前也写过很多版本，在我上传代码时就发现我自己的 github 账号下早有同名仓库。不过，之前的版本的接口设计不太满意，直接删掉了，用这次的新版本复用老的仓库名字。
我希望达到的目标是，C 接口简单易用，且和地图本身的数据结构无关，只提供寻路功能。这样容易拓展到不同应用场景。
数据结构简单，内存开销固定，在算法执行过程中不额外分配内存。这可以方便的在多线程环境运行。
我不需要处理特别复杂和规模巨大的地图，那种场景应该额外做一些预处理。但在起点和终点的路线结果不长时（即使在大规模地图上），应该有较好的性能。
我倾向于在 C 程序里使用整数 handle ，而不是指针。尤其是需要做弱引用的时候。
我认为，一个好的 handle 生成算法，应该满足：
这两天在改 log 模块。我们需要一个并发写 log 的模块，它有多个 log 生产者一个消费者，这个唯一的消费者在 log 线程中把 log 数据持久化。
大多数 log 生产者是在第三方库的 callback 函数中调用的，比如 bgfx ，如果写 log 不够快的话，就会阻塞渲染。这个 callback 需要自己保证线程安全。因为 bgfx 支持多线程渲染，所以写 log 的 callback 可能在不同的线程触发。
过去在实现 bgfx 的 luabinding 时，我实现了一个简单的 mpsc 队列，get_log 这个函数就是那个单一消费者，它取出队列中所有的 log 信息，返回到 lua 虚拟机中。
它是用 spin_lock 实现的。这两天，我想应该可以实现一个更通用的无锁版本。
我们游戏 UI 基于 RmlUI 的 fork，做了大量的改造。它实际上类似目前的 web 前端技术，使用 CSS 来表示 UI 的布局。所以，我们做的底层工作也都是围绕如何高效实现一套基于 CSS 的 UI 引擎来做的。
一年多前，我写过一篇 blog 介绍了一些优化的工作。
最近，在游戏开发的使用中，我们又发现了一些性能热点，最近在着手优化。这一篇 blog 记录一下其中的一个优化点。
在我们的 ecs 模块中，有一个重要的内部数据结构是 eid 的数组。它是 Component 结构的一部分，表示每个 Component 属于哪个 Entity 。目前，它是以一个有序的 id 数组实现的。
这个数据结构常见的操作分别是：遍历、随机访问、查找 id 所在的位置。一个有序数组可以很好的完成任务。O(1) 的随机访问时间，O(Log N) 的查找时间。
我们的 Entity ID 是 48bit 的，我觉得保存 48 或 64bit 的 id 数组有点浪费，且空间越大，实际操作效率也会相应降低。实际上，Entity 的个数不会太多，我觉得限制在 2^24 (一千六百万左右）足够了，所以用了一个间接索引，保存 24bit id ，再用它去索引真正的 entity id 。
最近 AI 很火。我从读书的时候就对 AI 有兴趣，90 年代的时候读过一本关于神经网络的书。但当时没有能力完全理解。2000 年初刚毕业那会儿想搞明白点，又研究过一段时间。了解了很多相关知识，感觉自己弄明白了，但却没有真正动手实践过。
现在，所有人都看得到，AI 已经变成了一个可以真正帮助我们提高生产力的工具了。我觉得有必要好好学习一下。我并不期望几篇文章就可以搞清楚，那样只会让自己好像懂了，和人聊天估计够用，想理解它还是得自己动手。真正写几段代码，才有触碰的感觉，明白别人到底在解决什么问题。
一开始，我是从维基百科的 Machine learning 开始读的。顺着看了一整天，了解了近年发展的脉络。好多词条，乱七八糟的笔记记了一大堆，感觉快消化不了了。疑问也积累了很多，觉得看下去效率会越来越低。不如换一条路。
然后我开始读 Neural Networks and Deep Learning 这本书。读了两章后，我想，手写数字识别看起来是一个非常好的实践手段，不如自己写一遍最快。有这么一个基础，后面可以继续修修补补，沿着前人的轨迹走一下，可以更好的理解为什么。
绝大部分的基础数据结构都是定长的，很容易针对优化它们的内存管理。但字符串是一个例外。
内存管理和其它资源管理有明显的不同。管理内存有点像切蛋糕，从整块蛋糕上切下需要的那块，但归还的时候却因为支离破碎难以合并起来满足后续用途。举个极端的例子：如果内存堆有 2G 大小，如果碰巧在正中间分配了几个字节而从未释放，这个堆就被永久的分成了两个不足 1G 的分片。之后再无可能从这个 2G 大小的堆中分配出 1G 的内存块。
改进内存分配算法或许可以减轻内存碎片的危害，但即使是在此方面做了相当多努力的 jemalloc ，其表现也大大低于一般用户的预期。以我的经验，一个 16G 的内存堆，对于长期运行，需要大量反复分配释放内存的程序，通常能做到 10G 左右的峰值有效内存占用就不错了。这里说的有效内存使用，指你调用 malloc 传入的字节数之和。根据应用程序使用内存的方式不同，这个数字会有很大的不同。
60% 的内存使用率其实已经很好了，但还是会有很多人问，我的内存都去哪了？
我们的游戏引擎的 GameUI 使用的 RmlUI 。我的想法是用成熟的 CSS 来描述 UI 的呈现，借鉴 web 前端开发的方法来制作游戏的 UI 。
但我不想嵌入太复杂的 Web 渲染引擎，而且游戏的需求也会有所不同，所以我选择了轻量的 RmlUI 。同时，为了和游戏的开发语言一致，我们使用 Lua 而不是 javascript 来控制 CSS 。
在使用 RmlUI 的过程中，一开始我们尽量和上游保持一致，修复了不少 Bug ，并合并到了上游。后来发现我们有很多需求和上游不同，需要大刀阔斧的做一些改动，所以就 fork 了一个自己的分支。
最重要的两个改动是：第一，完全实现了 Lua Binding ，因为原有的实现非常低效和复杂，很多接口设计不合理。做大规模的接口变化必须破坏向前兼容，这是我们 fork 分支的主要动机。
第二，废弃了 RmlUI 自己实现的排版模块，换成了 Facebook 维护的 Yoga 。
我们引擎中使用的数学库已经修修补补很久了。期间积累了很多想法。最近在对引擎做性能优化，把一些找到的热点系统用 C/C++ 改写，顺便就重构了一下数学库，让它更好的兼顾 Lua API 和 C API 。
上一次对数学库的改进是三年前的事情了。这三年的使用，我们发现，基于一个栈的 DSL 虽然可以减轻 Lua 和 C 之间的通讯成本，但是使用起来并不方便。大部分时候，我们还是倾向更传统的接口：一次数学运算调用一次函数。而高复杂度的数学运算完全可以放在独立的 C 模块中完成。结合 ECS 系统，我们可以在 C side 集中批量处理相同但数量巨大的数学运算。
我们在很早以前就放弃了原来设计的 DSL ，只使用数学库的部分功能。趁这次重构，我打算把这些已经废弃的部分彻底删掉，并重新设计底层的数据结构，让它能更好的适应其核心特性。
目前，我们用 ECS 管理游戏引擎中的对象。当游戏场景大到一定程度，就需要有一个机制来快速筛选出需要渲染的对象子集。换句话说，如果你创建了 100K 个 Entity ，但是只有 1K 个 Entity 需要同时渲染，虽然遍历所有可渲染对象的成本最小是 O(n) ，但这个 n 是 100K 这个数量级，还是 1K 这个数量级，区别还是很大的。
我们的 ECS 系统已经支持了 tag 这个特性，可以利用 visible tag 做主 key 快速筛选可见对象。但当镜头移动时，需要重置这些 tag 又可能有性能问题。重置这些 visible tags 怎样才能避免在 100K 这个数量级的 O(n) 复杂度下工作？
今天在扩展我们游戏中的管道系统时，又遇到了实现一个无向图的问题。
之前的管道系统，每节管道的邻接管数量有限，所以我用了类似树的方式储存，在每节管道上直接放了一个固定大小的数组，保存该节管道的上下游节点。对于液体管道系统，这套数据结构工作的很好。
今天，我们的另一个系统需要一个有点不一样的管道。它没有方向，每个节点可以有很多的邻接点。例如电线拉成的网络、导热管构成的网络，都是这样的。这是典型的无向图结构。
我重新考虑了数据结构，用邻接表实现了一版。
今年 1024 程序员节公司搞活动，让我做一次分享。我在分享会上谈及程序优化时，说道优化算法减少时间复杂度的优化往往比优化代码本身更优化。举的一个例子就是检测一个整数是否是素数的问题。
米勒拉宾素数检验法比普通方法有数量级上的性能提高。当时我说道，这个算法的原理其实并不复杂，其证明过程有高中数学知识就可以理解，并不需要多深奥的数学知识。
会后，有同学提出了疑问。他怀疑一个高中生真的能看懂 wikipedia 上的解释 。仔细读了一遍后，我认为，对于中学生来说，难懂的可能只是其中的一些专有术语罢了，那些中学数学课本上没有引入。其内核还是挺好懂的。而且，这篇中文版写的（以及排版）不太好，远没有英文版清晰 。或许只要看英文版就立刻明白了。
我也许可以写一篇没那么多术语，但也不够严谨的解释。
在最近实现的 ECS 库中，Tag 是一种非常重要的数据结构。它是一类特殊的 Component ，不携带数据，但会关联到同一 Entity ，最重要的用途是用于筛选。我在设计 Comonent 的数据结构时，采用了一种简单的数据结构 。它采用连续内存储存的数组，按 Entity id 有序排列。并在查询算法上做了一些优化，可以使得大部分查询时间小于 Log(N)，接近常量时间。
但是，这样做的代价是插入和删除操作都是 O(n) 的。为了避免大量的插入删除操作堆积在一起时，整体的时间复杂度变成 O(n^2) ，我禁止 Component 的删除，而删除 Entity 改为标记，待一帧结束后一起删除。这样，可以让批量删除保持在 O(n) 的复杂度。
我想用 C 实现一个内存紧凑的 ECS 框架，希望数据结构足够的简单，且能管理海量的对象。所以我让每个 component 就是一个不包含任何引用的 struct ，并带有一个 32bit 的 id 。并把这样的一个数据结构放在一块连续内存中。
这个 id 没有对外暴露的 API （不是 entity id ），可以在运行过程中调整。如果两个不同类型的 component 有相同的 id ，即认为它们同属一个 entity 。id 的作用是管理 component 的生命期，以及在遍历 component 时，可以找到同个 entity 上其它的组件。
对于我的应用场合来说，最多的操作是遍历单类 component 的集合。这种操作在这个数据结构下特别简单，就是 for 循环遍历一个简单的数组。但有些系统会需要在处理一个 component 时，找到它归属的 entity 上的兄弟组件。由于我不想用额外的内存建立这些 component 间的联系，所以这个开销就会特别大。如果不做任何优化，查找是 O(n) 的，n 为组件的数量。这显然不能接受。
第一步优化，我让组件在组件集数组中保持有序，按 id 排序。id 本身在分配的时候是单调递增的，所以只要 32bit id 不回绕就能一直保持有序。一旦回绕，我们重排一下即可。对于有序的数组，用二分查找可以减少到 O(log N) 的时间复杂度。
如果 N 特别大（十万以上）时，还是比较慢的。那么，有没有可能对二分查找做进一步优化呢？我做了一点尝试。
上次谈到服务器上寻路算法的优化。文末提到，其实，针对具体需求，我们实际上可以预运算所有的路径，把结果持久化在文件中，运行时用 O(1) 的时间就可以查询到任意路径。
对于半径为 N 的地图网格，选取任意两点作为起点和终点，一共有 N^4 数量级的路径，直接按起点和终点来缓存路径显然不现实。
但实际上，除非整张地图是个复杂的迷宫，大部分路径是重复的。这和人实际上行路是一样的。如果你从家中的卧室去到办公室的工位上，整条路径和你从客厅出发是高度重叠的；仅有出家门前的那一小段略有不同。
在服务器上寻路，通常解决的是 NPC 的小范围内移动绕开障碍（从卧室到家门）的问题，远距离移动的路线（从家到公司）应当在另一个层面去解决。
基于网格寻路无论是用 A star 还是基于图的 dijkstra 算法都非常简单，这里不谈算法，只谈结果的持久化问题。
为了解决起点和终点有 N^2 种可能性，这个数量级太大的问题，我们可以适当的将地图划分成若干区域。如果每个区域都是一个内部没有任何障碍物的凸多边形，那么，当我们的起点和终点都落在同一个区域时，连接两点的直线就是最短路径。
最近一段时间，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 个字节，这导致数据量很大。这里云风给出一个有损压缩方案用于压缩这些信息。