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游戏。
Posted by: Anonymous | (16) February 10, 2014 07:49 PM
作者,您真的使用上面说的做法应用到你们游戏中了?我感觉好天真啊。。
Posted by: Anonymous | (15) February 10, 2014 07:43 PM
非常标准的Dijkstra最短路径算法的一个应用
Posted by: Zealot | (14) January 23, 2014 03:00 PM
没有更新了么?
Posted by: yanx | (13) January 20, 2014 09:51 AM
大哥,你不光编程犀利,我看你去演乔峰也是相当的合适呢!
Posted by: frr | (12) January 16, 2014 04:35 PM
实现的过程发现应该是所有建筑一个类型的寻路一个路图
Posted by: yanx8844 | (11) January 14, 2014 09:04 PM
很有意思,解决了我很多的困惑。对与diaosi.hu的问题,
应该是一个建筑对应一个类型的寻路一个路图。coc后期也就60-90的建筑数量,用2个字节存储一个点40*40*2*90也就是600K左右的内存占用。多几种兵种寻路,也不会太大。不知道这么说有没有错。
Posted by: yanx8844 | (10) January 13, 2014 11:17 AM
您好,用skynet作为开发后台,在linux下开发编译调试,请问在调试C和LUA的时候是如何的,是直接GDB吗?对于开发过程中的单步调试和运行的工作方式是怎样进行?谢谢!
Posted by: Anonymous | (9) January 13, 2014 09:53 AM
假如说近战类士兵,地图上有6个金矿,6个油矿,是不是要生成6+6等于12个路图?因为建筑可以随便摆,士兵也可以随便投放,每个格子到不同建筑的难度也都是各不相同的.
这样有N个建筑,就要相对某类兵种生成N张路图.
Posted by: diaosi.hu | (8) January 13, 2014 12:07 AM
假如说近战类士兵,地图上有6个金矿,6个油矿,是不是要生成6+6等于12个路图?因为建筑可以随便摆,士兵也可以随便投放,每个格子到不同建筑的难度也都是各不相同的.
这样有N个建筑,就要相对某类兵种生成N张路图.
Posted by: diaosi.hu | (7) January 13, 2014 12:07 AM
你好,你的意思是每个建筑都生成一张“记录地图上所有格子到它的距离”的表么
Posted by: xq | (6) January 12, 2014 10:37 PM
你好,你的意思是每个建筑都生成一张“记录地图上所有格子到它的距离”的表么
Posted by: xq | (5) January 12, 2014 10:37 PM
好文,希望多些这样的分享.思路是最重要的.不过看得出写这文章很累人,建议图文并茂更好
Posted by: gamefan | (4) January 12, 2014 05:04 PM
楼下外挂作者取经来了
Posted by: 星 | (3) January 12, 2014 04:20 PM
可以接受下客户端和服务器端的计算逻辑是怎么划分的吗,哪些是在客户端做的,哪些是在服务器端做的,怎么防作弊的
Posted by: lee | (2) January 12, 2014 03:10 PM
话说现在手游的一大普遍的弱项就是手机wifi太稳定了。手机wifi稳定性比笔记本,差太多了。
Posted by: starshine | (1) January 12, 2014 02:44 PM