《数据结构-使用JS实现四叉树》 上文中简单介绍了四叉树的一些实现和应用场景 本篇文章应评论区各位小伙伴的留言 基于四叉树实现一下2D的碰撞检测。
话不多说开始今天的内容。
碰撞节点比对进行四叉树查找
sample采取canvas2d进行绘制,JavaScript进行实现。
/**
*四叉树构造函数
*@四叉树 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 = [];
};
/*
*将对象插入节点。如果节点
*超过容量时,将拆分并添加所有
*对象到其相应的子节点。
*@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;
};
/**
*返回所有可能与给定对象碰撞的对象
*@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 = [];
};
D3 Quadtree
就拿一个模块来说:
find.js
也是寻找相应的nodes 然后追加 同样的实现,区别在于可以理解为访问做了记录/不访问重复点,而且有就近访问原则(这个可以做一些其他工作)i = (y >= ym) << 1 | (x >= xm)
,有兴趣的可以去学习一下。总的来说D3内部存在一些能够帮助到你思维转变提升的东西,学习还是很要必要的。对了, 实践过程中可以尝试和d3-force模块结合使用,效果更佳。
四叉树作为树的一种结构,上面的例子很好的体现了四叉树在2D碰撞的实践,有任何疑问请随时留言。
最后~ 托更一天本人感到非常抱歉!!!
在ie下设置 css 样式 style="cursor:hand;" 可以正常显示 但是在firefox下就不行...
在讲CSS优先级之前,我们得要了解什么是CSS,CSS是用来做什么的。 首先,我们对C...
作者 / Krish Vitaldevara,Google Play 信任与安全产品管理总监 多年来,向数十...
CSS3实现酷炫的3D旋转透视 3D动画效果现在越来越普及,已经被广泛的应用到了各个...
一、作用 离线浏览 - 根据文件规则把资源缓存在本地,脱机依然能够访问资源,联...
背景 京东购物小程序作为京东小程序业务流量的主要入口,承载着许多的活动和页面...
打开软件,我们按快捷键ctrl+n,建立一个新的文件。 点击常用,选择布局。 点击...
Dreamweaver中如何使用Flash影片 1、首先需要我们准备的是一个Flash文件,其次最...
最近在做项目时,发现CSS3中关于动画的技术,自己很少运用在项目中,平时一些列...
行高line-height实现单行文本垂直居中 以前一直认为单行文本垂直居中要将高度和...