先上一张鬼畜图，图为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
网友评论