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

近日，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值。如果有更好的方法请告知）

//获取指定图片文件的像素数据。返回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 专为开发者打造了知识分享专栏，我们将不定期邀请知名的游戏制作者，为广大开发者分享来自真实项目的实用的开发技术和实战经验。欢迎大家推荐想要学习的游戏产品和想要了解的技术知识，也诚邀有技术分享意愿的开发者联系我们噢~

更多【技术派】文章

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

记得点亮星标哟！

点个“在看”再走呗