四叉树优化碰撞检测

HTML

<canvas id="mycanvas"></canvas>

CSS

canvas {
    border: 1px solid #000;
}

JavaScript

(function(global) {
    var QuadTree = function QuadTree(bounds, level) {
        if (!(this instanceof QuadTree)) return;
        this.objects = [];
        this.nodes = [];
        this.level = typeof level === 'undefined' ? 0 : level;
        this.bounds = bounds;
    },
    cacheArr = [],
    concatArr, spliceArr;

    concatArr = function(targetArr) {
        var arr, i;
        for (i = 1; i < arguments.length; i++) {
            arr = arguments[i];
            Array.prototype.push.apply(targetArr, arr);
        }
    };

    spliceArr = function(arr, index, num) {
        var i, len;
        for (i = index + num, len = arr.length; i < len; i++) {
            arr[i - num] = arr[i];
        }
        arr.length = len - num;
    };

    // 常量
    QuadTree.prototype.MAX_OBJECTS = 10;
    QuadTree.prototype.MAX_LEVELS = 5;

    // 清空子节点
    QuadTree.prototype.clear = function() {
        var nodes = this.nodes,
            subnode;
        this.objects.splice(0, this.objects.length);
        while (nodes.length) {
            subnode = nodes.shift();
            subnode.clear();
        }
    };

    // 分裂
    QuadTree.prototype.split = function() {
        var level = this.level,
            bounds = this.bounds,
            x = bounds.x,
            y = bounds.y,
            sWidth = bounds.sWidth,
            sHeight = bounds.sHeight;

        this.nodes.push(
            new QuadTree(new Rect(bounds.cX, y, sWidth, sHeight), level + 1),
            new QuadTree(new Rect(x, y, sWidth, sHeight), level + 1),
            new QuadTree(new Rect(x, bounds.cY, sWidth, sHeight), level + 1),
            new QuadTree(new Rect(bounds.cX, bounds.cY, sWidth, sHeight), level + 1)
        );
    };

    // 获取象限号
    QuadTree.prototype.getIndex = function(rect, checkIsInner) {
        var bounds = this.bounds,
            onTop = rect.y + rect.h <=  bounds.cY,
            onBottom = rect.y >= bounds.cY,
            onLeft = rect.x + rect.w <= bounds.cX,
            onRight =...