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

小篱

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

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

1. for(var z=0; z<currentPlayer.cells.length; z++) {
   
2. 
   
3.     ……
   
4. 
   
5. }

复制代码

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

1. var V = SAT.Vector; //一开始定义
   
2. var C = SAT.Circle;
   
3. 
   
4. 
   
5. var playerCircle = new C(
   
6.             new V(currentCell.x, currentCell.y),
   
7.             currentCell.radius
   
8.         );

复制代码

吞食食物

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

1. var foodEaten = food.map(funcFood)
   
2. 
   
3.             .reduce( function(a, b, c) { return b ? a.concat(c) : a; }, []);
   
4. 
   
5. 
   
6. 
   
7.         foodEaten.forEach(deleteFood);
   
8. 
   
9. 
   
10. 
    
11. 
    
12. 
    
13.     function funcFood(f) {
    
14. 
    
15.         return SAT.pointInCircle(new V(f.x, f.y), playerCircle);
    
16. 
    
17.     }
    
18. 
    
19. 
    
20. 
    
21.     function deleteFood(f) {
    
22. 
    
23.         food[f] = {};
    
24. 
    
25.         food.splice(f, 1);
    
26. 
    
27.     }

复制代码

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

吞食massFood

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

1. var massEaten = massFood.map(eatMass)
   
2.             .reduce(function(a, b, c) {return b ? a.concat(c) : a; }, []);
   
3. 
   
4.      ……
   
5. 
   
6.         var masaGanada = 0;
   
7.         for(var m=0; m<massEaten.length; m++) {
   
8.             masaGanada += massFood[massEaten[m]].masa;
   
9.             massFood[massEaten[m]] = {};
   
10.             massFood.splice(massEaten[m],1);
    
11.             for(var n=0; n<massEaten.length; n++) {
    
12.                 if(massEaten[m] < massEaten[n]) {
    
13.                     massEaten[n]--;
    
14.                 }
    
15.             }
    
16.         }

复制代码

吞食病毒

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

1. 
   
2.         var virusCollision = virus.map(funcFood)
   
3. 
   
4.            .reduce( function(a, b, c) { return b ? a.concat(c) : a; }, []);
   
5. 
   
6. 
   
7. 
   
8.         if(virusCollision > 0 && currentCell.mass > virus[virusCollision].mass) {
   
9. 
   
10.           sockets[currentPlayer.id].emit('virusSplit', z);
    
11. 
    
12.         }

复制代码

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

增加质量

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

1. if(typeof(currentCell.speed) == "undefined")
   
2. 
   
3.             currentCell.speed = 6.25;
   
4. 
   
5.         masaGanada += (foodEaten.length * c.foodMass);
   
6. 
   
7.         currentCell.mass += masaGanada;
   
8. 
   
9.         currentPlayer.massTotal += masaGanada;
   
10. 
    
11.         currentCell.radius = util.massToRadius(currentCell.mass);
    
12. 
    
13.         playerCircle.r = currentCell.radius;

复制代码

吞食其他玩家

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

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

1. 
   
2.         tree.clear();
   
3. 
   
4.         users.forEach(tree.put);
   
5. 
   
6.         var playerCollisions = [];
   
7. 
   
8. 
   
9. 
   
10.         var otherUsers =  tree.get(currentPlayer, check);
    
11. 
    
12. 
    
13. 
    
14.         playerCollisions.forEach(collisionCheck);

复制代码

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

1. function check(user) {
   
2. 
   
3.         for(var i=0; i<user.cells.length; i++) {
   
4. 
   
5.             if(user.cells[i].mass > 10 && user.id !== currentPlayer.id) {
   
6. 
   
7.                 var response = new SAT.Response();
   
8. 
   
9.                 var collided = SAT.testCircleCircle(playerCircle,
   
10. 
    
11.                     new C(new V(user.cells[i].x, user.cells[i].y), user.cells[i].radius),
    
12. 
    
13.                     response);
    
14. 
    
15.                 if (collided) {
    
16. 
    
17.                     response.aUser = currentCell;
    
18. 
    
19.                     response.bUser = {
    
20. 
    
21.                         id: user.id,
    
22. 
    
23.                         name: user.name,
    
24. 
    
25.                         x: user.cells[i].x,
    
26. 
    
27.                         y: user.cells[i].y,
    
28. 
    
29.                         num: i,
    
30. 
    
31.                         mass: user.cells[i].mass
    
32. 
    
33.                     };
    
34. 
    
35.                     playerCollisions.push(response);
    
36. 
    
37.                 }
    
38. 
    
39.             }
    
40. 
    
41.         }
    
42. 
    
43.         return true;
    
44. 
    
45.     }

复制代码

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

1. function collisionCheck(collision) {
   
2. 
   
3.         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) {
   
4. 
   
5.             console.log('[DEBUG] Killing user: ' + collision.bUser.id);
   
6. 
   
7.             console.log('[DEBUG] Collision info:');
   
8. 
   
9.             console.log(collision);
   
10. 
    
11. 
    
12. 
    
13.             var numUser = util.findIndex(users, collision.bUser.id);
    
14. 
    
15.             if (numUser > -1) {
    
16. 
    
17.                 if(users[numUser].cells.length > 1) {
    
18. 
    
19.                     users[numUser].massTotal -= collision.bUser.mass;
    
20. 
    
21.                     users[numUser].cells.splice(collision.bUser.num, 1);
    
22. 
    
23.                 } else {
    
24. 
    
25.                     users.splice(numUser, 1);
    
26. 
    
27.                     io.emit('playerDied', { name: collision.bUser.name });
    
28. 
    
29.                     sockets[collision.bUser.id].emit('RIP');
    
30. 
    
31.                 }
    
32. 
    
33.             }
    
34. 
    
35.             currentPlayer.massTotal += collision.bUser.mass;
    
36. 
    
37.             collision.aUser.mass += collision.bUser.mass;
    
38. 
    
39.         }
    
40. 
    
41.     }

复制代码

这里是笔者看不懂还是四叉树没啥作用呢？在这里用四叉树和直接两次循环有区别么？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方法可以将节点放入四叉树里面，例如：

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

复制代码

Get方法

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

1. qt.get({x:0, y: 0, w: 10, h: 10}, function(obj) {
   
2. 
   
3. 
   
4. 
   
5. // obj == {x: 5, y: 5, w: 0, h: 0, string: 'test'}
   
6. 
   
7. 
   
8. 
   
9. });
   
10. 
    

复制代码

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

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

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