什么是四叉树

什么是四叉树（QuadTree）？这个名字与我们平常在算法与数据结构课上听到的二叉树（BinaryTree）十分相似，但也存在不同之处。回顾二叉树的定义，二叉树具有以下特点：

每个节点最多有两个子节点，分别称为左子节点和右子节点。
左子树和右子树也是二叉树，它们的结构与父节点类似。
二叉树的顺序不固定，可以是任意形状（因此也可能退化成链表）。
可以用来表示一维数据，例如堆的数据结构是数组，但可以用二叉树表示。

沿着二叉树的定义，我们可以试着得到四叉树的定义：

每个节点最多有四个子节点（区块），代表一个格子的东北（ne）、东南（se）、西北（nw）和西南（sw）。
四个子树也是四叉树，它们的结构与父节点类似。
四叉树的顺序不固定，可以是任意形状（因此也可能退化成链表）。
可以用来表示平面上的二维数据，例如下图：

上图中的 A、B、C、D、E、F 代表平面上的点，右侧的则是储存点信息的四叉树，我们可以发现两个性质：

点越密集的地方（例如点 E、F）空间的划分的就越细致，对应四叉树的深度越深。一般来说四叉树的深度并不是无限的，而是由图片、计算机内存和图形的复杂度决定的。
点只存储在四叉树的叶子节点，而不存储在父节点中。

如果平面中的对象正好覆盖了多个区域，那么该对象将被它覆盖的所有区域的叶子节点存储（代表该对象存在于这些区域）。
在本文中，我们通过抽象的一维点代替了实际的游戏对象，实际的游戏对象可以通过包围盒信息来查询覆盖的范围。

那我们怎么确定一个点位于四叉树的哪个位置、四叉树什么时候需要细分呢？这就涉及到四叉树的插入与查询了，让我们一起在 Unity 中实现一颗四叉树吧！

实现四叉树

在四叉树中，每个四叉树节点需要由以下几个部分组成：

该对象的叶子节点（QuadTree）列表 nodes，如果存在则大小为 4。
如果该节点是叶子节点，则需存储游戏对象（GameObject）列表 objects。
当前深度 level，表示细分等级。
节点的最大容量 maxObjects，如果 objects 的大小超出最大容量，则节点需要被分裂。
四叉树的最大深度 maxLevel，四叉树的深度达到最大深度后就无法继续分裂。
边界位置信息 bounds，作用是用来划分空间，可以存储区块四个顶点的位置，例如:

public struct Bound
{
    public float MinX;
    public float MinY;
    public float MaxX;
    public float MaxY;
}

由此，我们可以初步写出四叉树的基本结构：

public class QuadTree {
    private int MaxObjects{get; set;}
    private int MaxLevel{get; set;}
    private int Level{get; set;}
    private Bound Bounds{get; set;}
    private List<GameObject> Objects{get; set;}
    // node 按 nw、ne、sw、se 顺序划分
    private List<QuadTree> Nodes{get; set;}

    // 构造函数
    public QuadTree(Bound bounds, int maxObjects, int maxLevels, int level) {
        MaxObjects = maxObjects;
        MaxLevel = maxLevels;
        Bounds = bounds;
        Level = level;
        Objects = new List<GameObject>();
        Nodes = new List<QuadTree>();
    }
}

假设四叉树每个节点最多能容纳 5 个对象、最大深度为 4，我们可以创建一颗四叉树了：

1	QuadTree root = new QuadTree(bounds, 5, 4);

插入

这个四叉树现在是空的，我们可以往其中插入游戏对象。插入分为以下几种情况：

当前节点存在叶子节点，则将元素递归地插入到匹配的叶子节点中。
当前节点不存在叶子节点：
- 如果当前节点存储的节点超出最大限制，且层数未达到限制，则分裂该节点；
- 否则，将元素添加进当前节点的 nodes 中。

/// <summary>
/// 插入一个节点
/// </summary>
public void Insert(GameObject obj) {
    // 如果存在子节点，将节点插入到匹配的子节点中
    if (this.Nodes.Count == 4) {
        this.Nodes[this.GetIndex(obj)].Insert(obj);
        return;
    }

    // 否则，将节点存储在当前节点中
    this.Objects.Add(obj);

    // 如果当前节点的对象数量超过了最大容量，并且当前层级小于最大层级
    if (this.Objects.Count > this.MaxObjects && this.Level < this.MaxLevel) {
        // 如果还没有子节点，则进行分割
        if (this.Nodes.Count == 0) {
            this.Split();
        }

        // 将所有对象添加到对应的子节点中
        for (int i = 0; i < this.Objects.Count; i++) {
            int idx = this.GetIndex(Objects[i]);
            this.Nodes[idx].Insert(Objects[i]);
        }

        // 清空当前节点的对象列表
        this.Objects.Clear();
    }
}

如何将对象插入到对应的叶子节点中呢？上面的代码调用了 GetIndex 方法，该方法通过点的坐标位置关系获取所在区块的“索引”，即该点位于哪个叶子节点的范围内：

/// <summary>
/// 获取叶子节点id
/// </summary>
private int GetIndex(GameObject obj) {
    var x = obj.transform.position.x;
    var y = obj.transform.position.z;
    var midPointX = (this.Bounds.MaxX + this.Bounds.MinX)/2;
    var midPointY = (this.Bounds.MaxY + this.Bounds.MinY)/2;
        
    if (x <= midPointX && y >= midPointY)
        // nw（左上）
        return 0;
    if (x >= midPointX && y >= midPointY)
        // ne（右上）
        return 1;
    if (x < midPointX && y < midPointY)
        // sw（左下）
        return 2;
    // sw（右下）
    return 3;
}

根节点分裂成四个叶子节点则调用了 Split 方法，根据根节点的边界信息 Bound 划分四个叶子节点的区域，再将根节点存储的游戏对象插入对应的叶子节点中，最后清空根节点的 Objects：

/// <summary>
/// 分割节点
/// </summary>
private void Split() {
    int nextLevel = this.Level + 1;
    float midX = (this.Bounds.MaxX + this.Bounds.MinX) / 2;
    float midY = (this.Bounds.MaxY + this.Bounds.MinY) / 2;

    // 创建 4 个子节点
    this.Nodes = new List<QuadTree>(4);

    // nw（左上）
    this.Nodes.Add(new QuadTree(
        new Bound {
            MinX = this.Bounds.MinX,
            MaxX = midX,
            MinY = midY,
            MaxY = this.Bounds.MaxY
        },
        this.MaxObjects,
        this.MaxLevel,
        nextLevel
    ));

    // ne（右上）
    this.Nodes.Add(new QuadTree(
        new Bound {
            MinX = midX,
            MaxX = this.Bounds.MaxX,
            MinY = midY,
            MaxY = this.Bounds.MaxY
        },
        this.MaxObjects,
        this.MaxLevel,
        nextLevel
    ));

    // sw（左下）
    this.Nodes.Add(new QuadTree(
        new Bound {
            MinX = this.Bounds.MinX,
            MaxX = midX,
            MinY = this.Bounds.MinY,
            MaxY = midY
        },
        this.MaxObjects,
        this.MaxLevel,
        nextLevel
    ));

    // se（右下）
    this.Nodes.Add(new QuadTree(
        new Bound {
            MinX = midX,
            MaxX = this.Bounds.MaxX,
            MinY = this.Bounds.MinY,
            MaxY = midY
        },
        this.MaxObjects,
        this.MaxLevel,
        nextLevel
    ));

    // 在Unity中画线
    Debug.DrawLine(new Vector3(midX, 0, this.Bounds.MinY), new Vector3(midX, 0, this.Bounds.MaxY), Color.red,100.0f);
    Debug.DrawLine(new Vector3(this.Bounds.MinX, 0, midY), new Vector3(this.Bounds.MaxX, 0, midY), Color.red,100.0f);
}

在Unity中的效果

查询

根据一个游戏对象所处的位置，我们可以找到该节点位于四叉树的哪个叶子节点吗？当然是可以的，流程如下：

输入根节点，检测节点是否有叶子节点
- 有叶子节点，则通过 GetIndex 找到这个对象在四叉树的哪个叶子节点，继续查找；
- 无叶子节点，则说明对象处于该节点，返回即可。

/// <summary>
/// 查找对象所在的叶子节点
/// </summary>
public QuadTree Find(GameObject obj, QuadTree root) {
    // 该节点非叶子节点
    while (root.Nodes.Count == 4) {
        // 获取节点所在的子节点索引
        var index = root.GetIndex(obj);
        root = root.Nodes[index];
    }

    return root;
}

应用

既然四叉树是一种类似二叉树的数据结构，那它有什么用武之处呢？答案是优化二维空间搜索的复杂度。四叉树可以用在诸如碰撞检测（collision detection）、状态同步中的**感兴趣区域（AOI）**划分的算法优化上。

假设我们要检测两个矩形是否发生了碰撞（存在重合），一般是通过顶点的坐标进行判断的：

这是两两矩形之间碰撞检测，如果场景中存在多个矩形，我们该怎么判断它们之间是否发生了碰撞呢？朴素的碰撞检测会遍历所有的矩形，算法的时间复杂度将达到 $O(N)$ ：

Quad[] objs;    // 矩形数组，Quad 数据结构记录了矩形的四个顶点
void collisionDection(){
    for(int i = 0; i < objs.length; i++){
        for(int j = 0; j < objs.length; j++){
            if(j == i)  // 不检查自身
                continue;
            ... // 判断顶点关系
        }
    }
}

如果场景中只存在几个矩形倒还好，但一旦数量上升（例如部分 rts 游戏中动辄几十几百个单位）就可能成为移动端的性能瓶颈，造成帧率下降、卡顿、手机发热等问题。而有了四叉树之后，就可以根据对象所处的四叉树节点，检查节点内的几个对象之间的位置关系即可，避免遍历所有对象，是一种牺牲空间换取时间的优化方式。