云风的 BLOG

同样是一篇老文章, 2013 年初我刚玩 COC 的时候写给公司内部分享的。由于当时公司还没有决定开手游项目，但有意向做一款 COC Like 的产品，并希望开发期间保密，所以相关技术文章都没有公开。

目前，我们的游戏上线，就可以把当初写的东西陆续贴到 blog 上了。

COC 的地图有 40x40 格，边界还有两格不可以放建筑的格子。所以整个地图是 44x44 格的。但在做坐标判定时，基于格子是远远不够的。COC 官方版本很可能是基于像素级的精度的，和本文所述方法不一致，所以本文仅提出一种可行的数据结构，

地图至少要基于网格顶点来建立坐标系统。每个格子由中心点以及四角为顶点，一共有 9 个坐标点。也就是说，最小单位是半个格子。坐标系是 [0,88]

下面的示意图是一个格子，以及 9 个坐标点：

+--+--+
|  |  |
+--+--+
|  |  |
+--+--+

关于建筑，除了表面上看到的占据格子的面积外，还有实际的尺寸。

比如矿，空间上占 3x3 个格子，但实体则可能是这样的：

..+++..
.+###+.
+#####+
+#####+
+#####+
.+###+.
..+++..

也就是说，对于一个 3x3 的建筑来说，它占据了 9 个坐标点 # 。当步兵攻击它的时候，需要站在周围的一圈坐标 + 上。实体不是方的，可以让兵围起来的时候大致成一个八边形，而不是方形。

对于 2x2 的建筑，则是这样的：

..+..
.+#+.
+###+
.+#+.
..+..

像营地这样的 5x5 建筑，建筑实际占地和 3x3 一样，步兵看起来是靠近攻击的。步兵在攻击的时候，必须坐标轴对齐毗邻建筑，但是播放攻击动画是朝向建筑中心的。

关于寻路：

COC 不同于 RTS ，它基本上是运动的单位寻路去攻击静止建筑。（部队交火例外，这个先撇开不谈）地形在破坏之前，大体上路线其实大体上是固定的。而建筑也有限。加上地图规模不大，这让寻路模块也有了极大的优化空间。

我认为预处理可以极大的简化计算。

我们可以针对每类建筑设置一张寻路图。以 3x3 的普通建筑为例：

2100012
10###01
0#####0
0#####0
0#####0
10###01
2100012

这里的 0,1,2 只是到建筑的实际距离。我们只需要做一次全地图填充，就可以写入地图上所有坐标点到建筑的最短距离。陆军在移动时，只需要找到周围 8 个坐标中距离建筑更近的一个，移动过去即可。如果距离为 0 就可以展开进攻。注意，斜向移动并不会更快。

对于不同攻击距离的单位，可以分别生成不同的图表。这样，弓箭手就会在刚好在射程最远处就展开进攻了。

关于墙：

墙不是建筑，除了炸弹骷髅，所有兵种都不以墙为寻路目的地。所以墙不需要生成上面的图（炸弹骷髅的移动逻辑另做）。

墙对于寻路系统来说，只是一个权值很高的障碍（可以跳跃后则忽略）。比如，一个 3x3 建筑围了墙后该怎么计算呢？（如下图，我故意留了两个口）。

####.
#ooo#
#ooo#
#ooo#
##.##

展现为坐标点是这样的。# 表示建筑，X 表示墙，. 表示路。

...........
.XXXXXXX...
.X.........
.X..###..X.
.X.#####.X.
.X.#####.X.
.X.#####.X.
.X..###..X.
.X.......X.
.XXX...XXX.
...........

如果我们认为通过墙的难度是 6 (就是说，拆墙好过走 6 个格子。实际设置的值肯定比 6 大) ，那么按同样的方法标注前面的图就好了。

ba987765456
a9876667345
98210001234
8710###0165
760#####066
760#####067
760#####067
8710###0178
88210001288
79871117897
65432223456

如果在行军路线上，下一个目标点是墙，那么就先攻击墙就可以了。

总结一下，其实我们只需要为每类兵种，针对它所偏好攻击的建筑群生成一张路图，标记了一个士兵在地图任何位置所需要做的动作：是向某个方向移动？还是站在原地开始攻击。那么士兵每到任何一个新坐标，他都可以通过查表 O(1) 时间得到要做的事情。

只有地形破坏后，路图才需要重新计算。计算的时间复杂度是 O(n) 的，只跟地图尺寸有关。我的试验代码可以在毫秒级完成重算。

ps. COC 应该不是采用这样的算法这可能和他们采用的地图数据结构有关，因为它的士兵 AI 有明显的迟钝，大约 6 秒才会重算一次。但我认为上面的算法更优不必追究 COC 的原版算法是怎样的。

对于炸弹人的逻辑，大致应该是寻找附近封闭空间中最近目标，炸毁路径上的障碍。详细算法另开一篇。

Posted by 云风 at 02:14 PM | Permalink | Comments (22)

这篇文章是在大半年前, 我们的手游 刚刚做预研的时候写给公司内部分享的。由于这个项目公司不希望在开发阶段对外暴露信息，所以文章也没有在 blog 贴出来。

现在游戏已经上线 就没有消息保密的需求了，我就可以把当初开发时写的一些东西逐步贴出来。

所谓类似 COC 这样的斜视角引擎，在英文社区中叫作 Isometric Tileset Engine。它在早期计算资源匮乏的年代用的很多，后来内存不是问题了后，就很少有人用了。由于没有 Z-Buffer ，这种引擎的绘制次序其实很讲究。比如下图：

            /\
           /  \
          /    \
         /     / /\
  /\    /  B  / /C \
 /A \  /     /  \  /
 \  / /     /    \/
  \/ /     /
     \    /
      \  /
       \/

如果 A B C 三个菱形标识了三个物件的基座块的话，它们的正确绘制次序是怎样的呢？

在没有 Z-Buffer 的支持时，我们需要利用画家算法从后向前绘制。那么就是先画 A 再画 B ，最后画 C 。（我们设想一下 A B C 都有一定高度，那么 B 会挡住 A ，C 会挡住 B 。

那么，A 和 C 之间，是不是一定是先 A 再 C 呢？答案是不一定，这取决于 B 的摆放。比如 A C 位置不变，而 B 是这个样子：

        /\  
       /  \    
      /    \    
     /      \    /\
  /\ \    B  \  /C \
 /A \ \       \ \  /
 \  /  \       \ \/
  \/    \      /
         \    /
          \  /
           \/

就需要先画 C 再画 B ，最后画 A 了。

也就是说，两个物件的绘制次序，单靠每个物件自己的空间坐标来排序是不够的。

（Ps. 如果所有物件都是正方形则不会出现这种情况，按对称中心排序即可。）

那应该怎样做呢？事实上，在 Isometric Tileset Engine 中，任意两个物件的绘制次序有三种状态：A 在 B 的前面，A 在 B 的后面；A 和 B 无关。

每个基座为菱形的物件 A，它向上都可以延伸出一个扇面，在这个扇面之类的物件都必须在它之前绘制。

\............../
 \....扇面..../
  \........../
   \......../
    \../\../
     \/A \/
      \  /
       \/

如果两个物件 A 和 B ，A 不在 B 的扇面内，B 也不在 A 的扇面内，就认为 A 和 B 无关。

一个简单的方法是，利用所有物件之间的关系做一次冒泡排序。一遍扫描出一个物件，它在所有物件之前，或是跟其它物件无关，把它放在第一位绘制；然后依次处理剩下的物件即可。

这个方法很好理解，但是时间复杂度偏高。

另一种方法不需要排序，但是实现略微复杂一些。为了好描述，我把地图旋转 45 度，变成正方形的方便解说。假如有如下场景。

             +-+
      +---+  |C|
      | B |  +-+
 +-+  |   |   
 |A|  +---+  
 +-+

如果我们顺时针旋转 45 度就和第一张图类似了。我们需要按 A B C 的次序绘制。

现在从第一行开始从左到右扫描，直到碰到第一个东西 C ：

 ----------> +-+
      +---+  |C|
      | B |  +-+
 +-+  |   |   
 |A|  +---+  
 +-+

检查 C 的左边是否全部被触碰过，如果没有，就把 C 压入一个临时堆栈，然后另起一行重复前面的过程。但不要扫描已扫描过的区域。

如果 C 的左边全部被触碰过，则可以绘制 C ，然后从 C 的右边继续这个过程。

 ............+-+
 .... +---+  |C|
 ---> | B |  +-+
 +-+  |   |   
 |A|  +---+  
 +-+

按照这个规则，我们会发现 A 最先被处理掉，然后是 B 最后是 C 。因为 B 的下半部分被 A 挡住，所以 A 不处理完之前， B 一定在堆栈中。

这个堆栈的最大深度不会超过总行数。而扫描永远是从左向右的，只需要一个和行数相同的数组就可以保存下已经扫描过的位置。这个算法的时间复杂度以及空间复杂度都是 O(n) 的。我大约用了 60 行 C 代码实现了这个过程。

看完这个绘制过程，就知道，如果需要把场景正确的出来，需要知道地图上有哪些东西，它们是什么，它们在哪里，它们有多大。其它的信息是不必要的。

所以，我为这个需求设计了一个简单的数据结构，服务于绘制流程以及后面会提到的生成寻路图。

管理绘制次序只有一个 API ，就是从一个坐标取下一个需要绘制的对象所在的坐标。这个 API 所需要用到的数据，只要是一个 2D 数组，数组上的每个元素可以表明所在位置的建筑的尺寸就可以了。

Posted by 云风 at 04:47 PM | Permalink | Comments (16)

我们公司的第一个手游：陌陌争霸终于上线了。

苹果审核比我们预计的快了两天, 所以原定 10 号上线的, 今天就开始了。

有兴趣的同学可以玩一下。客户端基于前几天开源的 ejoy2d ，服务器使用的是我们开源项目 skynet 。

iOS 版：http://itunes.apple.com/cn/app/id765375025?ls=1&mt=8

Andriod 版：http://game.immomo.com/download/mmzb.apk

由于这个产品是为传说中的交友神器 陌陌 开发的，所以必须有陌陌账号登陆（最初设计时是不需要注册登陆的）。

Posted by 云风 at 07:23 PM | Permalink | Comments (41)

最近我们的手游上线， 一开始稳定的跑了好几天，最近两天开始平均 30 小时崩溃一次。这个周末我们一直在查这个 bug 。

第一次崩溃发生在周六凌晨 1:00 左右，没有收集到 core 文件，只有事故现场的寄存器的值(通过查看 kern.log 和 dmesg )。通过 EIP 寄存器最终定位到是在内存分配器中出的错。

我们用的 jemalloc ，崩溃发生在一段红黑树插入节点的代码中。 这里的 pathp 指针变成了 NULL 。

昨天在岩馆攀岩的时候，我脑子里一直在转这段代码，想为什么这个局部变量会变成 NULL 。反复推测的结果是 path 这个局部数组越界了，导致把 pathp 改写。

这段代码是用来展开一颗红黑树的，如果树的数据结构正常，128 一定够用，不会越界。比较可能的解释是插入了相同的节点，导致树结构绕接。虽然 jemalloc 在这里加了 assert ，但似乎在最终的程序中没有生效。

我推测是在内存释放的时候调整红黑树的，虽然我们的崩溃没有产生 core 文件，但从网上搜索到另一条类似的信息可以佐证我的推测：这条 bug report 报告了一个类似的崩溃。从调用栈来看，的确是在内存释放时发生的。

我的第一次推测是我们有些代码对指针做了 double free ，导致了红黑树节点绕接，间接导致后续的 free 操作不正常，让树展开代码越界。如果这个推测成立，那么即使我们拿到完整的 core 文件，对我们 debug 也没有什么帮助。因为数据结构是事先被破坏掉，才会导致后面的操作出错。

今天上午 10 点左右发生了第二次崩溃。这次收集到了 core 文件。

这次的错误点和上一次相同，但现象有所不同，并没有访问 NULL 地址。double free 的猜测应该是不成立的。但和我的推测相同，core 文件中可以看到调用栈的确是从 free 过来的，其它信息则没有什么用。数据结构早就被破坏了，事故现场是一次正常的 lua state 关闭操作（引发大量内存回收）。

但可以肯定的是这起 bug 最近连发两次，每次间隔都是 30 小时左右，一定是最近代码的修改造成的。我们翻看了最近的修改。对 C 代码的修改只有一两个位置，之前反复看了好几次都没有发现问题。不得以再看一次。

最后终于发现了问题，是一个简单的内存越界造成的：

我们上周发现有玩家客户端发过来的数据包解包失败，但不知道原因，所以增加了一个函数把错误的数据包以 16 进制输出到 log 的函数。晓靖同学是这样写的：

  char *buffer = calloc(sz*2+1, sizeof(char));

先分配一块内存，长度是要 dump 的数据长度两倍加一。然后循环

  sprintf(buffer+i*2, "%02x", data[i]);

这就是我们看了几次没留意的 bug 所在：data 是 const char 类型，有符号的。当 data[i] 是一个负数时， %02x 不一定只输出 3 个字节(别忘记字符串结尾的 \0)。buffer 这块内存就被写越界了。

Posted by 云风 at 04:28 PM | Permalink | Comments (38)