QuadTree四叉樹顧名思義就是樹狀的數據結構，其每個節點有四個孩子節點，可將二維平面遞歸分割子區域。QuadTree常用於空間數據庫索引，3D的椎體可見區域裁剪，甚至圖片分析處理，我們今天介紹的是QuadTree最常被游戲領域使用到的碰撞檢測。采用QuadTree算法將大大減少需要測試碰撞的次數，從而提高游戲刷新性能，本文例子基於HT for Web的Canvas拓撲圖和WebGL的3D引擎組件，通過GraphView和Graph3dView共享同一數據模型DataModel，同時呈現QuadTree算法下的2D和3D碰撞視圖效果：http://v.youku.com/v_show/id_XODQyNTA1NjY0.html
http://www.hightopo.com/demo/QuadTree/ht-quadtree.html
QuadTree的實現有很多成熟的版本，我選擇的是https://github.com/timohausmann/quadtree-js/四叉樹的算法很簡單，因此這個開源庫也就兩百來行代碼。使用也非常簡單，構建一個Quadtree對象，第一個參數傳入rect信息制定游戲空間范圍，在每次requestAnimationFrame刷新幀時，先通過quadtree.clear()清除老數據，通過quadtree.insert(rect)插入新的節點矩形區域，這樣quadtree就初始化好了，剩下就是根據需要調用quadtree.retrieve(rect)獲取指定矩形區域下，與其可能相交需要檢測的矩形對象數組。
我構建了HT(http://www.hightopo.com/)的GraphView和Graph3dView兩個組件，通過ht.widget.SplitView左右分割，由於兩個視圖都共享同一DataModel，因此我們剩下的關注點僅是對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次的監測，我這個例子場景下一般也就100*(10~30)的量：http://v.youku.com/v_show/id_XODQyNTA1NjY0.html
http://www.hightopo.com/demo/QuadTree/ht-quadtree.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
