前言
這篇文章會(huì)簡單介紹一下四叉樹的基本思想，然后會(huì)對(duì)timohausmann/quadtree-js進(jìn)行代碼解析。
預(yù)備理論
什么是四叉樹
為什么需要四叉樹
怎么通過四叉樹進(jìn)行碰撞檢測
代碼解析
構(gòu)造函數(shù)
function Quadtree( bounds, max_objects, max_levels, level ) {
this.max_objects = max_objects || 10; //每個(gè)區(qū)域可以容納的最大對(duì)象數(shù)，超過就需要?jiǎng)澐? this.max_levels = max_levels || 4; //最多劃幾層四叉樹
this.level = level || 0; //當(dāng)前樹或子樹的層，根為0
this.bounds = bounds; //bounds就是對(duì)象集，每個(gè)點(diǎn)包括x,y,width,height(有些實(shí)現(xiàn)是圓形，這個(gè)是矩形)
this.objects = []; //屬于當(dāng)前節(jié)點(diǎn)的對(duì)象，不包括子節(jié)點(diǎn)的對(duì)象
this.nodes = []; //屬于當(dāng)前樹的節(jié)點(diǎn)
};
劃分
當(dāng)調(diào)用Insert函數(shù)向樹中插入對(duì)象的時(shí)候，如果當(dāng)前節(jié)點(diǎn)沒有被劃分過的時(shí)候，會(huì)判斷節(jié)點(diǎn)的對(duì)象數(shù)是否超過的限制的max_objects,如果超過了的話當(dāng)前節(jié)點(diǎn)就會(huì)調(diào)用這個(gè)split方法。
Quadtree.prototype.split = function() {
var nextLevel = this.level + 1;
var subWidth = Math.round( this.bounds.width / 2 );
var subHeight = Math.round( this.bounds.height / 2 );
var x = Math.round( this.bounds.x );
var y = Math.round( this.bounds.y );
//第一象限，和數(shù)學(xué)里的坐標(biāo)軸一樣，不過起點(diǎn)變了而已
this.nodes[0] = new Quadtree({
x : x + subWidth,
y : y,
width : subWidth,
height : subHeight
}, this.max_objects, this.max_levels, nextLevel);
//第二象限
this.nodes[1] = new Quadtree({
x : x,
y : y,
width : subWidth,
height : subHeight
}, this.max_objects, this.max_levels, nextLevel);
//第三象限
this.nodes[2] = new Quadtree({
x : x,
y : y + subHeight,
width : subWidth,
height : subHeight
}, this.max_objects, this.max_levels, nextLevel);
//第四象限
this.nodes[3] = new Quadtree({
x : x + subWidth,
y : y + subHeight,
width : subWidth,
height : subHeight
}, this.max_objects, this.max_levels, nextLevel);
};
基本是切割，沒什么太值得一說的，劃分后的節(jié)點(diǎn)level + 1了
查找對(duì)象
插入節(jié)點(diǎn)和碰撞檢測的時(shí)候我們需要先知道對(duì)象在這個(gè)節(jié)點(diǎn)所在的象限，這個(gè)函數(shù)輸入一個(gè)有x,y,width,height的對(duì)象，并判斷應(yīng)該屬于這個(gè)節(jié)點(diǎn)的哪個(gè)象限。
Quadtree.prototype.getIndex = function( pRect ) {
var index = -1,
verticalMidpoint = this.bounds.x + (this.bounds.width / 2),
horizontalMidpoint = this.bounds.y + (this.bounds.height / 2),
topQuadrant = (pRect.y < horizontalMidpoint && pRect.y + pRect.height < horizontalMidpoint),
//pRect can completely fit within the bottom quadrants
bottomQuadrant = (pRect.y > horizontalMidpoint);
if( pRect.x < verticalMidpoint && pRect.x + pRect.width < verticalMidpoint ) {
if( topQuadrant ) {
index = 1;
} else if( bottomQuadrant ) {
index = 2;
}
} else if( pRect.x > verticalMidpoint ) {
if( topQuadrant ) {
index = 0;
} else if( bottomQuadrant ) {
index = 3;
}
}
return index;
};
比較簡單的數(shù)學(xué)，不過值得注意一點(diǎn)的是，如果一個(gè)對(duì)象是跨象限的，那么在它會(huì)返回-1
插入對(duì)象到節(jié)點(diǎn)
Quadtree.prototype.insert = function( pRect ) {
var i = 0,
var index;
// 如果當(dāng)前節(jié)點(diǎn)已經(jīng)劃分過了，就查找對(duì)象所屬象限，遞歸調(diào)用
if( typeof this.nodes[0] !== 'undefined' ) {
index = this.getIndex( pRect );
if( index !== -1 ) {
this.nodes[index].insert( pRect );
return;
}
}
this.objects.push( pRect );
// 如果節(jié)點(diǎn)對(duì)象超過設(shè)置值，而且還能繼續(xù)劃分(level沒到上限)的時(shí)候
if( this.objects.length > this.max_objects && this.level < this.max_levels ) {
// 先劃分節(jié)點(diǎn)
if( typeof this.nodes[0] === 'undefined' ) {
this.split();
}
// 把對(duì)象加入對(duì)應(yīng)子節(jié)點(diǎn)
while( i < this.objects.length ) {
index = this.getIndex( this.objects[ i ] );
if( index !== -1 ) {
this.nodes[index].insert( this.objects.splice(i, 1)[0] );
} else {
i = i + 1;
}
}
}
};
這里值得注意一點(diǎn)的是，如果一個(gè)對(duì)象是跨象限的，這種時(shí)候怎么處理?？创a段
if( index !== -1 ) {
this.nodes[index].insert( this.objects.splice(i, 1)[0] );
} else {
i = i + 1;
}
之前getIndex的時(shí)候我們就說過，如果一個(gè)對(duì)象是跨象限的，getIndex會(huì)返回-1，從代碼來看，跨象限的對(duì)象會(huì)被放在當(dāng)前節(jié)點(diǎn)的objects里面而不會(huì)被劃給子節(jié)點(diǎn)。這一點(diǎn)很有必要，因?yàn)閎labla(待補(bǔ)充)
返回碰撞候選列表
四叉樹最核心的一部分就是要過濾掉一些根本不可能碰撞的對(duì)象，避免對(duì)比全部的對(duì)象以此來提高效率，這個(gè)函數(shù)輸入一個(gè)包含x,y,width,height的對(duì)象，返回一個(gè)集合，是經(jīng)過過濾后的可能和輸入對(duì)象發(fā)生碰撞的候選對(duì)對(duì)象。
Quadtree.prototype.retrieve = function( pRect ) {
var index = this.getIndex( pRect ),
returnObjects = this.objects;
//if we have subnodes ...
if( typeof this.nodes[0] !== 'undefined' ) {
//if pRect fits into a subnode ..
if( index !== -1 ) {
returnObjects = returnObjects.concat( this.nodes[index].retrieve( pRect ) );
//if pRect does not fit into a subnode, check it against all subnodes
} else {
for( var i=0; i < this.nodes.length; i=i+1 ) {
returnObjects = returnObjects.concat( this.nodes[i].retrieve( pRect ) );
}
}
}
return returnObjects;
};
首先我們先確立一下，對(duì)于一個(gè)對(duì)象來說，什么樣的對(duì)象才算是可能和它發(fā)生碰撞的候選對(duì)象？，代碼里面主要分兩部分來考慮
一個(gè)是對(duì)象就在這個(gè)節(jié)點(diǎn)的某個(gè)象限里面，這個(gè)時(shí)候看代碼段
if( index !== -1 ) {
returnObjects = returnObjects.concat( this.nodes[index].retrieve( pRect ) );
//if pRect does not fit into a subnode, check it against all subnodes
}
如果一個(gè)對(duì)象在當(dāng)前節(jié)點(diǎn)的某個(gè)象限里面，則其碰撞候選是當(dāng)前節(jié)點(diǎn)的對(duì)象加上那個(gè)象限里面調(diào)用retrieve的節(jié)點(diǎn)。這里也解釋了為什么跨象限的節(jié)點(diǎn)的對(duì)象就放在當(dāng)前節(jié)點(diǎn)上，因?yàn)榭缦笙薜墓?jié)點(diǎn)也有可能和某個(gè)象限內(nèi)的節(jié)點(diǎn)發(fā)生碰撞，所以需要把這些對(duì)象都加入到候選對(duì)象里面(盡管可能這個(gè)對(duì)象在第四象限，而跨象限的對(duì)象在第一象限和第二象限之間)
其次是這個(gè)對(duì)象本身就是跨象限的，這個(gè)時(shí)候看代碼段
else {
for( var i=0; i < this.nodes.length; i=i+1 ) {
returnObjects = returnObjects.concat( this.nodes[i].retrieve( pRect ) );
}
}
就是直接把這個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)遞歸把結(jié)果集合到一起，然后根據(jù)上面retrieve的內(nèi)容我們知道，如果輸入的對(duì)象不在節(jié)點(diǎn)的任意象限內(nèi)，則返回節(jié)點(diǎn)上的對(duì)象
總結(jié)一下就是，當(dāng)這個(gè)對(duì)象是個(gè)跨象限的對(duì)象的時(shí)候
可能發(fā)生碰撞的是所屬節(jié)點(diǎn)所有跨象限的對(duì)象加上所跨象限的所有內(nèi)容，具體可以在網(wǎng)站上自己試一下simple demo
