QuadTree4叉树顾名思义就是树状的数据结构，其每一个节点有4个孩子节点，可将2维平面递归分割子区域。QuadTree经常使用于空间数据库索引，3D的椎体可见区域裁剪，乃至图片分析处理，我们今天介绍的是QuadTree最常被游戏领域使用到的碰撞检测。采取QuadTree算法将大大减少需要测试碰撞的次数，从而提高游戏刷新性能，本文例子基于HT
for Web的图形引擎，通过GraphView和Graph3dView同享同1数据模型DataModel，同时显现QuadTree算法下的2D和3D碰撞视图效果：http://v.youku.com/v_show/id_XODQyNTA1NjY0.html
QuadTree的实现有很多成熟的版本，我选择的是 https://github.com/timohausmann/quadtree-js/ 4叉树的算法很简单，因此这个开源库也就两百来行代码。使用也非常简单，构建1个Quadtree对象，第1个参数传入rect信息制定游戏空间范围，在每次requestAnimationFrame刷新帧时，先通过quadtree.clear()清除老数据，通过quadtree.insert(rect)插入新的节点矩形区域，这样quadtree就初始化好了，剩下就是根据需要调用quadtree.retrieve(rect)获得指定矩形区域下，与其可能相交需要检测的矩形对象数组。
我构建了HT的GraphView和Graph3dView两个组件，通过ht.widget.SplitView左右分割，由于两个视图都同享同1DataModel，因此我们剩下的关注点仅是对DataModel的数据操作，构建了200个ht.Node对象，每一个对象的attr属性上保存了随机的运动方向vx和vy，同时保存了将要反复插入quadtree的矩形对象，这样避免每帧更新时反复创建对象，同时矩形对象也援用了ht.Node对象，用来当通过quadtree.retrieve(rect)获得需要检测的矩形对象时，我们能指定其所关联的ht.Node对象，由于我们需要对终究检测为碰撞的图元设置上红色彩的效果，也就是ht.Node平时显示默许的蓝色，当相互碰撞时将改变成红色。
需要注意从quadtree.retrieve(rect)获得需要检测的矩形对象数组中会包括本身图元，同时这些仅仅是可能会碰撞的图元，其实不意味着已碰撞了，由于我们例子是矩形，因此采取ht.Default.intersectsRect(r1, r2)终究判断是不是相交，如果你的例子是圆形则可以采取计算两个圆心距离是不是小于两个半径来决定是不是相交，因此终究判断的标准根据游戏类型会有差异。
采取了QuadTree还是极大了提高了运算性能，否则100个图元就需要100*100次的监测，我这个例子场景下1般也就100*(10~30)的量：http://v.youku.com/v_show/id_XODQyNTA1NjY0.html
除碰撞检测外QuadTree算法还有很多有趣的利用领域，有兴趣可以玩玩这个 https://github.com/fogleman/Quads
所有代码以下供参考：
function init(){
d = 200;
speed = 8;
dataModel = new ht.DataModel();
g3d = new ht.graph3d.Graph3dView(dataModel);
g2d = new ht.graph.GraphView(dataModel);
mainSplit = new ht.widget.SplitView(g3d, g2d);
mainSplit.addToDOM();
g2d.translate(300, 220);
g2d.setZoom(0.8, true);
for(var i=0; i<100; i++) {
var node = new ht.Node();
node.s3(randMinMax(5, 30), 10, randMinMax(5, 30));
node.p3(randMinMax(-d/2, d/2), 0, randMinMax(-d/2, d/2));
node.s({
'batch': 'group',
'shape': 'rect',
'shape.border.width': 1,
'shape.border.color': 'white',
'wf.visible': true,
'wf.color': 'white'
});
node.a({
vx: randMinMax(-speed, speed),
vy: randMinMax(-speed, speed),
obj: {
width: node.getWidth(),
height: node.getHeight(),
data: node
}
});
dataModel.add(node);
}
createShape([
{x: -d, y: d},
{x: d, y: d},
{x: d, y: -d},
{x: -d, y: -d},
{x: -d, y: d}
]);
quadtree = new Quadtree({ x: -d, y: -d, width: d, height: d });
requestAnimationFrame(update);
}
function update() {
quadtree.clear();
dataModel.each(function(data){
if(!(data instanceof ht.Shape)){
var position = data.getPosition();
var vx = data.a('vx');
var vy = data.a('vy');
var w = data.getWidth()/2;
var h = data.getHeight()/2;
var x = position.x + vx;
var y = position.y + vy;
if(x - w < -d){
data.a('vx', -vx);
x = -d + w;
}
if(x + w > d){
data.a('vx', -vx);
x = d - w;
}
if(y - h < -d){
data.a('vy', -vy);
y = -d + h;
}
if(y + h > d){
data.a('vy', -vy);
y = d - h;
}
data.setPosition(x, y);
var obj = data.a('obj');
obj.x = x - w;
obj.y = y - h;
quadtree.insert(obj);
setColor(data, undefined);
}
});
dataModel.each(function(data){
if(!(data instanceof ht.Shape)){
var obj = data.a('obj');
var objs = quadtree.retrieve(obj);
if(objs.length > 1){
for(var i=0; i<objs.length; i++ ) {
var data2 = objs[i].data;
if(data === data2){
continue;
}
if(ht.Default.intersectsRect(obj, data2.a('obj'))){
setColor(data, 'red');
setColor(data2, 'red');
}
}
}
}
});
requestAnimationFrame(update);
}
function randMinMax(min, max) {
return min + (Math.random() * (max - min));
}
function createShape(points){
shape = new ht.Shape();
shape.setPoints(points);
shape.setThickness(4);
shape.setTall(10);
shape.s({
'all.color': 'red',
'shape.background': null,
'shape.border.width': 2,
'shape.border.color': 'red'
});
dataModel.add(shape);
return shape;
}
function setColor(data, color){
data.s({
'all.color': color,
'shape.background': color
});
}