陈巧倩

Unity 四叉树

· 126 words · 1 minutes to read
Categories: Unity
Tags: QuadTree

四叉树是一种树状数据结构，每个节点上都有四个子区块，也可以理解成每个子节点分为四个象限，可以是矩形或者任意图形。常用来表示空间索引或者二位空间碰撞检测等等。

四叉树特点 🔗

  1. 可以分解成各自的区块。
  2. 每个区块都有自己存储的数量上限，当节点达到上限则会节点分裂。
  3. 每个区块的子树相当于独立的四叉树。

实例 🔗

需求：将摄像机范围的场景物体进行隐藏裁剪，只显示摄像机范围的场景物体。 开发环境:

  • 引擎：Unity
  • 语言：C#
  • 摄像机：正交摄像机 实现：基于上述理解，我构建了一个四叉树，只是现实了5个方法，上述功能。
//当前树的位置和大小
private readonly Rect _treeRect;
//子四叉树最大数量为4
private readonly List<QuadTree> _childTrees;
//当前四叉树插入的Object的数量
private readonly List<ObjRect> _objects;
//当前四叉树深度
private readonly int _depth;
//最大深度(常量)
private readonly int _maxDepth;
//四叉树当前节点允许存储的最大Object数量
private readonly int _maxRectObjectCount;

四叉树构建 🔗

/**
** Rect为根Rect可以理解为整个四叉树的最大矩形(x、y、width、heigh)，需要注意rect锚点位置，需要实现Overlaps、Contains方法
** depth为当前四叉树深度，默认为0，每每分裂一次++。
** 注意:需要默认设置最大depth和当前节点区域最大数量上限
**/
public QuadTree(Rect rect,int depth)
{
    ......
}

四叉树分裂 🔗

/**
** 将当前区块节点分裂成4个子树，分别为当前Rect的右上、右下、左上和左下四个区域。
** 同时深度++
**/
private void Split()
{
    ......
}

四叉树获取象限 🔗

/**
** 根据传入ObjRect的Rect获取在当前四叉树的那些象限
** 使用数组是因为一个足够大的ObjRect可能会同时存在多个象限，所以对每个象限都要进入插入。
** 返回值为象限索引数组，提前规划好右上、右下、左上和左下四个子节点区域的索引。
**/
private List<int> GetSpaceIndex(ObjRect rect)
{
    ......
}

四叉树插入 🔗

/**
** 插入规则:
** 1、该区域节点已经分裂(存在子四叉树数组)，直接调用GetSpaceIndex返回对应象限索引，直接插入即可。
** 2、该区域节点未分裂，直接插入到区域对象数组里，当数组达到上限后，执行Split分裂，分裂后，讲数组的对象，依次调用**GetSpaceIndex获取象限索引，直接插入即可。
** 注意:插入为一个递归的过程，根据depth依次插入。
**/
public void Insert(ObjRect rect)
{
    ......
}

四叉树遍历检测重叠的对象 🔗

/**
** 1、通过GetSpaceIndex获取象限索引数组
** 2、遍历象限索引数组，分别调用象限子树的Retrieve进行递归
** 3、遍历象限子树Retrieve返回的List<ObjRect>，进行Overlaps判断是否重叠，对重叠的对象进行保存并且返回。
**/
public List<ObjRect> Retrieve(ObjRect rect)
{
    ......
}

四叉树最终实现效果 🔗

unity-quad-tree-animation

结论 🔗

搬砖愉快！

Recent Post

Categories

Tags