前言
《数据结构-应用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