碰撞检测性能优化：四叉树碰撞检测
Author：zhoulujun Date：
上篇 《碰撞检测一文讲透：多边形碰撞检测有哪些方法？》讲过如何做碰撞检测，但是当要检测的图形非常多的时候，就嘎了
那么，如何做碰撞检测性能优化呢？比如：
场景中有500个矩形，要进行碰撞检测，普通的检测就是遍历一遍小球数组，两两进行碰撞检测。
这种方式需要遍历每一个小球，造成大量的计算。500个小球需要进行499500次碰撞检测，消耗时间大约10-11毫秒。
划分区域进行碰撞检测(四叉树)
将场景划为为不同区域，小球只和自己同一区域的小球进行碰撞检测，这样可以大量减少碰撞次数。
这种方式需要额外计算每个小球属于哪一个区域，但是对比碰撞检测的消耗，还是比较节省效率的。
二叉树、四叉树、八叉树
二叉树：树形结构，每个节点最多2个子树。
四叉树：树状数据结构，每个节点有四个子区块。
八叉树：描述三维空间的树状结构，任意子节点有0或8个。
2D中是四叉树，3D中则对应的为八叉树，具体可以拜读：《空间管理Space management：四叉树 & 八叉树 》
四叉树本质使用了 空间分割，给图形加 索引，将视口界面分割成多个区域，每个区域记住自己包含了哪些图形。
然后移动目标图形时，判断它落在哪个区域，取出所在区域的图形，这些图形集合就是和目标图形发生碰撞图形的超集。
这些区域外的图形就被我们排除了。
四叉树碰撞检测算法
遍历小球列表ballList，计算小球所在格子的行列值，将小球保存到对应的格子列表中。
for (let i = 0; i < this.ballList.length; i++) {
let ball = this.ballList[i];
let row = Math.floor((ball.node.y + this.maxHeight) / this.gridSize);
let col = Math.floor((ball.node.x + this.maxWidth) / this.gridSize);
ball.row = row;
ball.col = col;
this.gridList[row][col].push(ball);
}遍历小球列表ballList，根据小球的行列值row、col可以从格子gridLsit中获取同一区域的小球。每个小球只和自己同一区域的小球进行碰撞检测。
for (let i = 0; i < this.ballList.length; i++) {
let ballA = this.ballList[i];
let list = this.gridList[ballA.row][ballA.col];
for (let j = 0; j < list.length; j++) {
let ballB = list[j];
if (ballA != ballB) {
if (this.rectRect(ballA.node, ballB.node)) {
console.log("碰撞");
}
}
}
}这个前辈们已经实现好了一个公共库：https://github.com/timohausmann/quadtree-js
其他空间分割思想的算法
简单介绍一些也使用了 空间分割 思想的算法。
跳表：一种有序链表，通过叠加大量的索引层，可以进行链表形式的 “二分查找”，达到高效的
O(logn)时间复杂度，但也带来了内存的消耗。Redis 中的有序集合（Sorted Set）底层使用了跳表，一个原因是可以高效地获取区间内的数据集；B+ 树：一种平衡二叉树，有点像跳表，但树的层数最多为三层，MySQL 的索引实现使用了 B+ 树，因为层数较少，可以减少 IO 操作；
R 树：R 表示矩形的意思。相比前面两种单维的范围查找，R 树能做高效的高维查找。比如地图中，我们可以通过 R 树将 距离 相近的高维图形合并为一个大节点，当搜索 “2km 内的药店” 时，如果你落到某个大节点上，我们只要遍历一个大节点下的所有节点，而不是遍历整个市，或整个国家。
R 树的思路是最接近四叉树的，它其实是另一种 减少图形遍历的方案，可以适用于高效剔除视口范围之外的图形。
参考：
【算法】四叉树和碰撞检测 https://www.cnblogs.com/gamedaybyday/p/16673206.html
游戏编程模式-空间分区 https://www.cnblogs.com/xin-lover/p/12216053.html
冰冰教你用“四叉树”手写“碰撞检测”，太感动了！ https://cloud.tencent.com/developer/article/1658411
快速检索碰撞图形：四叉树碰撞检测 https://juejin.cn/post/7179409799228948537
转载本站文章《碰撞检测性能优化：四叉树碰撞检测》,
请注明出处：https://www.zhoulujun.cn/html/theory/Mathematics/Geometry/9233.html