Cocos Creator 开源技术方案详解:使用四叉树优化碰撞检测
引言:Cocos 技术支持团队将基于官方或开发者分享的开源方案,持续为大家整理、提供一些实用的技术解决方案,并随着 Cocos Creator 更新迭代,确保其在新版引擎中可运行,帮助大家提升开发效率,做出更棒的游戏效果。本次,我们先从「四叉树碰撞检测优化方案」说起。
方案应用效果
四叉树(quad-tree)又称四元数,是一种树状数据结构,在每一个节点上会有四个子区块。四叉树常应用于二维空间数据的分析与分类,如果是在三维空间中,则就是八叉树。
简单来说,四叉树就是一种优化方法,能够帮助我们对元素按照区域进行划分,减少检测数量。需要说明的是,四叉树只是一种「减少碰撞候选者」的算法,在利用四叉树得到碰撞候选元素后,还需要检测这些候选元素与目标元素是否发生碰撞。
运用场景
四叉树被广泛应用于游戏开发中的游戏内大地图检测、子弹碰撞检测等方面。
想象一下,假如在我们要在游戏中对200个物体进行碰撞检测,按照常规的碰撞检测方式,每帧每个物体都要对其他199个物体进行物理碰撞检测,则需要进行200*199=39800次检测。这样的检测效率,很容易对低端手机的性能造成一定的影响。
而使用四叉树则能够大大减少检测次数,那么,它又是怎么做到的呢?
原理探究
我们把游戏屏幕看做一个区域,不断放置圆点进去。假设我们设定每个区域只能容纳4个物体,只要超过这个数量,就分割该区域。如下图,当区域内的圆点数达到4个,这个时候再想加入第5个,就必须先将当前区域分割为4个区域,再将第5个放入左上区域:
以此类推,当要放入第9个圆点时,我们发现黑色圆点所在的左上区域也满了,那么就需要再对左上区域再次进行分割。如下图:
最后,我们就可以得出下图这样的树状结构,这也是为什么会叫做四叉树的原因。
碰撞检测
GitHub 用户「xjz1994」提供了一个四叉树碰撞检测优化开源方案,官方技术团队已将其升级至 Cocos Creator 3.4.1 版本。使用核心代码如下。
通过代码引入:
import{Quadtree}from"./QuadTree";
创建四叉树,区域为整个屏幕,并将树保存为全局变量:
privatetree:Quadtree=null;start(){constbounds={x:0,y:0,width:screen.width,height:screen.height}this.tree=newQuadtree(bounds);}
插入需要做碰撞检测的目标元素:
for(leti=0;i<250;i++){letnewNode=instantiate(this.nodePrefab);this.node.addChild(newNode);this.nodes.push(newNode);this.tree.insert(newNode);}}
检索目标元素的待检测碰撞对象,返回碰撞候选元素组:
//node为目标元素,targetNodes为碰撞候选元素组lettargetNodes=this.tree.retrieve(node)//进行碰撞检测这个部分可以调用自己写的碰撞检测,也可以调用引擎自带的检测,这里选用自己写的letisCollision:any=this.isCollision(targetNode,node)
清除四叉树中的元素,以方便下次继续检测:
this.tree.clear();
资源下载
点击文末【阅读原文】前往 GitHub 免费下载方案:
https://github.com/cocos/cocos-awesome-tech-solutions/tree/3.4.0-release/demo/Creator3.4.1_2D_QuadtreeCollision
论坛反馈贴
https://forum.cocos.org/t/topic/128862
四叉树或许不是最好的多物体检测算法,但是它适用于大部分情况,并且能够无缝的插入到你的项目当中。完整代码请下载方案查看,我们对四叉树算法做了详细注释,感兴趣的同学可以进行更深入的学习与优化。
参考链接
https://davidhsu666.com/archives/quadtree_in_2d/#7-%E7%B8%BD%E7%B5%90
https://forum.cocos.org/t/topic/95573
往期精彩相关阅读
-
世界热推荐:今晚7:00直播丨下一个突破...
今晚19:00,Cocos视频号直播马上点击【预约】啦↓↓↓在运营了三年... -
NFT周刊|Magic Eden宣布支持Polygon网...
Block-986在NFT这样的市场,每周都会有相当多项目起起伏伏。在过去... -
环球今亮点!头条观察 | DeFi的兴衰与...
在比特币得到机构关注之后,许多财务专家预测世界将因为加密货币的... -
重新审视合作,体育Crypto的可靠关系才能双赢
Block-987即使在体育Crypto领域,人们的目光仍然集中在FTX上。随着... -
简讯:前端单元测试,更进一步
前端测试@2022如果从2014年Jest的第一个版本发布开始计算,前端开发... -
焦点热讯:刘强东这波操作秀
近日,刘强东发布京东全员信,信中提到:自2023年1月1日起,逐步为...