基于有向距离场(SDF)的地图碰撞系统 | Cocos技术派第15期

2020.5.27 技术干货 by Cocos

近日,ID 为 kx-dz 的开发者在 Cocos 中文社区分享了一篇名为《介绍一个基于有向距离场(SDF)的地图碰撞系统》的技术文章,获得诸多好评。C姐第一时间联系到了作者,在获得转载授权的同时,也对这则分享背后真实游戏项目《吃鸡联盟》制作人书生进行了专访。精彩内容,跟着C姐一起往下看吧!

《吃鸡联盟》游戏截图

受访者:书生

编辑:C姐

《吃鸡联盟》是由南京壹游网络科技有限公司基于 Cocos Creator 3D 研发的一款 IO 竞技小游戏。这支成立于2017年的团队,在经历了创业初期 H5 页游的失利和中期的迷茫时期后,如今坚定地选择了走小游戏开发路线,团队负责人笑称自己“是芸芸小开发者的真实缩影”。

目前团队共有4人,分别担任项目制作人书生(兼行政、商务、运营…..)、技术开发毛毛熊、美术设计啊翔和策划汤包五十六,“能者多劳”,作为公司负责人的书生很苦逼的对应了 N 个岗位。

《吃鸡联盟》立项于2020年3月,疫情期间,成员们就通过远程办公的方式不断寻找新的产品方向。团队之前的产品都是关卡制,受限于团队规模,关卡制的游戏又对内容的要求比较多,制作成本较高,此前的产品效果不是很理想。考虑到小游戏的特性、用户需求以及团队本身的能力,最终选择了 IO 类作为后期团队的主要研发方向。

3月初团队复工,产品立项,4月底完成了第一个版本,开发周期将近两个月。这是团队的第二款 3D 产品,也是第一款 IO 类产品,增加了 AI 来提高游戏可玩性,花费了相当多的时间在 AI 的研究上。

游戏融合了吃鸡+IO 元素,玩法很简单,拖动人物即可控制行走并发射道具,玩家可以通过灵活的走位来发射子弹攻击敌人,也可以通过掩体来躲避敌人攻击。拾取游戏内的紫钻可以提升等级,进而对技能进行解锁和升级,比如回复血量、提高攻击力、提高攻速、提高射程等,随着时间的推进,游戏地图会缩小,玩家必须移动至安全区域,否则就将丧生在毒圈中。

除了缩圈机制之外,《吃鸡联盟》区别于其他类型射击游戏的地方,还表现在子弹的速度上。大部分的射击游戏属于不对称攻击(闯关类的都是玩家射速高、怪物射速慢)和硬扛类(射速相同拼武器和血量),《吃鸡联盟》的子弹速度相对较慢,有比较多的可操作性,玩家可以通过操作躲避敌人的子弹,利用走位去攻击其他玩家,这样的机制更能让玩家体验操作的乐趣。

游戏中玩家与障碍物的碰撞检测便是采用的 SDF 技术,是怎么想到把 SDF 技术运用在这款游戏中的呢?

洪磊分享道,“目前团队主要发布的平台是微信小游戏,但是微信小游戏平台对于性能的压制还是比较严重的,尤其是苹果手机。在项目初期,团队有两个选择:一是基于物理引擎,二是使用 SDF 技术。这款游戏涉及到比较多寻路算法,而且模型较多,基于性能的考虑,我们尽量在其他的方面进行优化,所以选择使用 SDF 技术来实现碰撞检测。”

传统方案上,对于这种场景的设计,大家首先想到的肯定是物理引擎,通过设置建筑物和障碍物的碰撞体(Collider)来阻挡人物的行动。

在这种思路下,如果场景中的建筑物和人物比较多,会造成比较严重的性能问题,因为每一帧内对每一个人物和每一个障碍物都需要做碰撞检测,计算量是:N (人物) * M (障碍物)。再加上飞镖的碰撞检测计算量,在不支持 JIT 的 iOS 平台上可能会有不小的性能压力。当然,基于物理引擎的碰撞检测方式也有不少可以优化的点,比如说:

  • 使用简单的 Builtin Physics 替代 Cannon 物理后端
  • 通过场景管理剔除不在可视范围内的物体的碰撞计算
  • 简化 3D 碰撞检测为 2D 碰撞检测,简化盒子碰撞体为圆形碰撞体

但是这些优化的效率都远远不如《吃鸡联盟》中所应用的有向距离场碰撞系统。下面就来看看开发团队倾囊相授的基于 Cocos Creator 3D 如何实现这样一套场景碰撞检测系统吧!

原文作者:kx-dz

首先,大概实现的原理是通过插值计算得出任意点的有向距离数据,然后与单位的碰撞大小做比对,来检测单位是否可以通行。实例图如下:

如果你做的是类似于《王者荣耀》这样的伪 3D 游戏,只需要考虑平面位置因素,不需要考虑高度,不需要太精准的碰撞判定,并且地图元素固定不会变动,这套高效的、基于有向距离场(SDF)的地图碰撞系统可以参考使用。

1. 原理

将地图划分为 N*N 个格子,每个格子的四个角存储有距离数据,这些数据是每个角所在点到最近的障碍的距离。如下图:

深色格子不可通行,交叉点数字代表该点到最近的不可通行格子的距离(下文称“有向距离”)。

通过有向距离数据,我们可以通过计算差值的方式算出任意点到最近障碍的距离。

如图所示,在判断精灵是否可通行时,只要在精灵当前位置所在格子上的数据进行一次插值计算,即可判断是否可通行,非常高效。

2. 具体实现

既然这么棒,那么,要怎样获得这些数据呢?

2.1:栅格化地图数据

就是将地图划分为N*N个格子,每个格子标记为可通行/不可通行。当然,划分的格子越多,精度越高。

建议使用高度图来存储通行数据,高度图长这个样子:

这是一张 128*128 的图片,代表将地图划分出的 128*128 个格子。图片上每个像素点的颜色表示是否通行,黑色为障碍,白色为通行区域。

2.2:读取栅格数据

准备好图片后就需要读取像素信息了。

(关于原生url的获取,暂时没太好的方法,只有先load资源然后再获取nativeUrl值。如果有更好的方法请告知)

成功的话,你会获取到 imageData,格式差不多这样:

data 数据每 4 个一组,存储了一张图片上每个像素的 RGBA 值,顺序则是按照由左向右、由上往下的顺序(遵循 canvas 坐标系)。将颜色数据转换为二维的布尔数组,即为地图每个栅格的通行数据。

实现代码:

2.3:计算栅格四角的有向距离数据
(比较麻烦的一步。这里介绍一个笨办法,如果有更简单的办法,欢迎告知)
每个角(即栅格划分线的交叉点)都需要计算一次。如果你将地图划分成了N*N个栅格,那将有(N+1)*(N+1)个交叉点的有向距离数据需要计算。

对于每个交叉点:

首先要遍历所有的栅格。如果是不可通行的栅格,判断栅格和当前点的方位关系,决定用栅格的哪个角去计算到当前点的距离。

决定好了后,计算两点距离。所有不可通行的栅格都要和当前点计算距离,最后取它们的最小值,即为有向距离值。

差不多是这个意思

实现代码:

优化:

因为计算量高达 (N+1)(N+1)N*N 次,可能会消耗大量时间。经试验,一张网格尺寸为 128*128 的地图,在纯 H5 环境以及安卓的微信小游戏环境下,计算速度尚能接受,但是在 iOS 的微信小游戏环境下,计算时间高达 50s,这显然是不能接受的。

所以,推荐使用事先处理好数据,然后导出 json 文件的方式,游戏运行时直接读取现成的 json 文件即可。

这就是以内存空间换取速度的思想,也是 SDF 系统的核心思想。

2.4:使用 SDF 碰撞系统

分三步:
第一步:判断精灵当前位置属于哪个格子,这个很容易;
第二步:获取格子四个角的有向距离,并计算插值;

插值计算代码:

第三步:最后取得的数值表示精灵体积半径为多少时才能通过,否则判定为阻拦。

2.5:检测到碰撞后的处理

游戏中玩家使用摇杆控制角色时,如果撞到墙面了,肯定不可以让角色立刻停下来,那样的操作体验就很糟糕了。通常的做法是让角色沿着墙面滑行。

基于 SDF 的碰撞系统有一套处理这类情况的方式,即通过计算碰撞法线来得出玩家移动时碰到障碍后的正确方位。

计算碰撞法线方向的代码:

具体的处理碰撞的代码:

关于 SDF 的细节就不在这里向大家详细解读了,目前这方面的资料相对比较稀少,感兴趣的开发者朋友,可以参考《腾讯游戏开发精粹》这本书进行学习,此外,也可以多逛逛 Cocos 官方论坛,论坛上还是有很多有价值的学习资料可以挖掘的。

最后,要感谢 Cocos 团队在这一年多来给予我们的支持。由于 Cocos Creator 引擎的易用性,在19年做小游戏时,我们就把 Cocos Creator 作为首选引擎,后期推出了 3D 引擎,我们几乎没有花学习成本就成功完成了从 2D 到 3D 的团队转型。

在最开始使用 3D 引擎时,我们对于优化毫无经验,Cocos 给我们提供了很多很好的思路。特别是到了后期,产品开始一些跨渠道跨平台的运营时,关于各个渠道的平台差异所产生的分包问题以及参数配置问题,这些对于小开发者很不友好,没有经验的情况下,可能要花很长时间来应对这些问题,幸好我们跟 Cocos 团队有密切的沟通,这些问题都很快得到解决。


以上就是本期技术派的全部内容啦!非常感谢制作人书生接受 Cocos 的专访,也非常感谢《吃鸡联盟》团队慷慨的技术分享,希望游戏可以取得好成绩!

点击这里可进入社区原贴与作者交流,为作者点赞哟!也欢迎大家在微信中搜索体验这款小游戏。

技术派,是 Cocos 专为开发者打造了知识分享专栏,我们将不定期邀请知名的游戏制作者,为广大开发者分享来自真实项目的实用的开发技术和实战经验。欢迎大家推荐想要学习的游戏产品和想要了解的技术知识,也诚邀有技术分享意愿的开发者联系我们噢~

更多【技术派】文章

技术派01 |《野蛮人大作战》H5项目从开发到上线

技术派02 | Cocos Creator 2.0 摄像机的灵活运用

技术派03 |  推荐一款可查看节点树的插件

技术派04 | 3D 人物渲染详细教程

技术派05 | 实时竞技小游戏技术分享

技术派06 | Camera 摄像机详解

技术派07 | 重度小游戏《三国封魔传》技术实现方案

技术派08 | 3D 小游戏《飞跃地平线 Plus》开发分享

技术派09 | 畅销 SLG《乱世王者》深度优化方案

技术派10 | 3D小游戏《快上车》技术分享

技术派11 | 极限开发创作笔记

技术派12 | 竞技对抗小游戏《单挑篮球》开发历程 

技术派13 |3D《巅峰漂移》技术分享

技术派14 |腾讯光子《最强魔斗士》3D 开发经验