《球球大作战》源码解析（6）：碰撞处理

作者：罗培羽 2019-03-20

系列文章
《球球大作战》源码解析——(1)运行起来
《球球大作战》源码解析：服务器与客户端架构
《球球大作战》源码解析：移动算法
《球球大作战》源码解析（6）：碰撞处理
《球球大作战》源码解析（7）：游戏循环
《球球大作战》源码解析（8）：消息广播

小球移动过程中，可能会碰到食物、其他玩家和病毒，如果碰到食物，则吞食食物，质量增加；如果碰到其他玩家，体积大的吃掉体积小的，如果吞食病毒，分身解体。tickPlayer中有一段遍历所有cell的代码，它处理了游戏中的碰撞事件。

for(var z=0; z<currentPlayer.cells.length; z++) {
……
}

复制代码

代码中定义了一个SAT.Circle类型的playerCircle，它指的是以currentCell.x和currentCell.y为圆心，currentCell.radius为半径的圆。后续将会用这个圆形去和场景中的物体做碰撞检测。

var V = SAT.Vector; //一开始定义
var C = SAT.Circle;
var playerCircle = new C(
new V(currentCell.x, currentCell.y),
currentCell.radius
);

复制代码

吞食食物

吞食食物的代码如下所示，foodEaten表示被吃掉的食物列表，程序对food列表的所有食物执行funcFood方法，即是使用 SAT.pointInCircle看看食物是不是被包含在玩家的面积之内。然后再对每个foodEaten执行deleteFood方法，即删除掉这个食物。food.map(funcFood)表示对food数组的每个元素传递给指定的函数，并返回一个数组，该数组由函数的返回值构成。funcFood返回的是玩家是否吞食了食物，形成true/false的列表。reduce() 方法接收一个函数作为累加器，数组中的每个值（从左到右）开始缩减，最终为一个值，是ES5中新增的一个数组逐项处理方法。针对map(funcFood)返回的true/false列表，如果该食物被包含（为true），则将它添加到返回值中。

var foodEaten = food.map(funcFood)
.reduce( function(a, b, c) { return b ? a.concat(c) : a; }, []);
foodEaten.forEach(deleteFood);
function funcFood(f) {
return SAT.pointInCircle(new V(f.x, f.y), playerCircle);
}
function deleteFood(f) {
food[f] = {};
food.splice(f, 1);
}

复制代码

看到这里作者还是比较失望的，因为本来期待有更好的方法，减少计算量。像这样两两判断谁不会啊！

吞食massFood

massFood是玩家喷射出的“质量”处理过程与吞食食物类似，获取被吃掉的mass的列表massEaten，然后从massFood列表中删掉它。

var massEaten = massFood.map(eatMass)
.reduce(function(a, b, c) {return b ? a.concat(c) : a; }, []);
……
var masaGanada = 0;
for(var m=0; m<massEaten.length; m++) {
masaGanada += massFood[massEaten[m]].masa;
massFood[massEaten[m]] = {};
massFood.splice(massEaten[m],1);
for(var n=0; n<massEaten.length; n++) {
if(massEaten[m] < massEaten[n]) {
massEaten[n]--;
}
}
}

复制代码

吞食病毒

如果不小心吞食了病毒，玩家会被迫分身，代码如下所示。

var virusCollision = virus.map(funcFood)
.reduce( function(a, b, c) { return b ? a.concat(c) : a; }, []);
if(virusCollision > 0 && currentCell.mass > virus[virusCollision].mass) {
sockets[currentPlayer.id].emit('virusSplit', z);
}

复制代码

下图为吞食病毒导致的分身前后，绿色圆形为病毒，大球aa吞食病毒后，立即分解为两个小球。

增加质量

如果玩家吞食了食物或massfood，小球会变大，相关代码如下。

if(typeof(currentCell.speed) == "undefined")
currentCell.speed = 6.25;
masaGanada += (foodEaten.length * c.foodMass);
currentCell.mass += masaGanada;
currentPlayer.massTotal += masaGanada;
currentCell.radius = util.massToRadius(currentCell.mass);
playerCircle.r = currentCell.radius;

复制代码

吞食其他玩家

接下来是使用四叉树计算玩家之间的碰撞，笔者就在想，前面都用了那么多个for循环了，这可是每个玩家都对food，massfood，病毒都for一次啊。这里用四叉树意义很大么？为什么不一开始就都用呢？

先使用tree.put构建四叉树，四叉树可以把判断的范围变小，把每个玩家都放进去，然后通过tree.get(currentPlayer, check)获取发生碰撞的玩家。最后再对每个可能发生碰撞的玩家执行collisionCheck。

tree.clear();
users.forEach(tree.put);
var playerCollisions = [];
var otherUsers = tree.get(currentPlayer, check);
playerCollisions.forEach(collisionCheck);

复制代码

接下来看看check，它遍历玩家身上每个cells，然后使用SAT.testCircleCircle测试是否圆在圆内，如果是的话返回一个response结构，该结构里面包含对方玩家的id、name、坐标等信息。然后构建playerCollisions数组。

function check(user) {
for(var i=0; i<user.cells.length; i++) {
if(user.cells[i].mass > 10 && user.id !== currentPlayer.id) {
var response = new SAT.Response();
var collided = SAT.testCircleCircle(playerCircle,
new C(new V(user.cells[i].x, user.cells[i].y), user.cells[i].radius),
response);
if (collided) {
response.aUser = currentCell;
response.bUser = {
id: user.id,
name: user.name,
x: user.cells[i].x,
y: user.cells[i].y,
num: i,
mass: user.cells[i].mass
};
playerCollisions.push(response);
}
}
}
return true;
}

复制代码

然后是对发生碰撞的玩家执行逻辑，把它吃掉。

function collisionCheck(collision) {
if (collision.aUser.mass > collision.bUser.mass * 1.1 && collision.aUser.radius > Math.sqrt(Math.pow(collision.aUser.x - collision.bUser.x, 2) + Math.pow(collision.aUser.y - collision.bUser.y, 2))*1.75) {
console.log('[DEBUG] Killing user: ' + collision.bUser.id);
console.log('[DEBUG] Collision info:');
console.log(collision);
var numUser = util.findIndex(users, collision.bUser.id);
if (numUser > -1) {
if(users[numUser].cells.length > 1) {
users[numUser].massTotal -= collision.bUser.mass;
users[numUser].cells.splice(collision.bUser.num, 1);
} else {
users.splice(numUser, 1);
io.emit('playerDied', { name: collision.bUser.name });
sockets[collision.bUser.id].emit('RIP');
}
}
currentPlayer.massTotal += collision.bUser.mass;
collision.aUser.mass += collision.bUser.mass;
}
}

复制代码

这里是笔者看不懂还是四叉树没啥作用呢？在这里用四叉树和直接两次循环有区别么？check是固定返回true的啊！！！！！下面的四叉树说明，可以证明这里用四叉树是无效的。

四叉树

四叉树空间索引原理及其实现 - 心如止水-GISer的成长之路 - CSDN博客

四叉树索引的基本思想是将地理空间递归划分为不同层次的树结构。它将已知范围的空间等分成四个相等的子空间，如此递归下去，直至树的层次达到一定深度或者满足某种要求后停止分割。四叉树的结构比较简单，并且当空间数据对象分布比较均匀时，具有比较高的空间数据插入和查询效率，因此四叉树是GIS中常用的空间索引之一。常规四叉树的结构如图所示，地理空间对象都存储在叶子节点上，中间节点以及根节点不存储地理空间对象。

四叉树对于区域查询，效率比较高。但如果空间对象分布不均匀，随着地理空间对象的不断插入，四叉树的层次会不断地加深，将形成一棵严重不平衡的四叉树，那么每次查询的深度将大大的增多，从而导致查询效率的急剧下降。

nodejs的 simple-quadtree介绍

代码中的tree.get、tree.put等方法用到了nodejs的simple-quadtree库，这里做个简单介绍。

simple-quadtree

simple-quadtree是一套小型的四叉树实现，每棵树支持 put、 get、remove 和 clear四种操作。四叉树的节点对象必须包含x，y坐标，以及长度宽度w、h。

Put方法

Put方法可以将节点放入四叉树里面，例如：

qt.put({x: 5, y: 5, w: 0, h: 0, string: 'test'});

复制代码

Get方法

Get方法会迭代取出四叉树节点，然后调用回调函数，如下所示。

qt.get({x:0, y: 0, w: 10, h: 10}, function(obj) {
// obj == {x: 5, y: 5, w: 0, h: 0, string: 'test'}
});

复制代码

如果回调函数返回true，迭代会一直进行下去，如果回调函数返回false，则迭代停止。由于源码中的check方法总是返回true，所以这里使用四叉树并没能减少计算量，相反比for循环多了构建树的计算。没什么用！

还是放个广告吧，笔者出版的一本书《Unity3D网络游戏实战》充分的讲解怎样开发一款网络游戏，特别对网络框架设计、网络协议、数据处理等方面都有详细的描述，相信会是一本好书的。

作者：罗培羽
原地址：https://zhuanlan.zhihu.com/p/28107508

微信公众号

微博

头条号

百家号

网易号

知乎号

《球球大作战》源码解析（6）：碰撞处理

微信公众号

微博

头条号