四叉树碰撞检测算法

实现原理

四叉树是什么?

四叉树本身是树结构的一种，如果物体过多的话，先根据物体所处位置划分成四块，如果每个块的中的物体数量还是很多的话，继续划分成四块。如下图红线所示。

检测的时候，就是根据待测试对象的位置，去找属于哪个块，再把这个块中的物体告诉你。如下图中的绿色物体。

那么怎么实现四叉树呢？用好 github 就行了(误)，搜了一下，找到一个库，直接拿来改改就行了。

GitHub - timohausmann/quadtree-js: A lightweight quadtree implementation for javascript

代码解析

构造函数

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