2D碰撞優化 四叉樹碰撞檢測算法

實作原理

四叉樹是什麼?

四叉樹本身是樹結構的一種，如果物體過多的話，先根據物體所處位置劃分成四塊，如果每個塊的中的物體數量還是很多的話，繼續劃分成四塊。如下圖紅線所示。

檢測的時候，就是根據待測試對象的位置，去找屬于哪個塊，再把這個塊中的物體告訴你。如下圖中的綠色物體。

那麼怎麼實作四叉樹呢？用好 

github

 就行了(誤)，搜了一下，找到一個庫，直接拿來改改就行了。

https://github.com/timohausmann/quadtree-js

代碼解析

構造函數

function Quadtree( bounds, max_objects, max_levels, level ) {
    
    this.max_objects    = max_objects || 10;　//每個區域可以容納的最大對象數，超過就需要劃分
    this.max_levels     = max_levels || 4;　//最多劃幾層四叉樹
    
    this.level      = level || 0;　//目前樹或子樹的層，根為0
    this.bounds         = bounds; //bounds就是對象集，每個點包括x,y,width,height(有些實作是圓形，這個是矩形)
    
    this.objects        = [];　//屬于目前節點的對象，不包括子節點的對象
    this.nodes      = [];　//屬于目前樹的節點
};
           

劃分

當調用Insert函數向樹中插入對象的時候，如果目前節點沒有被劃分過的時候，會判斷節點的對象數是否超過的限制的max_objects,如果超過了的話目前節點就會調用這個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 );
 
    //第一象限，和數學裡的坐标軸一樣，不過起點變了而已
    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);
};
           

基本是切割，沒什麼太值得一說的，劃分後的節點level + 1了

查找對象

插入節點和碰撞檢測的時候我們需要先知道對象在這個節點所在的象限，這個函數輸入一個有x,y,width,height的對象，并判斷應該屬于這個節點的哪個象限。

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;
};
           

比較簡單的數學，不過值得注意一點的是，如果一個對象是跨象限的，那麼在它會傳回-1

插入對象到節點

Quadtree.prototype.insert = function( pRect ) {
    
    var i = 0,
    var index;
    
    // 如果目前節點已經劃分過了，就查找對象所屬象限，遞歸調用
    if( typeof this.nodes[0] !== 'undefined' ) {
        index = this.getIndex( pRect );
 
        if( index !== -1 ) {
            this.nodes[index].insert( pRect );   
            return;
        }
    }
 
    this.objects.push( pRect );
    
    // 如果節點對象超過設定值，而且還能繼續劃分(level沒到上限)的時候
    if( this.objects.length > this.max_objects && this.level < this.max_levels ) {
        
        // 先劃分節點
        if( typeof this.nodes[0] === 'undefined' ) {
            this.split();
        }
        
        // 把對象加入對應子節點
        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;
            }
        }
    }
};
           

這裡值得注意一點的是，如果一個對象是跨象限的，這種時候怎麼處理。看代碼段

if( index !== -1 ) {                    
    this.nodes[index].insert( this.objects.splice(i, 1)[0] );
} else {
    i = i + 1;
}
           

之前getIndex的時候我們就說過，如果一個對象是跨象限的，getIndex會傳回-1，從代碼來看，跨象限的對象會被放在目前節點的objects裡面而不會被劃給子節點。這一點很有必要，因為blabla(待補充)

傳回碰撞候選清單

四叉樹最核心的一部分就是要過濾掉一些根本不可能碰撞的對象，避免對比全部的對象以此來提高效率，這個函數輸入一個包含x,y,width,height的對象，傳回一個集合，是經過過濾後的可能和輸入對象發生碰撞的候選對對象。

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;
};
           

首先我們先确立一下，對于一個對象來說，什麼樣的對象才算是可能和它發生碰撞的候選對象？，代碼裡面主要分兩部分來考慮

一個是對象就在這個節點的某個象限裡面，這個時候看代碼段

if( index !== -1 ) {
            returnObjects = returnObjects.concat( this.nodes[index].retrieve( pRect ) );
            
        //if pRect does not fit into a subnode, check it against all subnodes
        } 
           

如果一個對象在目前節點的某個象限裡面，則其碰撞候選是目前節點的對象加上那個象限裡面調用retrieve的節點。這裡也解釋了為什麼跨象限的節點的對象就放在目前節點上，因為跨象限的節點也有可能和某個象限内的節點發生碰撞，是以需要把這些對象都加入到候選對象裡面(盡管可能這個對象在第四象限，而跨象限的對象在第一象限和第二象限之間)

其次是這個對象本身就是跨象限的，這個時候看代碼段

else {
            for( var i=0; i < this.nodes.length; i=i+1 ) {
                returnObjects = returnObjects.concat( this.nodes[i].retrieve( pRect ) );
            }
        }
           

就是直接把這個節點的所有子節點遞歸把結果集合到一起，然後根據上面retrieve的内容我們知道，如果輸入的對象不在節點的任意象限内，則傳回節點上的對象

總結一下就是，當這個對象是個跨象限的對象的時候

可能發生碰撞的是所屬節點所有跨象限的對象加上所跨象限的所有内容，具體可以在網站上自己試一下simple demo