3D游戏里，角色和地图元素的碰撞一般由物理系统完成，但是不可避免会由此带来效率上的问题。
如果你做的是类似于《王者荣耀》这样的伪3D游戏，只需要考虑平面位置因素，不需要考虑高度，不需要太精准的碰撞判定，并且地图元素固定不会变动，那这里有一套高效的、基于有向距离场(SDF)的地图碰撞系统可供使用。
1. 原理
将地图划分为N*N个格子，每个格子的四个角存储有距离数据，这些数据是每个角所在点到最近的障碍的距离。例如下图：
深色格子不可通行，交叉点数字代表该点到最近的不可通行格子的距离（下文称“有向距离”）。
通过有向距离数据，我们可以通过计算差值的方式算出任意点到最近障碍的距离。
如图所示，在判断精灵是否可通行时，只要在精灵当前位置所在格子上的数据进行一次插值计算，并将结果与精灵碰撞半径作对比，即可判断是否可通行，非常的高效。
2. 具体实现
既然这么棒，那么要怎样获得这些数据呢？
2.1栅格化地图数据
就是将地图划分为N*N个格子，每个格子标记为可通行/不可通行。当然，划分的格子越多，精度越高。
建议使用高度图来存储通行数据。高度图长这个样子：
这是一张128128的图片，代表将地图划分出的128128个格子。图片上每个像素点的颜色表示是否通行，黑色为障碍，白色为通行区域。
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：计算栅格四角的有向距离数据
（比较麻烦的一步。这里介绍一个笨办法，如果有更简单的办法，欢迎告知）
每个角（即栅格划分线的交叉点）都需要计算一次。如果你将地图划分成了NN个栅格，那将有(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)NN次，可能会消耗大量时间。经试验，一张网格尺寸为128128的地图，在纯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();
}
}
3．最后的话
这篇文章就此告一段落。因为楼主水平有限，关于 SDF的一些细节就不向大家详细解读了，作为补充向大家推荐一下《腾讯游戏开发精粹》这本书。虽然我喷过它，但是它确实解决了我的问题，对SDF具体原理感兴趣的同学可以在里面找到解答（微信读书app上就有，不是托= =||）。
附上简单的Demo（基于v1.1）
sdfDemo.rar (769.5 KB)
=======================
6月6日更新
修复了里面的一个错误算法，增加了碰撞的稳定性
sdfDemo.zip (996.1 KB)
，有没有大佬讲解一下那个插值是怎么计算碰撞的