云风的 BLOG: COC Like 游戏中的寻路算法

同样是一篇老文章, 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 的原版算法是怎样的。

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

Comments

云风大哥，本人因喜欢coc所以在学习unity（初学）的时候尝试模仿coc来做，但遇到很多问题，所以来这里取经。为了方便我是直接拿3D来做的2.5D效果（没考虑性能问题的前提）。寻路是我自己写的A*（C#写的，每次寻路都消耗上百k的内存40*40的地图（导致频繁的GC），而且时间会消耗0-8ms，并非像留言说的200各地面单位都无压力的情况（当然不排除我写的A*还不够好）），这样一来单位多的话帧率很低。看了云风大哥所提到的路图预算，我有个疑问，关于说到的"如果下一个行军路线是城墙就攻打城墙"，那么远距离单位有办法在很远的距离就攻打城墙吗？（为了简单测试，我还去试完了云风大哥的游戏，发现弓箭手总是在打完附近建筑在挨着城墙的位置打城墙（不知是不是因为阵型和城墙的权值太高的原因））。

Posted by: TonyTang | (22) February 2, 2016 02:27 PM

个人认为是带权值的A*寻路算法。

Posted by: grass | (21) January 21, 2015 06:26 PM

非常好奇，如果有些士兵会跳墙或者某个建筑被摧毁了之类的操作，会不会影响路径的缓存。如果被影响到了，那是不是还要把所有的建筑刷新一个缓存？

Posted by: ht | (20) December 26, 2014 04:04 PM

我只想来安静的凑个热闹，《海岛奇兵的获取即计算算法》： http://blog.sina.com.cn/s/blog_5e6fd4290102vczo.html

Posted by: paladin_t | (19) November 13, 2014 10:17 PM

其实实时寻路的花费的时间也非常低，我们实测下来200个地面单位也只花费几毫秒，类A星算法在这么小的范围内的寻路压力很小，没太大必要做预处理，贵公司的大作仔细研究过，做的不错，还原度比较高，不过我们的也不赖，我们的即将上线，已通过审核，期待市场上较量一番.

Posted by: Anonymous | (18) February 19, 2014 11:51 PM

大神，如果可以把一些后台制作的方式或者具体的实现也写一下啊！

Posted by: terry8210 | (17) February 13, 2014 09:42 AM

暂时没有发现能达到COC技术水平50%以上的类COC游戏。