Quadtree implementation that was used to optimize crashy.io. Quadtree is used to optimize collision detection and reduce the time complexity for checks from O(n²) to O(n log (n))

quadtree.js

//******************* QuadTree Implementation *******************
var getX = function(item){
	return item.x - item.width/2;
}
var getY = function(item){
	return item.y - item.height/2;
}
function QuadTree(bounds, pointQuad, maxDepth, maxChildren) {
        var node;
        if (pointQuad) {

            node = new Node(bounds, 0, maxDepth, maxChildren);
        } else {
            node = new BoundsNode(bounds, 0, maxDepth, maxChildren);
        }

        this.root = node;
    }

    QuadTree.prototype.root = null;

    QuadTree.prototype.refresh = function(items){
        this.clear();
        this.insertList(items);
    }
    QuadTree.prototype.insert = function (item) {
        if (item instanceof Array) {
            var len = item.length;

            var i;
            for (i = 0; i < len; i++) {
                this.root.insert(item[i]);
            }
        } else {
            this.root.insert(item);
        }
    };
    QuadTree.prototype.insertList = function (items) {
        var keys = Object.keys(items);
        var len = keys.length;

        var i;
        for (i = 0; i < len; i++) {
            this.root.insert(items[keys[i]]);
        }
       
    };
    QuadTree.prototype.delete = function (item) {
        if (item instanceof Array) {
            var len = item.length;

            var i;
            for (i = 0; i < len; i++) {
                this.root.delete(item[i]);
            }
        } else {
            this.root.delete(item);
        }
    };
    QuadTree.prototype.updateTreePosition = function(item){
        if (item instanceof Array) {
            var len = item.length;

            var i;
            for (i = 0; i < len; i++) {
                if(!inBound(item[i])){
                //if(true){
                    this.delete(item[i]);
                    this.insert(item[i]);
                }
            }
        } else {
            if(!inBound(item)){
            //if(true){
                this.delete(item);
                this.insert(item);
            }
        }
    }
    QuadTree.prototype.clear = function () {
        this.root.clear();
    };

    QuadTree.prototype.retrieve = function (item) {
        var out = this.root.retrieve(item).slice(0);
        return out;
    };
    QuadTree.prototype._retrieve = function (item) {
        var output = [];
        this.root._retrieve(output,item);
        return output;
    };
    QuadTree.prototype.print = function(){
        console.log(this);
        this.root.print();

    }
    /************** Node ********************/


    function Node(bounds, depth, maxDepth, maxChildren) {
        this._bounds = bounds;
        this.children = [];
        this.nodes = [];

        if (maxChildren) {
            this._maxChildren = maxChildren;
        }

        if (maxDepth) {
            this._maxDepth = maxDepth;
        }

        if (depth) {
            this._depth = depth;
        }
    }

    Node.prototype.nodes = null;
    Node.prototype._classConstructor = Node;

    Node.prototype.children = null;
    Node.prototype._bounds = null;

    Node.prototype._depth = 0;

    Node.prototype._maxChildren = 4;
    Node.prototype._maxDepth = 4;

    Node.TOP_LEFT = 0;
    Node.TOP_RIGHT = 1;
    Node.BOTTOM_LEFT = 2;
    Node.BOTTOM_RIGHT = 3;


    Node.prototype.insert = function (item) {
        if (this.nodes.length) {
            var index = this._findIndex(item);

            this.nodes[index].insert(item);

            return;
        }

        this.children.push(item);

        var len = this.children.length;
        if (!(this._depth >= this._maxDepth) &&
                len > this._maxChildren) {
            
            this.subdivide();

            var i;
            for (i = 0; i < len; i++) {
                this.insert(this.children[i]);
            }

            this.children.length = 0;
        }
        else{
            item._bounds = this._bounds;
        }
    };
    Node.prototype.delete = function (item) {
        if (this.nodes.length) {
            var index = this._findIndex(item);

            this.nodes[index].delete(item);

        }
        this.children = this.children.filter(function(value, index, arr){

            return value.id != item.id;
        });
    };

    Node.prototype.retrieve = function (item) {
        if (this.nodes.length) {
            var index = this._findIndex(item);

            return this.nodes[index].retrieve(item);
        }

        return this.children;
    };
    Node.prototype._retrieve = function (output,item) {
        if (this.nodes.length) {
            var index = this._findIndex(item);

            this.nodes[index]._retrieve(output,item);
        }
        output.push.apply(output, this.children);
    };
    Node.prototype._findIndex = function (item) {
        var b = this._bounds;
        var left = (getX(item) > b.x + b.width / 2) ? false : true;
        var top = (getY(item) > b.y + b.height / 2) ? false : true;

        var index = Node.TOP_LEFT;
        if (left) {
            if (!top) {
                index = Node.BOTTOM_LEFT;
            }
        } else {
            if (top) {
                index = Node.TOP_RIGHT;
            } else {
                index = Node.BOTTOM_RIGHT;
            }
        }

        return index;
    };


    Node.prototype.subdivide = function () {
        var depth = this._depth + 1;

        var bx = this._bounds.x;
        var by = this._bounds.y;

        //floor the values
        var b_w_h = (this._bounds.width / 2); 
        var b_h_h = (this._bounds.height / 2);
        var bx_b_w_h = bx + b_w_h;
        var by_b_h_h = by + b_h_h;

        this.nodes[Node.TOP_LEFT] = new this._classConstructor({
            x: bx,
            y: by,
            width: b_w_h,
            height: b_h_h
        },
            depth, this._maxDepth, this._maxChildren);

        this.nodes[Node.TOP_RIGHT] = new this._classConstructor({
            x: bx_b_w_h,
            y: by,
            width: b_w_h,
            height: b_h_h
        },
            depth, this._maxDepth, this._maxChildren);

        this.nodes[Node.BOTTOM_LEFT] = new this._classConstructor({
            x: bx,
            y: by_b_h_h,
            width: b_w_h,
            height: b_h_h
        },
            depth, this._maxDepth, this._maxChildren);


        this.nodes[Node.BOTTOM_RIGHT] = new this._classConstructor({
            x: bx_b_w_h,
            y: by_b_h_h,
            width: b_w_h,
            height: b_h_h
        },
            depth, this._maxDepth, this._maxChildren);
    };

    Node.prototype.clear = function () {
        this.children.length = 0;

        var len = this.nodes.length;
        
        var i;
        for (i = 0; i < len; i++) {
            this.nodes[i].clear();
        }

        this.nodes.length = 0;
    };
    
    Node.prototype.print = function(){
        console.log(this);
        console.log("children : ");
        for(var i = 0; i< this.children.length;i++){
            console.log(this.children[i]);
        }
        console.log("subnodes : ");
        for(var i = 0; i< this.nodes.length;i++){
            this.nodes[i].print();
        }
    }
    /******************** BoundsQuadTree ****************/

    function BoundsNode(bounds, depth, maxChildren, maxDepth) {
        Node.call(this, bounds, depth, maxChildren, maxDepth);
        this._stuckChildren = [];
    }

    BoundsNode.prototype = new Node();
    BoundsNode.prototype._classConstructor = BoundsNode;
    BoundsNode.prototype._stuckChildren = null;

    BoundsNode.prototype._out = [];

    BoundsNode.prototype.insert = function (item) {
        if (this.nodes.length) {
            var index = this._findIndex(item);
            var node = this.nodes[index];

            if (getX(item) >= node._bounds.x &&
                    getX(item) + item.width <= node._bounds.x + node._bounds.width &&
                    getY(item) >= node._bounds.y &&
                    getY(item) + item.height <= node._bounds.y + node._bounds.height) {
                
                this.nodes[index].insert(item);
                
            } else {
                this._stuckChildren.push(item);
                item._bounds = this._bounds;
            }

            return;
        }

        this.children.push(item);

        var len = this.children.length;

        if (!(this._depth >= this._maxDepth) &&
                len > this._maxChildren) {
            
            this.subdivide();

            var i;
            for (i = 0; i < len; i++) {
                this.insert(this.children[i]);
            }

            this.children.length = 0;
        }
        else{
            item._bounds = this._bounds;
        }
    };
    BoundsNode.prototype.delete = function (item) {
        if (this.nodes.length) {
            var index = this._findIndex(item);
            var node = this.nodes[index];

            if (getX(item) >= node._bounds.x &&
                    getX(item) + item.width <= node._bounds.x + node._bounds.width &&
                    getY(item) >= node._bounds.y &&
                    getY(item) + item.height <= node._bounds.y + node._bounds.height) {
                
                this.nodes[index].delete(item);
                
            } else {
                this._stuckChildren = this._stuckChildren.filter(function(value, index, arr){
                    return value.id != item.id;
                });
            }

        }
        this._stuckChildren = this._stuckChildren.filter(function(value, index, arr){
            return value.id != item.id;
        });
        this.children= this.children.filter(function(value, index, arr){
            return value.id != item.id;
        });
    };

    BoundsNode.prototype.getChildren = function () {
        return this.children.concat(this._stuckChildren);
    };

    BoundsNode.prototype.retrieve = function (item) {
        var out = this._out;
        out.length = 0;
        if (this.nodes.length) {
            var index = this._findIndex(item);
            var node = this.nodes[index];

            if (getX(item) >= node._bounds.x &&
                    getX(item) + item.width <= node._bounds.x + node._bounds.width &&
                    getY(item) >= node._bounds.y &&
                    getY(item) + item.height <= node._bounds.y + node._bounds.height) {
                
                out.push.apply(out, this.nodes[index].retrieve(item));
            } else {

                if (getX(item) <= this.nodes[Node.TOP_RIGHT]._bounds.x) {
                    if (getY(item) <= this.nodes[Node.BOTTOM_LEFT]._bounds.y) {
                        out.push.apply(out, this.nodes[Node.TOP_LEFT].getAllContent());
                    }
                    
                    if (getY(item) + item.height > this.nodes[Node.BOTTOM_LEFT]._bounds.y) {
                        out.push.apply(out, this.nodes[Node.BOTTOM_LEFT].getAllContent());
                    }
                }
                
                if (getX(item) + item.width > this.nodes[Node.TOP_RIGHT]._bounds.x) {
                    if (getY(item) <= this.nodes[Node.BOTTOM_RIGHT]._bounds.y) {
                        out.push.apply(out, this.nodes[Node.TOP_RIGHT].getAllContent());
                    }
                    
                    if (getY(item) + item.height > this.nodes[Node.BOTTOM_RIGHT]._bounds.y) {
                        out.push.apply(out, this.nodes[Node.BOTTOM_RIGHT].getAllContent());
                    }
                }
            }
        }

        out.push.apply(out, this._stuckChildren);
        out.push.apply(out, this.children);

        return out;
    };
    BoundsNode.prototype._retrieve = function (output,item) {
        if (this.nodes.length) {
            var index = this._findIndex(item);
            var node = this.nodes[index];

            if (getX(item) >= node._bounds.x &&
                    getX(item) + item.width <= node._bounds.x + node._bounds.width &&
                    getY(item) >= node._bounds.y &&
                    getY(item) + item.height <= node._bounds.y + node._bounds.height) {
                this.nodes[index]._retrieve(output,item);
            } else {

                if (getX(item) <= this.nodes[Node.TOP_RIGHT]._bounds.x) {
                    if (getY(item) <= this.nodes[Node.BOTTOM_LEFT]._bounds.y) {
                        var items = [];this.nodes[Node.TOP_LEFT].getAllItems(items);
                        output.push.apply(output, items);
                    }
                    
                    if (getY(item) + item.height > this.nodes[Node.BOTTOM_LEFT]._bounds.y) {
                        var items = [];this.nodes[Node.BOTTOM_LEFT].getAllItems(items);
                        output.push.apply(output, items);
                    }
                }
                
                if (getX(item) + item.width > this.nodes[Node.TOP_RIGHT]._bounds.x) {
                    if (getY(item) <= this.nodes[Node.BOTTOM_RIGHT]._bounds.y) {
                        var items = [];this.nodes[Node.TOP_RIGHT].getAllItems(items);
                        output.push.apply(output, items);
                    }
                    
                    if (getY(item) + item.height > this.nodes[Node.BOTTOM_RIGHT]._bounds.y) {
                        var items = [];this.nodes[Node.BOTTOM_RIGHT].getAllItems(items);
                        output.push.apply(output, items);
                    }
                }
            }
        }

        output.push.apply(output, this._stuckChildren);
        output.push.apply(output, this.children);

    };
    BoundsNode.prototype.getAllContent = function () {
        var out = this._out;
        if (this.nodes.length) {
            
            var i;
            for (i = 0; i < this.nodes.length; i++) {
                this.nodes[i].getAllContent();
            }
        }
        out.push.apply(out, this._stuckChildren);
        out.push.apply(out, this.children);
        return out;
    };
    BoundsNode.prototype.getAllItems = function (output){
        output.push.apply(output, this.children);
        output.push.apply(output, this._stuckChildren);
        for(var i = 0; i< this.nodes.length;i++){
            this.nodes[i].getAllItems(output);
        }
    }
    BoundsNode.prototype.clear = function () {

        this._stuckChildren.length = 0;

        //array
        this.children.length = 0;

        var len = this.nodes.length;

        if (!len) {
            return;
        }

        var i;
        for (i = 0; i < len; i++) {
            this.nodes[i].clear();
        }

        //array
        this.nodes.length = 0;

    };
    BoundsNode.prototype.print = function(){
        console.log(this);
        console.log("children : ");
        for(var i = 0; i< this.children.length;i++){
            console.log(this.children[i]);
        }
        console.log("_stuckChildren : ");
        for(var i = 0; i< this._stuckChildren.length;i++){
            console.log(this._stuckChildren[i]);
        }
        console.log("subnodes : ");
        for(var i = 0; i< this.nodes.length;i++){
            this.nodes[i].print();
        }
    }
bound = {
    x:0,
    y:0,
    height:100,
    width:100
}
var inBound = function(item){
    return (getX(item) >= item._bounds.x &&
                    getX(item) + item.width <= item._bounds.x + item._bounds.width &&
                    getY(item) >= item._bounds.y &&
                    getY(item) + item.height <= item._bounds.y + item._bounds.height);
}