HT for Web可視化QuadTree四叉樹碰撞檢測
來源：程序員人生 發布時間：2014-12-09 08:56:59 閱讀次數：3673次
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
});
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
