八叉树空间寻路

八叉树寻路的作用

八叉树（Octree）寻路是一种在 3D空间 中进行路径规划的技术。它的主要作用和优势包括：

1. 3D空间分割与管理

• 八叉树将3D空间递归地分割成8个子节点（类似于2D中的四叉树）

• 可以高效地表示复杂的3D环境，包括有高度差异的地形

2. 主要应用场景

3. 相比2D寻路的优势

传统2D寻路（NavMesh/Grid）：只考虑水平面移动

八叉树3D寻路：支持上下左右前后全方位移动

4. 空间优化

• 稀疏表示：空旷区域用大节点表示，复杂区域细分为小节点

• 动态更新：可以高效地更新局部空间变化

• 内存高效：只存储必要的空间信息

5. 与A算法结合 八叉树通常与A等寻路算法结合使用： - 八叉树节点作为寻路图的节点 - 相邻节点之间建立连接 - 使用启发式搜索找到最优路径

简单示意

       ┌───────────┐
       │  根节点   │  (整个3D空间)
       └─────┬─────┘
             │
    ┌────┬───┴───┬────┐
    ↓    ↓       ↓    ↓
  ┌──┐ ┌──┐   ┌──┐ ┌──┐  × 8个子节点
  └──┘ └──┘   └──┘ └──┘
    ↓
  继续细分...

开始创建八叉树

1. 创建节点

子节点方块的布置如下图所示

简单分析可知， 每个子节点中心的位置都是从父节点中心偏移 四分之一 父节点边长 而来

而且偏移的方向都是在 X, Y, Z 三条轴上，8个子节点对应了8种偏移位置

所以我们可以用1-8的二进制来表示这三个位置（000， 001， 010， 011， 100， 101， 110， 111）

用每个位置上的 0 来区分 X, Y, Z 上偏移的方向

对应代码如下：

using System.Collections.Generic;
using UnityEngine;

public class OctreeTreeNode
{
    /// <summary>
    /// 分割单元最小尺寸
    /// </summary>
    private readonly float MIN_SIZE = 1.0f;

    /// <summary>
    /// 父节点
    /// </summary>
    public OctreeTreeNode parent { get; private set; }

    /// <summary>
    /// 子节点列表
    /// </summary>
    public List<OctreeTreeNode> child;

    /// <summary>
    /// 包围盒作为节点方块
    /// </summary>
    public Bounds nodeCube { get; private set; }

    public OctreeTreeNode(OctreeTreeNode parent, Bounds nodeCube)
    {
        this.parent = parent;
        this.nodeCube = nodeCube;
    }

    public void Divide()
    {
        if (nodeCube.size.x / 2 < MIN_SIZE)
        {
            return;
        }

        float childHalfSize = nodeCube.size.x / 4;
        if (child == null)
        {
            child = new List<OctreeTreeNode>();
        }
        Vector3 offest; // 子节点相对于父节点的偏移量
        for (int i = 0; i < 8; i++)
        {
            offest = new Vector3(
                ((i & 1) == 0) ? -childHalfSize : childHalfSize, // 001
                ((i & 2) == 0) ? -childHalfSize : childHalfSize, // 010
                ((i & 4) == 0) ? -childHalfSize : childHalfSize  // 100
            );
            Bounds childBounds = new Bounds(
                nodeCube.center + offest,
                new Vector3(childHalfSize * 2, childHalfSize * 2, childHalfSize * 2)
            );
            OctreeTreeNode childNode = new OctreeTreeNode(this, childBounds);
            child.Add(childNode);
            childNode.Divide();
        }
    }
}

为了方便观察结果，在类中添个用于绘制方块的函数，当它在OnDrawGizmos中调用时就可以看到方块了

public void Draw(bool isSeeOne)
{
    Gizmos.color = Color.green;
    Gizmos.DrawWireCube(NodeCube.center, NodeCube.size);
    if (Children == null)
        return;
    foreach(var c in Children)
    {
        c.Draw(isSeeOne);
        if(isSeeOne)
        {
            break;
        }
    }
}

为了方便在Unity中使用，我们创建一个继承了 MonoBehaviour 的类 CreatOctreeTree，并将它挂在一个边长为8的Cube上：

public class CreatOctreeTree : MonoBehaviour
{
    public bool isSeeOne = true; //只看分裂后的一个
    private OctreeTreeNode node;
    private void Awake()
    {
        //用Cube本身的包围盒做为起始尺寸进行划分
        node = new OctreeTreeNode(node, GetComponent<Renderer>().bounds);
        node.Divide();
    }

    private void OnDrawGizmos()
    {
        if (Application.isPlaying)
        {
            node.Draw(isSeeOne);
        }
    }
}

运行查看， 我们创建了一个边长为 8 的 Cube， 一共分裂了 3 次， 符合预期

创建节点完整代码

using System.Collections.Generic;
using UnityEngine;

public class OctreeTreeNode
{
    /// <summary>
    /// 分割单元最小尺寸
    /// </summary>
    private readonly float MIN_SIZE = 1.0f;

    /// <summary>
    /// 父节点
    /// </summary>
    public OctreeTreeNode parent { get; private set; }

    /// <summary>
    /// 子节点列表
    /// </summary>
    public List<OctreeTreeNode> child;

    /// <summary>
    /// 包围盒作为节点方块
    /// </summary>
    public Bounds nodeCube { get; private set; }

    public OctreeTreeNode(OctreeTreeNode parent, Bounds nodeCube)
    {
        this.parent = parent;
        this.nodeCube = nodeCube;
    }

    public void Divide()
    {
        if (nodeCube.size.x / 2 < MIN_SIZE)
        {
            return;
        }

        float childHalfSize = nodeCube.size.x / 4;
        if (child == null)
        {
            child = new List<OctreeTreeNode>();
        }
        Vector3 offest; // 子节点相对于父节点的偏移量
        for (int i = 0; i < 8; i++)
        {
            offest = new Vector3(
                ((i & 1) == 0) ? -childHalfSize : childHalfSize, // 001
                ((i & 2) == 0) ? -childHalfSize : childHalfSize, // 010
                ((i & 4) == 0) ? -childHalfSize : childHalfSize  // 100
            );
            Bounds childBounds = new Bounds(
                nodeCube.center + offest,
                new Vector3(childHalfSize * 2, childHalfSize * 2, childHalfSize * 2)
            );
            OctreeTreeNode childNode = new OctreeTreeNode(this, childBounds);
            child.Add(childNode);
            childNode.Divide();
        }
    }

    //isSeeOne为true，则只查看分裂后的一个，否则查看所有分裂后的方块
    public void Draw(bool isSeeOne)
    {
        Gizmos.color = Color.green;
        Gizmos.DrawWireCube(nodeCube.center, nodeCube.size);
        if (child == null)
            return;
        foreach (var c in child)
        {
            c.Draw(isSeeOne);
            if (isSeeOne)
            {
                break;
            }
        }
    }
}


public class CreatOctreeTree : MonoBehaviour
{
    public bool isSeeOne = true; //只看分裂后的一个
    private OctreeTreeNode node;
    private void Awake()
    {
        //用Cube本身的包围盒做为起始尺寸进行划分
        node = new OctreeTreeNode(node, GetComponent<Renderer>().bounds);
        node.Divide();
    }

    private void OnDrawGizmos()
    {
        if (Application.isPlaying)
        {
            node.Draw(isSeeOne);
        }
    }
}

2. 寻找根节点

游戏场景往往是多变的，一直用一个Cube去试显然不是高效的方案。

Unity内置了一个方法可以为我们解决这个问题

Encapsulate 方法可以让包围盒自行扩大以容纳下传进来的包围盒。所以我们让一个包围盒把场景中的所有物体都容纳进去，这样就能得到足够大的包围盒了。我们新建一个MyOctree类：

public class MyOctreetree
{
    public OctreeTreeNode rootNode { get; private set; }
    public MyOctreetree(List<GameObject> objects)
    {
        if (objects == null || objects.Count == 0)
            return;

        // 用第一个物体的包围盒初始化
        var baseCube = objects[0].GetComponent<Renderer>().bounds;
        // 将剩余对象的包围盒合并
        for (int i = 1; i < objects.Count; i++)
        {
            baseCube.Encapsulate(objects[i].GetComponent<Renderer>().bounds);
        }
        // 将包围盒调整为立方体
        var cubeSize = Mathf.Max(baseCube.size.x, Mathf.Max(baseCube.size.y, baseCube.size.z)) * Vector3.one;
        baseCube.SetMinMax(baseCube.center - cubeSize / 2f, baseCube.center + cubeSize / 2f);

        rootNode = new OctreeTreeNode(null, baseCube);
        rootNode.Divide();
    }
}

注意baseCube的bounds只能用用第一个物体的包围盒初始化，不能直接 new() ，因为当你使用 new Bounds() 创建一个空的包围盒时，它的 center 是 (0,0,0)，size 是 (0,0,0)。

当你调用 Encapsulate 时，它会扩展包围盒以同时包含原点 (0,0,0) 和物体的包围盒，导致最终的 baseCube 包含了从原点到物体位置的整个区域。

顺便也改改 CreatOctreeTree 脚本，让它画出八叉树，而不是单一节点：

public class CreatOctreeTree : MonoBehaviour
{
    /// <summary>
    /// 只看分裂后的一个
    /// </summary>
    public bool isSeeOne = true;

    /// <summary>
    ///  需要划分八叉树的物体列表
    /// </summary>
    public List<GameObject> objects;

    /// <summary>
    /// 八叉树
    /// </summary>
    private MyOctreetree myOctreetree;

    private void Awake()
    {
        // 获取场景中有 Render 的 GameObject
        var renderers = FindObjectsOfType<Renderer>();
        objects = new List<GameObject>();
        foreach (var renderer in renderers)
        {
            objects.Add(renderer.gameObject);
        }
        myOctreetree = new MyOctreetree(objects);
    }

    private void OnDrawGizmos()
    {
        if (Application.isPlaying)
        {
            myOctreetree.rootNode.Draw(isSeeOne);
        }
    }
}

随便在场景里摆了几个立方体，最终生成的最大包围盒能将它们都裹住：

但是现在有一个问题，当场景变大包围盒跟着变大时，我们需要分割的次数也会跟着上升，我们使用的Divide函数为递归调用，每递归深度加一都要进行8ⁿ次方次分割，这会带来巨大的性能开销，因此我们要进行一些优化。

3. 性能优化

Ⅰ. 限制递归深度

首先最容易想到的就是限制递归深度

我们为代码添加最大递归深度，并实时追踪当前深度，当递归达到最大深度时退出分割递归。

using System.Collections.Generic;
using UnityEngine;

public class OctreeTreeNode
{
    /// <summary>
    /// 分割单元最小尺寸
    /// </summary>
    private float minSize;

    /// <summary>
    /// 最大递归深度
    /// </summary>
    private int maxDepth;

    /// <summary>
    /// 当前节点深度
    /// </summary>
    private int depth;

    /// <summary>
    /// 父节点
    /// </summary>
    public OctreeTreeNode parent { get; private set; }

    /// <summary>
    /// 子节点列表
    /// </summary>
    public List<OctreeTreeNode> child;

    /// <summary>
    /// 包围盒作为节点方块
    /// </summary>
    public Bounds nodeCube { get; private set; }

    public OctreeTreeNode(OctreeTreeNode parent, Bounds nodeCube, int depth, float minSize, int maxDepth)
    {
        this.parent = parent;
        this.nodeCube = nodeCube;
        this.depth = depth;
        this.minSize = minSize;
        this.maxDepth = maxDepth;
    }

    public void Divide()
    {
        if (nodeCube.size.x / 2 < minSize || depth >= maxDepth)
        {
            return;
        }

        float childHalfSize = nodeCube.size.x / 4;
        if (child == null)
        {
            child = new List<OctreeTreeNode>();
        }
        Vector3 offest; // 子节点相对于父节点的偏移量
        for (int i = 0; i < 8; i++)
        {
            offest = new Vector3(
                ((i & 1) == 0) ? -childHalfSize : childHalfSize, // 001
                ((i & 2) == 0) ? -childHalfSize : childHalfSize, // 010
                ((i & 4) == 0) ? -childHalfSize : childHalfSize  // 100
            );
            Bounds childBounds = new Bounds(
                nodeCube.center + offest,
                new Vector3(childHalfSize * 2, childHalfSize * 2, childHalfSize * 2)
            );
            OctreeTreeNode childNode = new OctreeTreeNode(this, childBounds, depth + 1, minSize, maxDepth);
            child.Add(childNode);
            childNode.Divide();
        }
    }

    //isSeeOne为true，则只查看分裂后的一个，否则查看所有分裂后的方块
    public void Draw(bool isSeeOne)
    {
        Gizmos.color = Color.green;
        Gizmos.DrawWireCube(nodeCube.center, nodeCube.size);
        if (child == null)
            return;
        foreach (var c in child)
        {
            c.Draw(isSeeOne);
            if (isSeeOne)
            {
                break;
            }
        }
    }
}

public class MyOctreetree
{
    public OctreeTreeNode rootNode { get; private set; }
    public MyOctreetree(List<GameObject> objects, float minSize, int maxDepth)
    {
        if (objects == null || objects.Count == 0)
            return;

        // 用第一个物体的包围盒初始化
        var baseCube = objects[0].GetComponent<Renderer>().bounds;
        // 将剩余对象的包围盒合并
        for (int i = 1; i < objects.Count; i++)
        {
            baseCube.Encapsulate(objects[i].GetComponent<Renderer>().bounds);
        }
        // 将包围盒调整为立方体
        var cubeSize = Mathf.Max(baseCube.size.x, Mathf.Max(baseCube.size.y, baseCube.size.z)) * Vector3.one;
        baseCube.SetMinMax(baseCube.center - cubeSize / 2f, baseCube.center + cubeSize / 2f);

        rootNode = new OctreeTreeNode(null, baseCube, 0, minSize, maxDepth);
        rootNode.Divide();
    }
}


public class CreatOctreeTree : MonoBehaviour
{
    /// <summary>
    /// 只看分裂后的一个
    /// </summary>
    public bool isSeeOne = true;

    /// <summary>
    /// 分割单元最小尺寸
    /// </summary>
    [Range(0.1f, 10f)]
    public float minSize = 1.0f;

    /// <summary>
    /// 最大递归深度
    /// </summary>
    [Range(1, 10)]
    public int maxDepth = 5;

    /// <summary>
    ///  需要划分八叉树的物体列表
    /// </summary>
    public List<GameObject> objects;

    /// <summary>
    /// 八叉树
    /// </summary>
    private MyOctreetree myOctreetree;

    /// <summary>
    /// 八叉树构建时间(毫秒)
    /// </summary>
    [Header("构建信息")]
    public float buildTimeMs;

    private void Awake()
    {
        // 获取场景中有Render的GameObject
        var renderers = FindObjectsOfType<Renderer>();
        objects = new List<GameObject>();
        foreach (var renderer in renderers)
        {
            objects.Add(renderer.gameObject);
        }

        var stopwatch = System.Diagnostics.Stopwatch.StartNew();
        myOctreetree = new MyOctreetree(objects, minSize, maxDepth);
        stopwatch.Stop();
        buildTimeMs = stopwatch.ElapsedMilliseconds;
        Debug.Log($"八叉树构建完成，耗时: {buildTimeMs} ms");
    }

    private void OnDrawGizmos()
    {
        if (Application.isPlaying)
        {
            myOctreetree.rootNode.Draw(isSeeOne);
        }
    }
}

可以看到限制了递归深度后，构建耗时明显下降

但仅仅限制递归深度并不完善而且当物体体积较小时精度并不准确

所以我们还需要一种更有策略性的优化方式 —— 前剪枝

Ⅱ. 前剪枝

什么是前剪枝？

前剪枝（Pre-pruning）

是决策树和八叉树等树形数据结构中的一种优化策略。

定义：在树的构建过程中，提前停止节点的分裂，而不是等树完全构建后再进行修剪。

在我们的代码中，对递归深度进行限制也是一种前剪枝策略

现在我将说明一种更具有针对性的前剪枝策略

我们可以注意到，其实有一些方块没必要继续分裂下去。分裂行为其实是有目的的：检测出哪里有障碍物。一个大方块不断分裂变小，就是更进一步定位内部障碍物位置的过程，如果它一开始就没碰到什么障碍物，那也没必要分裂了。

在 MyOctreetree 中将第一个包围盒中的所有Collider收集起来，传入到rootNode的分割当中

public class MyOctreetree
{
    public OctreeTreeNode rootNode { get; private set; }
    public MyOctreetree(List<GameObject> objects, float minSize, int maxDepth)
    {
        if (objects == null || objects.Count == 0)
            return;

        // 用第一个物体的包围盒初始化
        var baseCube = objects[0].GetComponent<Renderer>().bounds;
        // 将剩余对象的包围盒合并
        for (int i = 1; i < objects.Count; i++)
        {
            baseCube.Encapsulate(objects[i].GetComponent<Renderer>().bounds);
        }
        // 将包围盒调整为立方体
        var cubeSize = Mathf.Max(baseCube.size.x, Mathf.Max(baseCube.size.y, baseCube.size.z)) * Vector3.one;
        baseCube.SetMinMax(baseCube.center - cubeSize / 2f, baseCube.center + cubeSize / 2f);

        rootNode = new OctreeTreeNode(null, baseCube, 0, minSize, maxDepth);

        var colliders = new List<Collider>();
        foreach (var o in objects)
        {
            if (o.TryGetComponent<Collider>(out var collider))
            {
                colliders.Add(collider);
            }
        }
        rootNode.Divide(colliders);
    }
}

在 Divide 中，我们先判断当前节点是否与之前收集的Collider有相交，若没有相交，则该节点不再进行分割

public void Divide(List<Collider> colliders)
{
    if (nodeCube.size.x / 2 < minSize || depth >= maxDepth)
    {
        return;
    }

    // 找出与当前节点包围盒相交的碰撞体
    var intersecting = colliders.FindAll(c => nodeCube.Intersects(c.bounds));
    // 前剪枝：没有物体相交则停止
    if (intersecting.Count == 0)
    {
        return;
    }

    float childHalfSize = nodeCube.size.x / 4;
    if (child == null)
    {
        child = new List<OctreeTreeNode>();
    }
    Vector3 offest; // 子节点相对于父节点的偏移量
    for (int i = 0; i < 8; i++)
    {
        offest = new Vector3(
            ((i & 1) == 0) ? -childHalfSize : childHalfSize, // 001
            ((i & 2) == 0) ? -childHalfSize : childHalfSize, // 010
            ((i & 4) == 0) ? -childHalfSize : childHalfSize  // 100
        );
        Bounds childBounds = new Bounds(
            nodeCube.center + offest,
            new Vector3(childHalfSize * 2, childHalfSize * 2, childHalfSize * 2)
        );

        OctreeTreeNode childNode = new OctreeTreeNode(this, childBounds, depth + 1, minSize, maxDepth);
        child.Add(childNode);
        childNode.Divide(intersecting); // 只传递相交的碰撞体
    }
}

我们来看一下进行了前剪枝后的性能

调大了递归深度，减小了最小分割长度，构建速度依旧远超之前 ！！！

至此我们就创建好了八叉树，并得到了每一个节点。

4. 连接网格

Ⅰ. 收集节点

通过观察我们知道，每一个节点都为一个正方体，有六个面，所以我们可以一个节点与相邻的六个节点连接起来，我们称为 邻居连接

同时我们要剔除包含了障碍物的节点

通过这个图我们很容易可以看出包含障碍物的节点一定是不能再分割的节点(叶子节点)

什么情况不能再分割

1. 节点不包含障碍物

2. 节点包含障碍物，但是已经到达分割最小单元或最大递归深度

显然符合我们需求的是第二种

if (nodeCube.size.x / 2 < minSize || depth >= maxDepth)
{
    // 叶子节点：检查是否与障碍物相交
    isBlocked = colliders.Exists(c => nodeCube.Intersects(c.bounds));
    return;
}

所以我们直接在进入最小分割单元或最大递归深度里判断该节点是否包含障碍物即可得到障碍物节点

在 OctreeTreeNode 中添加用于邻居连接的字段

 /// <summary>
 /// 是否包含障碍物（与碰撞体相交）
 /// </summary>
 public bool isBlocked = false;

 /// <summary>
 /// 六个方向的邻居节点 (Left, Right, Down, Up, Back, Front)
 /// </summary>
 public OctreeTreeNode[] neighbors = new OctreeTreeNode[6];

 /// <summary>
 /// 邻居方向枚举
 /// </summary>
 public enum Direction { Left, Right, Down, Up, Back, Front }

/// <summary>
/// 判断是否为叶子节点
/// </summary>
public bool IsLeaf => child == null || child.Count == 0;

/// <summary>
/// 是否可通行（叶子节点且不包含障碍物）
/// </summary>
public bool IsWalkable => IsLeaf && !isBlocked;

在 MyOctreetree 中添加储存叶子节点的列表，以及收集叶子列表的方法

/// <summary>
/// 叶子节点列表
/// </summary>
public List<OctreeTreeNode> leafNodes { get; private set; }

 /// <summary>
/// 递归收集所有叶子节点
/// </summary>
private void CollectLeafNodes(OctreeTreeNode node)
{
    if (node == null) return;

    // 只收集不含障碍物的叶子节点
    if (node.IsLeaf)
    {
        if (node.isBlocked)
        {
            return;
        }
        leafNodes.Add(node);
        return;
    }

    // 非叶子节点，递归处理子节点
    foreach (var c in node.child)
    {
        CollectLeafNodes(c);
    }
}

Ⅱ. 建立邻居连接

建立连接条件

1.两个节点有共享面

判断“是否共享面”

两个叶节点 A / B：

A.max.x == B.min.x 或反过来

且 Y、Z 区间有重叠

共享面 = 
|Axmax - Bxmin| < ε
AND overlap(A.y, B.y)
AND overlap(A.z, B.z)

2.共享面的面积大于阈值

这一步能直接避免：

• AI 卡边

• 穿过“细缝”

• 数值抖动

添加字段

/// <summary>
/// 共享面最小面积阈值（小于此值不建立连接）
/// </summary>
private float minSharedAreaThreshold;

/// <summary>
/// 浮点数比较容差
/// </summary>
private const float EPSILON = 0.001f;

连接方法

接下来在 MyOctreetree 中添加为为叶子节点建立邻居连接的方法

/// <summary>
/// 为叶子节点建立邻居连接
/// </summary>
private void BuildNeighborConnections()
{
    foreach (var leaf in leafNodes)
    {
        for (int i = 0; i < 6; i++)
        {
            var dir = (OctreeTreeNode.Direction)i;
            var neighbor = FindNeighborNode(leaf, dir);
            // 只连接可通行的邻居
            if (neighbor != null && !neighbor.isBlocked)
            {
                leaf.neighbors[i] = neighbor;
            }
        }
    }
}

/// <summary>
/// 查找指定方向的邻居节点
/// </summary>
private OctreeTreeNode FindNeighborNode(OctreeTreeNode node, OctreeTreeNode.Direction dir)
{
    // 计算邻居位置（稍微偏移到邻居内部）
    Vector3 offset = OctreeTreeNode.GetDirectionOffset(dir) * node.nodeCube.size.x;
    Vector3 neighborCenter = node.nodeCube.center + offset;

    // 从根节点查找包含该点的叶子节点
    return FindLeafNodeContainingPoint(rootNode, neighborCenter);
}

/// <summary>
/// 查找包含指定点的叶子节点
/// </summary>
private OctreeTreeNode FindLeafNodeContainingPoint(OctreeTreeNode node, Vector3 point)
{
    if (node == null || !node.nodeCube.Contains(point))
        return null;

    // 如果是叶子节点，返回自己
    if (node.IsLeaf)
        return node;

    // 递归查找子节点
    foreach (var c in node.child)
    {
        var result = FindLeafNodeContainingPoint(c, point);
        if (result != null)
            return result;
    }

    return null;
}