Unity八叉树及导航

树的组织特点：一种只有唯一的上级和若干下级的概念结构。

对于八叉树来说则是：只有唯一的上级和最多八个下级，而在本例中，下级节点的数量只会为0(null)或8。

声明：

请确保看完了视频，我会直接讲解我的改动与添加。

0.有物体的区域，Draw的线框改色

1.物体位移重建线框(树的数据)

2.通过点的坐标得到其所在的小区块

3.导航

改色

在OctreeNode的DivideAndAdd方法中

这个if只有在递归的时候才会触发，因为我们不太可能设计根物体尺寸小于最小尺寸。

那么，进入递归表明这个区域涉及到了物体，而走进这个if表明这个区域已经是预设的最小单位。

上面的if先检测了子节点的区域是否涉及物体，然后再去递归，

上面return服务于，一个与物体Bounds相交并且尺寸小于minSize的子节点区域，使其不再产生子节点，并且置红颜色表示这个区域与物体相交。

重建线框

1) 在Octree类中，把构造方法中建立数据组织的语句封装给另一个函数，为了更简单的调用我把这个方法记录在了一个UnityAction中。

2) 写一个Mono脚本，当检测物体的变换发生改变时，调用UnityAction。

定位点所在小区块

1) 重新组织数据

将一个父区域切割为八个小区域，其所作的操作就是：

过立方体的中心，在其X、Y、Z轴做切线。

我直接举实例：

先判断点在大区域的中心的左右位置，能排除8个可能中的4个，

在判断点在大区域的中心的上下位置，能排除4个可能中的2个，

最好判断点在大区域的中心的前后位置，排除2个可能中的1个。

以此就从一个大区域中，得到了点所在的小区域。

2) 循环二分查找

这里强调一下八叉树存在的意义，它每次产生子区域能更精准的表示一个物体所占的区域，而对于不存在物体的区域不做细化。八叉树所表示的方形区域一般不会被分割为n*n*n的大魔方。

我们要定位的目标是层层推进找到点所在的最小树节点，对于不存在物体的区域，这个节点会是根的子节点；而区域存在物体的区域，这个节点的区域尺寸是规定的最小尺寸，层数由根节点所表示的区域决定(根的尺寸/2小于等于最小尺寸的次数)。

导航就是随便写的了，通过物体判断行进方向上一点(物体pos+dir*minSize)是否处于有物体的区域，如果有，就进行避障。

物体pos+dir*minSize中minSize是最小的区域尺寸，我们延伸检测minSize就能有效检测所有区域。(当一帧的移动大于一格不成立)。