JS实现的四叉树算法详解 - 行业资讯 - 肥雀云

本文实例讲述了JS实现的四叉树算法。分享给大家供大家参考,具体如下:

最近在看帆布动画方面教程,里面提到了采用四叉树检测碰撞。之前也看到过四叉树这个名词,但是一直不是很懂。于是就又找了一些四叉树方面的资料看了看,做个笔记,就算日后忘的了,也可以回来看看。

四叉树四叉树顾名思义就是树状的数据结构,其每个节点有四个孩子节点,可将二维平面递归分割子区域.QuadTree常用于空间数据库索引,3 d的椎体可见区域裁剪,甚至图片分析处理,我们今天介绍的是四叉树最常被游戏领域使用到的碰撞检测。采用四叉树算法将大大减少需要测试碰撞的次数,从而提高游戏刷新性能,

四叉树很简单,就是把一块2 d的区域,等分成4份,如下图:,,,我们把4块区域从右上象限开始编号,逆时针。

四叉树起始于单节点。对象会被添加到四叉树的单节点上。

当更多的对象被添加到四叉树里时,它们最终会被分为四个子节点。(我是这么理解的:下面的图片不是分为四个区域吗,每个区域就是一个孩子或子节点),然后每个物体根据他在2 d空间的位置而被放入这些子节点中的一个里,任何不能正好在一个节点区域内的物体会被放在父节点。(这点我不是很理解,就这幅图来说,那根节点的子节点岂不是有五个节点了。)

如果有更多的对象被添加进来,那么每个子节点要继续划分(成四个节点)。

正如你看到的,每个节点仅包括几个物体。这样我们就可以明白前面所说的规则,例如,左上角节点里的物体是不可能和右下角节点里的物体碰撞的,所以我们也就没必要运行消耗很多资源的碰撞检测算法来检验他们之间是否会发生碰撞。

<强>下面我们对四叉树进行实现:

主要代码:()

　　　　　　函数四叉树(boundBox级){ 　　var maxObjects=10; 　　这一点。边界=boundBox | | { 　　x: 0, 　　y: 0, 　　宽度:0, 　　高度:0 　　}; 　　var对象=[]; 　　这一点。节点=[]; 　　var=级水平| | 0; 　　var maxLevels=5; 　　} 　　　　之前　　　　

maxObjects是每个节点能容纳的最多对象超过则分割4个节点,我们并不是事先就分好格子,而是在插入对象的时候才进行划分。

maxLevels是四叉树的最大层数超过则不再划分从根节点开始最多6层。

水平:当前层数

对象:当前节点内的待检测的对象。

范围:当前节点所表示的2 d区域的范围

节点:4个子节点队列。

四叉树每个节点的面积可以为任意形状。然后,我们会使用五个四叉树里会用到的方法,分别为:清晰、分裂,getIndex,插入和检索。

　　　　　　函数clear () { 　　对象=[]; 　　(var=0;我& lt;this.nodes.length;我+ +){ 　　this.nodes[我].clear (); 　　} 　　这一点。节点=[]; 　　}; 　　　　之前　　　　

明确函数,是通过循环来清除四叉树所有节点的所有对象。

　　　　　　功能划分(){//按位或[html5rocks] 　　var subWidth=(this.bounds。宽/2)| 0; 　　var subHeight=(this.bounds。身高/2)| 0; 　　这一点。新四叉树节点[0]=({ 　　x: this.bounds。x + subWidth, 　　y: this.bounds.y, 　　宽度:subWidth, 　　高度:subHeight 　　},等级+ 1); 　　这一点。新四叉树节点[1]=({ 　　x: this.bounds.x, 　　y: this.bounds.y, 　　宽度:subWidth, 　　高度:subHeight 　　},等级+ 1); 　　这一点。新四叉树节点[2]=({ 　　x: this.bounds.x, 　　y: this.bounds。y + subHeight, 　　宽度:subWidth, 　　高度:subHeight 　　},等级+ 1); 　　这一点。新四叉树节点[3]=({ 　　x: this.bounds。x + subWidth, 　　y: this.bounds。y + subHeight, 　　宽度:subWidth, 　　高度:subHeight 　　},等级+ 1); 　　} 　　　　之前　　　　

分裂方法,就是用来将节点分成相等的四份面积,并用新的边界来初始化四个新的子节点。