先上一张鬼畜图，图为1000个单位的碰撞检测，中间的头像单位可以吃掉碰到他的单位
最近看到一篇不错的文章，学习了一点四叉图的知识，感觉终于可以做游戏了，来这做个笔记。

Q-tree

先上一段维基百科的简介：
四元樹又稱四叉樹是一種樹狀資料結構，在每一個節點上會有四個子區塊。四元樹常應用於二維空間資料的分析與分類。 它將資料區分成為四個象限。資料範圍可以是方形或矩形或其他任意形狀。這種資料結構是由 拉斐爾·芬科爾(Raphael Finkel) 與 J. L. Bentley 在1974年發展出來 。 類似的資料分割方法也稱為 Q-tree。 所有的四元樹法有共同之特點:
可分解成為各自的區塊
每个区块都有节点容量。当节点达到最大容量时，节点分裂
樹狀資料結構依造四元樹法加以區分

有没有觉得不明觉厉，来看图

想要实现物体碰撞的检测其实很简单，两层遍历判断就可以了，但是物体单元数量太多的时候 O n^2的计算压力就很明显暴露了。所以就需要一个算法来降低找到两个可能碰撞的物体的成本。

迭代划分屏幕为四个象限区域

四叉树原理 正如其名，四叉树就是每个父节点都具有四个子节点的树状数据结构。由于要区分屏幕上的物体，我们要将屏幕划分为四个区域，所以四叉树的四个节点正合适表示这四个区域。
我们需要设定一个象限内容纳最多单元的阀值，如果超过该值，就继续分列生成4个子节点，来将这些单元放在它的子象限内。

这里的代码是根据 这里 用了ES6修改了一部分

/*
 四叉树节点包含： 
- objects: 用于存储物体对象 
- nodes: 存储四个子节点
 - level: 该节点的深度，根节点的默认深度为0 
- bounds: 该节点对应的象限在屏幕上的范围，bounds是一个矩形
*/
class QuadTree {
            constructor (bounds, level = 0) {
                this.objects = []
                this.nodes = []
                this.level = level
                this.bounds = bounds
                this.MAX_OBJECTS = 10
                this.MAX_LEVELS = 5
            }
}

判断物体是在那个象限内，之后的检索 插入等功能都会调用这个方法

getIndex (rect, checkIsInner) {
                let bounds = this.bounds
                let onTop = rect.y + rect.h <=  bounds.cY
                let onBottom = rect.y >= bounds.cY
                let onLeft = rect.x + rect.w <= bounds.cX
                let onRight = rect.x >= bounds.cX

                // 检测矩形是否溢出象限界限
                if (checkIsInner &&
                    (Math.abs(rect.cX - bounds.cX) + rect.sWidth > bounds.sWidth ||
                    Math.abs(rect.cY - bounds.cY) + rect.sHeight > bounds.sHeight)) {

                    return -1
                }

                if (onTop) {
                    if (onRight) {
                        return 0
                    } else if (onLeft) {
                        return 1
                    }
                } else if (onBottom) {
                    if (onLeft) {
                        return 2
                    } else if (onRight) {
                        return 3
                    }
                }

                return -1
            }

插入功能：

• 如果当前节点[ 存在 ]子节点，则检查物体到底属于哪个子节点，如果能匹配到子节点，则将该物体插入到该子节点中
• 如果当前节点[ 不存在 ]子节点，将该物体存储在当前节点。随后，检查当前节点的存储数量，如果超过了最大存储数量，则对当前节点进行划分，划分完成后，将当前节点存储的物体重新分配到四个子节点中。

insert (rect) {
                let objs = this.objects
                let index

                if (this.nodes.length) {
                    index = this.getIndex(rect)
                    if (index !== -1) {
                        this.nodes[index].insert(rect)
                        return
                    }
                }
                objs.push(rect)

                if (!this.nodes.length &&
                    this.objects.length > this.MAX_OBJECTS &&
                    this.level < this.MAX_LEVELS) {

                    this.split()

                    for (let i = objs.length - 1; i >= 0; i--) {
                        index = this.getIndex(objs[i])
                        if (index !== -1) {
                            this.nodes[index].insert(objs.splice(i, 1)[0])
                        }
                    }
                }
            }

生成子象限

            split () {
                let level = this.level
                let bounds = this.bounds
                let x = bounds.x
                let y = bounds.y
                let sWidth = bounds.sWidth
                let sHeight = bounds.sHeight
                this.nodes.push(
                    new QuadTree(new Area(bounds.cX, y, sWidth, sHeight), level + 1),
                    new QuadTree(new Area(x, y, sWidth, sHeight), level + 1),
                    new QuadTree(new Area(x, bounds.cY, sWidth, sHeight), level + 1),
                    new QuadTree(new Area(bounds.cX, bounds.cY, sWidth, sHeight), level + 1)
                )
            }

检索功能：

给出一个物体对象，该函数负责将该物体可能发生碰撞的所有物体选取出来。该函数先查找物体所属的象限，该象限下的物体都是有可能发生碰撞的，然后再递归地查找子象限

            retrieve (rect) {
                let result = []
                let arr
                let i
                let index

                if (this.nodes.length) {
                    index = this.getIndex(rect)
                    if (index !== -1) {
                        result = result.concat(this.nodes[index].retrieve(rect))
                    } else {
                        // 切割矩形
                        arr = rect.carve(this.bounds)
                        
                        for (i = arr.length - 1; i >= 0; i--) {
                            index = this.getIndex(arr[i])
                            result = result.concat(this.nodes[index].retrieve(rect))
                        }
                    }
                }

                return result.concat(this.objects)
            }

动态刷新

从根节点深入四叉树，检查四叉树各个节点存储的物体是否依旧属于该节点（象限）的范围之内，如果不属于，则重新插入该物体。
有没一点Visual Dom的感觉，（笑

            refresh (root) {
                let objs = this.objects
                let index
                let i
                let len

                root = root || this

                for (i = objs.length - 1; i >= 0; i--) {
                    if (objs[i].destroy) {
                        objs.splice(i, 1)
                    } else {
                        index = this.getIndex(objs[i], true)
                        if (index === -1) {
                            if (this !== root) {
                                root.insert(objs.splice(i, 1)[0])
                            }
                        } else if (this.nodes.length) {
                            this.nodes[index].insert(objs.splice(i, 1)[0])
                        }
                    }
                }

                for (i = 0, len = this.nodes.length; i < len; i++) {
                    this.nodes[i].refresh(root)
                }
            }

参考资历：
https://zh.wikipedia.org/zh/%E5%9B%9B%E5%8F%89%E6%A0%91
http://blog.lxjwlt.com/front-end/2014/09/04/quadtree-for-collide-detection.html