长话短说

1.Define Quad Tree

四叉树的作用就是从原点开始根据一定的范围画出周围的四个象限，然后每个子象限继续划分为四个孙子象限，以此类推，到达递归深度最大值时停止。

2.在碰撞检测中的作用

如果场景里有1万个障碍物和2个子弹，那么子弹需要和每个障碍物进行一次碰撞检测，复杂度Omn。而我们进行了空间划分之后，只需要将子弹与其所在的区域内的障碍物进行检测即可，复杂度Omlogn。 相当于将碰撞检测分成了两部分，第一部分（粗测）尽可能将不会碰到的物体扔掉，从所有的物体中筛选出与子弹最接近最可能碰到的物体，第二部分（精测）使用尽可能精确的碰撞检测公式去检测是否碰撞，简单的有几行代码就能写出来的简单几何体碰撞，复杂的有GJK算法等。

3.Unity中的实现

如果把二分查找的每个步骤都存储起来，那么最终的结果看起来就像是一个二叉树，那么可以参考二分查找的步骤去创建。

3.1.设计

类名作用Obstacle障碍物QTree四叉树集合的封装类QNode四叉树的每个节点Bound包围盒，定义物体的碰撞体积，这里用的无旋转矩形

需要的初始化参数：

参数每个节点内最大物体数量四叉树坐标和大小四叉树的最大递归深度

3.2 坑

3.2.1 边界问题

如果一个物体正好脚踩N个象限，如何对敌？ 两种方法，1.脚踩的每个象限都存储该物体的索引，好处是分的清楚，检测的效率高，但缺点是不好管理，因为这样会产生一大堆同样的索引，占内存。2.将该物体交给能完整的包住该物体的父节点，优点是号管理，每个物体都只属于一个节点，但缺点是，举个例子，如果有个比较小的物体正好在四叉树根节点的中心位置，那么任何要进行碰撞检测的物体都要与该物体检测，增加了许多无用的检测，效率低。 我选的第二个方法，因为我觉得游戏中需要移动的碰撞体相比静态物体还是少数，可以通过提前手动修改静态物体位置的方法尽量减少效率低的问题。

3.2.2 动态更新

假设最坏的情况，场景中的每个碰撞体都是移动的，那么问题来了，怎么更新呢？很好理解，删除+插入。但是每一帧重建整个四叉树显然是不现实的，所以这里面有很多优化的trick，比如只更新可能移动的物体；比如只搜索原物体附近的区域，进行删除和插入，但是这样解决不了闪现的问题；或者将物体新坐标与旧坐标检测是否在同一区域的方法来剪枝，等等。 本文暂时不考虑优化。

3.2.3 单个插入和集体插入的不一致

这个是我自己造的词和坑。 举个例子，假如有100个障碍物，每个节点最多存1个，如果是一起插入四叉树，那么根节点大概率是不存物体的，因为有100个障碍物都可以插入根节点，早就超出单个节点的最大容量了。而单个插入就不同了，你在插入时并不知道其他节点的信息，那么第一个插入的物体一定就在根节点。 不过我感觉这两者区别的影响也并不是很大。

3.3 思路

3.3.1 创建四叉树

拿到要插入的物体的集合后 (1).计算该节点四个象限内和跨象限的物体 (2).(1)如果全部节点个数小于节点最大物体个数或者到达最大递归深度，直接全部存到该节点中 (2).(2)否则跨象限的物体存到该节点中，而四个象限的物体传入四个子节点的构造函数中。

3.3.2 检索

(1).遍历节点内的所有物体，进行碰撞检测 (2).如果节点为空，检查该物体在该节点的哪个象限，递归的去找该象限的所属节点

3.3.2 删除

(1).从物体的所属节点中删除该物体 (2).如果该物体的所属节点内没有物体且该节点没有子节点，则删除该节点。 (3).递归的检查该节点的父节点是否需要删除

3.3.3 插入

(1).(1)遇到最大深度的节点或者该节点内的物体未到达最大容量，直接插入该节点 (1).(2)否则，仿照创建四叉树的套路

3.4 代码

using System; using System.Collections; using System.Collections.Generic; using System.Linq; using UnityEngine; public enum QTNodeType { /// <summary> /// 左上 /// </summary> LT = 0, /// <summary> /// 右上 /// </summary> RT = 1, /// <summary> /// 右下 /// </summary> RB = 2, /// <summary> /// 左下 /// </summary> LB = 3, /// <summary> /// 根节点 /// </summary> Root = 4, } public class Bound { public float X; public float Y; public float Width; public float Height; public Bound(float x, float y, float w,float h) { X = x; Y = y; Width = w; Height = h; } public static bool CheckCollision(Bound b1, Bound b2) { float[] rec1 = { b1.X - b1.Width / 2, b1.Y - b1.Height / 2, b1.X + b1.Width / 2, b1.Y + b1.Height / 2, }; float[] rec2 = { b2.X - b2.Width / 2, b2.Y - b2.Height / 2, b2.X + b2.Width / 2, b2.Y + b2.Height / 2, }; return !(rec1[2] <= rec2[0] || rec2[2] <= rec1[0] || rec1[3] <= rec2[1] || rec2[3] <= rec1[1]); } } public class QTree { public int MaxObjCnt; public int MaxDepth; public QNode Root; public Bound Bound; public List<Obstacle> ObjList; public QTree(List<Obstacle> objList,Bound bound,int maxObjCnt,int maxDepth) { this.MaxObjCnt = maxObjCnt; this.ObjList = objList; this.MaxDepth = maxDepth; Bound = bound; Root = new QNode(objList,Bound, 0,Root, this,QTNodeType.Root); } public void RenderTree() { Root.RenderNode(); } public void SearchNode(Bullet bullet) { Root.SearchNode(bullet); } public void InsertObj(Obstacle obj) { Root.InsertObj(obj); } public void DeleteObj(Obstacle obj) { obj.BelongedNode.DeleteObj(obj); } public void UpdateObj(Obstacle obj) { // 删除后重新插入 DeleteObj(obj); InsertObj(obj); } } public class QNode { private QTNodeType Type; private QTree BelongedTree; private Bound Bound; private int Depth; private List<Obstacle> ObjList; private QNode Father; private List<QNode> ChildList; public QNode(List<Obstacle> intersectionObjs, Bound bound, int depth, QNode father, QTree qTree, QTNodeType type) { this.Bound = bound; this.Depth = depth; this.Father = father; this.BelongedTree = qTree; this.Type = type; ObjList = new List<Obstacle>(); ChildList = new List<QNode>(); List<Obstacle> _LTlist = new List<Obstacle>(); List<Obstacle> _RTlist = new List<Obstacle>(); List<Obstacle> _RBlist = new List<Obstacle>(); List<Obstacle> _LBlist = new List<Obstacle>(); List<Obstacle> _Rootlist = new List<Obstacle>(); List<List<Obstacle>> _AllLists = new List<List<Obstacle>> { _LTlist, _RTlist, _RBlist, _LBlist, _Rootlist }; foreach (Obstacle obj in intersectionObjs) { if (obj.isLoaded == false) { #region 检测物体与几个子节点相交 List<bool> _blist = new List<bool> { CheckIntersection(obj.Bound, QTNodeType.LT), CheckIntersection(obj.Bound, QTNodeType.RT), CheckIntersection(obj.Bound, QTNodeType.RB), CheckIntersection(obj.Bound, QTNodeType.LB) }; int _intersectionTimes = 0; foreach (bool b in _blist) _intersectionTimes += b ? 1 : 0; #endregion #region 该物体穿过多个子节点 if (_intersectionTimes >= 2) { _Rootlist.Add(obj); } #endregion #region 完全在某个子节点内 else if (_intersectionTimes==1) { for (int i = 0; i < 4; i++) if (_blist[i]) { _AllLists[i].Add(obj); break; } } #endregion else throw new Exception("正在检测父节点外的物体"); } } int _totalCnt = 0; foreach (List<Obstacle> list in _AllLists) _totalCnt += list.Count(); if (_totalCnt <= BelongedTree.MaxObjCnt || Depth >= BelongedTree.MaxDepth) { #region 直接全部放入父节点 foreach (List<Obstacle> list in _AllLists) foreach (Obstacle obj in list) { AddObj(obj); } #endregion } else { #region 父节点物体放入根节点，子节点物体继续向下递归 foreach (Obstacle obj in _Rootlist) { AddObj(obj); } #region 递归创建四个节点 for (int i = 0; i < 4; i++) { if (_AllLists[i].Count() != 0) { QTNodeType _type = (QTNodeType)i; ChildList.Add(new QNode(_AllLists[i], GenBound(_type), depth + 1, this, BelongedTree, _type)); } } #endregion #endregion } } public QNode(Bound bound, int depth, QNode father, QTree qTree, QTNodeType type) { this.Bound = bound; this.Depth = depth; this.Father = father; this.BelongedTree = qTree; this.Type = type; ObjList = new List<Obstacle>(); ChildList = new List<QNode>(); } public void RenderNode() { foreach (QNode node in ChildList) { node.RenderNode(); } Gizmos.DrawWireCube(new Vector3(Bound.X, 0, Bound.Y), new Vector3(Bound.Width,0, Bound.Height)); } public void SearchNode(Bullet bullet) { if (ObjList.Count() != 0 && CheckPointInside(bullet.Bound, QTNodeType.Root)) { // 检查每次递归遇到的节点内的物体（非叶子节点内为交叉物体，叶子节点内为非交叉物体） // 在这里检查碰撞 for (int i = 0;i<ObjList.Count;i++) { ObjList[i].HighLightObs = true; if (Bound.CheckCollision(bullet.Bound, ObjList[i].Bound)) { ObjList[i].DestroySelf(); bullet.DestroySelf(); return; } } } // 找不到就从最可能的子节点入手继续递归的找 foreach (QNode qNode in ChildList) { if (CheckPointInside(bullet.Bound, qNode.Type)) { qNode.SearchNode(bullet); return; } } } public void InsertObj(Obstacle obj) { // 遇到最大深度的叶子，直接添加，不再递归 if (Depth == BelongedTree.MaxDepth||ObjList.Count()<BelongedTree.MaxObjCnt) { AddObj(obj); return; } #region 检测与节点的几个子节点相交 List<bool> _bList = new List<bool> { CheckIntersection(obj.Bound, QTNodeType.LT), CheckIntersection(obj.Bound, QTNodeType.RT), CheckIntersection(obj.Bound, QTNodeType.RB), CheckIntersection(obj.Bound, QTNodeType.LB) }; int _intersectionTimes = 0; foreach (bool b in _bList) _intersectionTimes += b ? 1 : 0; if (_intersectionTimes >= 2) //要添加的物体与多个子节点相交 { // 直接加入父节点 AddObj(obj); return; } else if (_intersectionTimes == 1) // 在子节点的位置内 { QNode _node; for (int i = 0; i < 4; i++) { if (_bList[i]) { QTNodeType _type = (QTNodeType)i; _node = GetNode((QTNodeType)i); if (_node == null) { _node = new QNode(GenBound(_type), Depth + 1, this, BelongedTree, _type); ChildList.Add(_node); _node.AddObj(obj); } else { _node.InsertObj(obj); } } } } else throw new Exception("该物体不在树的范围内"); #endregion } public void DeleteObj(Obstacle obj) { obj.BelongedNode = null; ObjList.Remove(obj); QNode qNode = this; // 该节点无物体且无叶子，即删除 while (qNode.ObjList.Count() == 0 && qNode.ChildList.Count() == 0) { QNode _deleteNode = qNode; qNode = qNode.Father; _deleteNode.Father.ChildList.Remove(_deleteNode); } } public Vector2 GetPos() { return new Vector3(Bound.X,Bound.Y); } public Vector2 GetSize() { return new Vector2(Bound.Width, Bound.Height); } private Bound GenLT() { return new Bound(Bound.X - Bound.Width / 4, Bound.Y + Bound.Height / 4, Bound.Width / 2, Bound.Height / 2); } private Bound GenRT() { return new Bound(Bound.X + Bound.Width / 4, Bound.Y + Bound.Height / 4, Bound.Width / 2, Bound.Height / 2); } private Bound GenRB() { return new Bound(Bound.X + Bound.Width / 4, Bound.Y - Bound.Height/ 4, Bound.Width / 2, Bound.Height / 2); } private Bound GenLB() { return new Bound(Bound.X - Bound.Width / 4, Bound.Y - Bound.Height / 4, Bound.Width / 2, Bound.Height / 2); } private Bound GenBound(QTNodeType type) { switch (type) { case QTNodeType.LT:return GenLT(); case QTNodeType.RT:return GenRT(); case QTNodeType.RB:return GenRB(); case QTNodeType.LB:return GenLB(); default:throw new Exception("不支持的type类型"); } } private bool CheckIntersection(Bound b,QTNodeType type) { Bound _nb; switch (type) { case QTNodeType.LT: _nb = GenLT(); break; case QTNodeType.RT: _nb = GenRT(); break; case QTNodeType.RB: _nb = GenRB(); break; case QTNodeType.LB: _nb = GenLB(); break; default: throw new NotImplementedException("未指定的QTNodeType"); } float[] rec1 = {b.X - b.Width / 2,b.Y - b.Height / 2,b.X + b.Width / 2,b.Y + b.Height / 2,}; float[] rec2 = {_nb.X - _nb.Width / 2,_nb.Y - _nb.Height / 2,_nb.X + _nb.Width / 2,_nb.Y + _nb.Height / 2,}; return !(rec1[2] <= rec2[0] || rec2[2] <= rec1[0] || rec1[3] <= rec2[1] || rec2[3] <= rec1[1]); } private bool CheckPointInside(Bound b, QTNodeType type) { switch (type) { case QTNodeType.Root: return (b.X < Bound.X + Bound.Width / 2) && (b.X > Bound.X - Bound.Width / 2) && (b.Y < Bound.Y + Bound.Height / 2) && (b.Y > Bound.Y - Bound.Height / 2); case QTNodeType.LB: return (b.X < Bound.X) && (b.X > Bound.X - Bound.Width / 2) && (b.Y < Bound.Y) && (b.Y > Bound.Y - Bound.Height / 2); case QTNodeType.LT: return (b.X < Bound.X) && (b.X > Bound.X - Bound.Width / 2) && (b.Y < Bound.Y + Bound.Height / 2) && (b.Y > Bound.Y); case QTNodeType.RB: return (b.X < Bound.X + Bound.Width / 2) && (b.X > Bound.X) && (b.Y < Bound.Y) && (b.Y > Bound.Y - Bound.Height / 2); case QTNodeType.RT: return (b.X < Bound.X + Bound.Width / 2) && (b.X > Bound.X) && (b.Y < Bound.Y + Bound.Height / 2) && (b.Y > Bound.Y); default: throw new NotImplementedException("未指定的QTNodeType"); } } private QNode GetNode(QTNodeType type) { foreach (QNode node in ChildList) { if (node.Type == type) { return node; } } return null; } private void AddObj(Obstacle obj) { ObjList.Add(obj); obj.isLoaded = true; obj.BelongedNode = this; } }

四.结果

五.参考

空间划分的数据结构(四叉树/八叉树/BVH树/BSP树/k-d树) 【物理篇】从零搭建2D物理系统②——用松散四叉树结合网格法来划分场景 空间索引-四叉树的实现及其应用