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

作者:CocosEngine
2020-06-02
7 6 1

团队介绍

《吃鸡联盟》是由南京壹游网络科技有限公司基于 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 值。如果有更好的方法请告知)


//获取指定图片文件的像素数据。返回 Promise
//path 写到文件名就行,不需要加 spriteFrame 和后缀
loadImagePixelData(path:string){
    var self = this
    return new Promise((resolve,reject)=>{
        loader.loadRes(path+"/spriteFrame",SpriteFrame,(err,res)=>{
            if(err){
                console.error(err)
                return reject();
            }
            var spriteFrame = <SpriteFrame>res;
            var rect = spriteFrame.rect;
            var img = new Image();
            img.src = spriteFrame.texture.image.nativeUrl;
            // console.log(spriteFrame._image.nativeUrl);
            // console.log(spriteFrame._image.url);
            img.onload=()=>{                
                self.context.drawImage(img,0,0,rect.width,rect.height);
                var imageData = self.context.getImageData(0,0,rect.width,rect.height);
                resolve(imageData);
            }
            img.onerror=()=>{
                reject("Error:load img failed!Path="+path);
            }
        })
    });
}
}

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

{    data: [0,0,0,255,0,0,0,255,…],    height:128,    width:128}

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

实现代码:

//高度图数据转化为地图通行数据
//imgData 格式:{data:Uint8ClampedArray,width:number,height:number}imgData2PassData(imgData:any){
    var data = imgData.data;
    var result = [];
    var width = imgData.width;
    var height = imgData.height;
    if(data.length<width*height*4){
        console.error("Error:图片数据长度不足!")
        return [];
    }
    var count = 0;
    for(var y=0;y<height;y++){
        var arr = [];
        for(var x=0;x<width;x++){
            var r = data[count];
            var g = data[count+1];
            var b = data[count+2];
            arr.push(r>128&&g>128&&b>128);
            count+=4;
        }
        result.push(arr);
    }
    return result;
}


2.3:计算栅格四角的有向距离数据

(比较麻烦的一步。这里介绍一个笨办法,如果有更简单的办法,欢迎告知)

每个角(即栅格划分线的交叉点)都需要计算一次。如果你将地图划分成了 N*N 个栅格,那将有(N+1)*(N+1)个交叉点的有向距离数据需要计算。

对于每个交叉点:

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

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


差不多是这个意思

实现代码:

//存储通行数据,这一步上面做过了
private _blocks=[]
//用来存储有向距离数据
private _distances=[];
initSdfSys(){
    var gridCountH = 128;
    var gridCountV = t128;
    this._distances=[];
    for(let i=0;i<gridCountV+1;i++){
        let dataArr = [];
        for(let j=0;j<gridCountH+1;j++){
            var value=0;
            dataArr.push(value);
        }
        this._distances.push(dataArr);
    }
    this.refreshData();        
}
private refreshData(){
    for(let y=0;y<this._distances.length;y++){
        for(let x=0;x<this._distances[y].length;x++){
            this._distances[y][x] = this._checkDis(x,y);
        }
    }
}
//距离检测
private _checkDis(vertX:number,vertY:number):number{
    var result;
    for(let y=0;y<this._blocks.length;y++){
        for(let x=0;x<this._blocks[y].length;x++){
            if(this._blocks[y][x]){
                let dis;
                if(y>=vertY&&x>=vertX){
                    dis = Math.floor(this.gridSize*(Math.sqrt(Math.pow(y-vertY,2)+Math.pow(x-vertX,2))));
                }
                else if(y<vertY&&x>=vertX){
                    dis = Math.floor(this.gridSize*(Math.sqrt(Math.pow(y-vertY+1,2)+Math.pow(x-vertX,2))));
                }
                else if(y>=vertY&&x<vertX){
                    dis = Math.floor(this.gridSize*(Math.sqrt(Math.pow(y-vertY,2)+Math.pow(x-vertX+1,2))));
                }
                else if(y<vertY&&x<vertX){
                    dis = Math.floor(this.gridSize*(Math.sqrt(Math.pow(y-vertY+1,2)+Math.pow(x-vertX+1,2))));
                }
                if(isNaN(result)||dis<result) result=dis;
            }
        }
    }
    return result||0;
}

优化:

因为计算量高达 (N+1)(N+1)N*N 次,可能会消耗大量时间。经试验,一张网格尺寸为 128*128 的地图,在纯 H5 环境以及安卓的微信小游戏环境下,计算速度尚能接受,但是在 iOS 的微信小游戏环境下,计算时间高达 50s,这显然是不能接受的。所以,推荐使用事先处理好数据,然后导出 json 文件的方式,游戏运行时直接读取现成的 json 文件即可。这就是以内存空间换取速度的思想,也是 SDF 系统的核心思想。


2.4:使用 SDF 碰撞系统

分三步:

第一步:判断精灵当前位置属于哪个格子,这个很容易;

第二步:获取格子四个角的有向距离,并计算插值;

插值计算代码:

calPointDis(pos:Vec3){
    var gridLen = 32;
    var gridPos = this.nodePos2GridPos(pos);
    if(this._block[gridPos.y]&& this._block[gridPos.y][gridPos.x]) return 0;
    var posZero = this.vertexPos2NodePos(gridPos.x,gridPos.y);
    var parmX = (pos.x-posZero.x)/gridLen;
    var parmY = (pos.z-posZero.z)/gridLen;
    var dis_lt = this._distances[gridPos.y+1][gridPos.x];
    var dis_ld = this._distances[gridPos.y][gridPos.x];
    var dis_rt = this._distances[gridPos.y+1][gridPos.x+1];
    var dis_rd = this._distances[gridPos.y][gridPos.x+1];
    var dis = (1-parmX)*(1-parmY)*dis_ld+parmX*(1-parmY)*dis_rd+(1-parmX)*parmY*dis_lt+parmX*parmY*dis_rt;
    return dis;
}

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


2.5:检测到碰撞后的处理

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

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

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

calGradient(pos:Vec3):Vec3{
    var delta=0.1;
    var dis0 = this.calPointDis(new Vec3(pos.x+delta,0,pos.z));
    var dis1 = this.calPointDis(new Vec3(pos.x-delta,0,pos.z));
    var dis2 = this.calPointDis(new Vec3(pos.x,0,pos.z+delta));
    var dis3 = this.calPointDis(new Vec3(pos.x,0,pos.z-delta));
    var result = new Vec3(dis0-dis1,0,dis2-dis3).multiplyScalar(0.5);
    return result.normalize();
}

具体的处理碰撞的代码:

update (deltaTime: number) {
    if(this._isControlledByJoystick&&this._speedRatio>0){
        var curPos = this.node.position.clone();
        var moveDis_dt = this.curSpeed*deltaTime;
        var newPos = curPos.clone().add(this.dir.clone().multiplyScalar(moveDis_dt));
        var sd = this.ground.calPointDis(newPos);
        if(sd<this.collideRaduis){
            //console.log("sd=",sd);
            var gradient = this.ground.calGradient(newPos);
            var adjustDir = this.dir.clone().subtract(gradient.clone().multiplyScalar(Vec3.dot(gradient,this.dir)))
            //console.log(StringUtils.format("dir=%s,gradient=%s,adjustDir=%s",this.dir,gradient,adjustDir));
            newPos = curPos.clone().add(adjustDir.normalize().multiplyScalar(moveDis_dt));
            for(var i=0;i<3;i++){
                sd = this.ground.calPointDis(newPos);
                if(sd>=this.collideRaduis) break;
                newPos.add(this.ground.calGradient(newPos.clone()).multiplyScalar(this.collideRaduis-sd));
            }
            // sd = this.ground.calPointDis(newPos);
            // if(sd<this.collideRaduis){
            //     newPos.add(this.ground.calGradient(newPos.clone()).multiplyScalar(this.collideRaduis-sd));
            // }
            //避免往返
            if(Vec3.dot(newPos.clone().subtract(curPos),this.dir.clone())<0){
                newPos = curPos;
            }
        }
        this.node.setPosition(newPos);
        this.onMove();
    }
}

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

最后,要感谢 Cocos 团队在这一年多来给予我们的支持。由于 Cocos Creator 引擎的易用性,在 19 年做小游戏时,我们就把 Cocos Creator 作为首选引擎,后期推出了 3D 引擎,我们几乎没有花学习成本就成功完成了从 2D 到 3D 的团队转型。在最开始使用 3D 引擎时,我们对于优化毫无经验,Cocos 给我们提供了很多很好的思路。特别是到了后期,产品开始一些跨渠道跨平台的运营时,关于各个渠道的平台差异所产生的分包问题以及参数配置问题,这些对于小开发者很不友好,没有经验的情况下,可能要花很长时间来应对这些问题,幸好我们跟 Cocos 团队有密切的沟通,这些问题都很快得到解决。


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

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