前言

《数据结构 - 应用 JS 实现四叉树》上文中简略介绍了四叉树的一些实现和利用场景 本篇文章应评论区各位小伙伴的留言 基于四叉树实现一下 2D 的碰撞检测。

话不多说开始明天的内容。

首先看下 quadtree 测试效果图

注释 coding 局部

实现思路

• 数据结构采取四叉树

• 碰撞节点比对进行四叉树查找

  sample 采取 canvas2d 进行绘制,JavaScript 进行实现。

实现过程

定义 quadtree 数据结构

/**
    * 四叉树构造函数
    *@四叉树 2D 类碰撞 须要四叉树边界 / 节点层数 /
    *@param{Rect}节点的边界（{x，y，width，height}）*@param{number}[max\u objects=10]在拆分为 4 个子节点之前，节点能够包容的最大对象数 默认:4
    *@param{number}[max\u levels=4]根四叉树内的总最大级别 默认为 4
    *@param{number}[level=0] 深度级别，子节点须要 默认:0  初始深度
*/
function Quadtree(bounds, max_objects, max_levels, level) {
        
        this.max_objects    = max_objects || 4;
        this.max_levels     = max_levels || 4;
        
        this.level  = level || 0;
        this.bounds = bounds;
        
        this.objects    = [];
        this.nodes      = [];};

增加 objects/ 如果超出 max_objects 那么就拆分子节点

/*
    * 将对象插入节点。如果节点
    * 超过容量时，将拆分并增加所有
    * 对象到其相应的子节点。*@param{Rect}要增加的对象的 pRect 边界（{x，y，width，height}）*@memberof 四叉树
*/
Quadtree.prototype.insert = function(pRect) {

    var i = 0,
        indexes;

    // 如果存在子节点, 那么找到子节点像子节点增加数据(子节点就是子树)
    if(this.nodes.length) {indexes = this.getIndex(pRect);

        for(i=0; i<indexes.length; i++) {this.nodes[indexes[i]].insert(pRect);     
        }
        return;
    }

    // 如果没找到不存在 nodes 向 objects 增加
    this.objects.push(pRect);

    // 如果 objects 超出最大 max_objects 那么就拆分
    // 开始
    if(this.objects.length > this.max_objects && this.level < this.max_levels) {// 拆分子节点 (split 办法能够移步仓库看代码, 很简略。后续不贴了)
        if(!this.nodes.length) {this.split();
        }

        // 将所有 objects 增加到对应的 nodes 
        for(i=0; i<this.objects.length; i++) {indexes = this.getIndex(this.objects[i]); // 找到对应的 nodes
            for(var k=0; k<indexes.length; k++) {this.nodes[indexes[k]].insert(this.objects[i]);
            }
        }

        // 清空这个 objects
        this.objects = [];
        // 超出 max_objects 逻辑完结
    }
 };

获取

/**
    * 确定对象属于哪个节点
    *@param{Rect}要查看的区域的 pRect 边界（{x，y，width，height}）*@return{number[]}相交子节点的索引数组（0-3= 右上、左上、左下、右下）*@memberof 四叉树
*/
Quadtree.prototype.getIndex = function(pRect) {var indexes = [],
        verticalMidpoint    = this.bounds.x + (this.bounds.width/2), // x 核心
        horizontalMidpoint  = this.bounds.y + (this.bounds.height/2);    // y 核心
    // 判断属于哪个区域
    var startIsNorth = pRect.y < horizontalMidpoint,
        startIsWest  = pRect.x < verticalMidpoint,
        endIsEast    = pRect.x + pRect.width > verticalMidpoint,
        endIsSouth   = pRect.y + pRect.height > horizontalMidpoint;    

    // 右上 quad
    if(startIsNorth && endIsEast) {indexes.push(0);
    }
    
    // 左上 quad
    if(startIsWest && startIsNorth) {indexes.push(1);
    }

    // 左下 quad
    if(startIsWest && endIsSouth) {indexes.push(2);
    }

    // 右下 quad
    if(endIsEast && endIsSouth) {indexes.push(3);
    }
    return indexes;
};

给定一个 rect 构造进行碰撞

/**
    * 返回所有可能与给定对象碰撞的对象
    *@param{Rect}要查看的对象的 pRect 边界（{x，y，width，height}）*@return{Rect[]}数组，蕴含所有检测到的对象
    *@memberof 四叉树
*/
Quadtree.prototype.retrieve = function(pRect) {var indexes = this.getIndex(pRect),
        returnObjects = this.objects;

    //if we have subnodes, retrieve their objects
    if(this.nodes.length) {for(var i=0; i<indexes.length; i++) {returnObjects = returnObjects.concat(this.nodes[indexes[i]].retrieve(pRect));
        }
    }

    //objects 去重
    returnObjects = returnObjects.filter(function(item, index) {return returnObjects.indexOf(item) >= index;
    });

    return returnObjects;
};

革除四叉树

/**
    * 革除四叉树
    * @memberof Quadtree
*/
Quadtree.prototype.clear = function() {this.objects = [];
 
    for(var i=0; i < this.nodes.length; i++) {if(this.nodes.length) {this.nodes[i].clear();}
    }

    this.nodes = [];};

quadtree 其余相干仓库 D3 Quadtree

拿 D3 来做一下学习, 首先实现更为全面 (能够看上面截图里具体的一个构造模块) 有 add cover,data,find…. 而且细节做的很棒, 值得学习。上面简略举个例子

就拿一个模块来说: find.js 也是寻找相应的 nodes 而后追加 同样的实现, 区别在于能够了解为拜访做了记录 / 不拜访反复点, 而且有就近拜访准则(这个能够做一些其余工作)i = (y >= ym) << 1 | (x >= xm), 有趣味的能够去学习一下。

总的来说 D3 外部存在一些可能帮忙到你思维转变晋升的货色, 学习还是很要必要的。对了, 实际过程中能够尝试和 d3-force 模块联合应用, 成果更佳。

结语

四叉树作为树的一种构造, 下面的例子很好的体现了四叉树在 2D 碰撞的实际, 有任何疑问请随时留言。

最初~ 托更一天自己感到十分道歉！！！

其余链接

上述示例代码仓库

D3 Quadtree