许多游戏需要使用碰撞检测算法来判断两个物体何时发生碰撞，但这些算法通常计算成本较高，可能会显著拖慢游戏的运行速度。在本文中，我们将学习什么是四叉树（quadtree），以及如何利用它们跳过那些相距太远而不可能发生碰撞的游戏对象，从而加快碰撞检测的速度。
注意：本教程使用 Java 编写，但原理是能够在任何游戏开发环境中应用相同的技巧和概念。
简介
碰撞检测是大多数电子游戏中不可或缺的一部分。无论是在二维还是三维游戏中，检测两个物体是否发生碰撞都是非常重要的，因为糟糕的碰撞检测可能会得到一些意想不到的结果。
碰撞检测也是一项计算成本非常高的操作。假设当前有 100 个物体需要检查是否发生碰撞。比较每一对物体间是否发生碰撞需要进行 10,000 次操作——这是一个相当大的运算量！
加快碰撞检测的一种方法是减少判断次数。比如位于屏幕两端的两个物体根本不可能发生碰撞，因此完全没有必要对它们进行碰撞检测。这时就可以利用四叉树（quadtree）来发挥作用了。
什么是四叉树？
四叉树是一种用于将二维区域划分为更小、并且更易于管理的数据结构。它是二叉树的扩展，但与二叉树只有两个子节点不同，四叉树的每个节点最多可以有四个子节点。
在下面的图示中，每张图都直观地表示了一个二维空间，其中红色方块代表物体。在本文中，子节点将按照逆时针方向进行标记，如下图：
四叉树开始时作为一个单一的节点。当向四叉树中添加物体时，这些物体会被添加到这个单一的节点中。
当向四叉树添加更多物体时，一旦达到某个条件（如节点包含的物体数量超过设定的阈值，或达到了空间划分的最小粒度），该节点就会分裂成四个子节点。每个物体会根据其在二维空间中的位置被分配到其中一个子节点中。如果有物体不能完全适应任何一个子节点的边界（即跨越了多个子区域），那么这个物体会被放置在其父节点中。
每个子节点在继续添加更多物体时也可以进一步细分。
如我们所见，每个节点只包含少量的物体。例如，位于左上角节点中的物体不可能与位于右下角节点中的物体发生碰撞，因此我们无需在这类物体对之间运行耗时的碰撞检测算法。
实现一个四叉树
实现四叉树（Quadtree）相对来说非常简单。以下代码使用 Java 编写，但其中的技巧可以适用于其他编程语言中。我会在每段代码后进行注释说明。
我们首先创建主 Quadtree 类。以下是 Quadtree.java 的代码：
public class Quadtree {
private int MAX_OBJECTS = 10;
private int MAX_LEVELS = 5;
private int level;
private List objects;
private Rectangle bounds;
private Quadtree[] nodes;
/*
* 构造器
*/
public Quadtree(int pLevel, Rectangle pBounds) {
level = pLevel;
objects = new ArrayList();
bounds = pBounds;
nodes = new Quadtree[4];
}
}
Quadtree 类的结构非常清晰。其中：
- MAX_OBJECTS 定义了一个节点在分裂之前最多可以容纳的对象数量；
- MAX_LEVELS 定义了子节点的最大层级深度（即最多可以细分多少层）；
- level 是当前节点的层级（最顶层为 0）；
- bounds 表示该节点所代表的二维空间区域；
- nodes 是该节点的四个子节点。
- 在这个例子中，四叉树所存储的对象是 Rectangle 类型，但你可以根据自己的需求将它替换为你所需的任何对象类型。
接下来，我们将实现四叉树的五个核心方法，clear、split、getIndex、insert 和 retrieve。
/*
* 清理四叉树
*/
public void clear() {
objects.clear();
for (int i = 0; i < nodes.length; i++) {
if (nodes[i] != null) {
nodes[i].clear();
nodes[i] = null;
}
}
}
clear 方法通过递归地清除所有节点中的所有对象来清空四叉树。
/*
* 将节点划分为4个子节点
*/
private void split() {
int subWidth = (int)(bounds.getWidth() / 2);
int subHeight = (int)(bounds.getHeight() / 2);
int x = (int)bounds.getX();
int y = (int)bounds.getY();
// 初始化四个子节点，每个子节点占据当前节点四分之一的空间
// 第一象限
nodes[0] = new Quadtree(level+1, new Rectangle(x + subWidth, y, subWidth, subHeight));
// 第二象限
nodes[1] = new Quadtree(level+1, new Rectangle(x, y, subWidth, subHeight));
// 第三象限
nodes[2] = new Quadtree(level+1, new Rectangle(x, y + subHeight, subWidth, subHeight));
// 第四象限
nodes[3] = new Quadtree(level+1, new Rectangle(x + subWidth, y + subHeight, subWidth, subHeight));
}
split 方法通过将节点划分为四个相等的部分来将其拆分为四个子节点，并使用新的边界初始化这四个子节点。
/*
* 确定一个物体属于哪一个子节点。
* 返回值为 -1 表示该物体无法完全放入任何一个子节点中，
* 因此它应保留在当前父节点中。
*/
private int getIndex(Rectangle pRect) {
int index = -1; // 默认：物体不能完全属于任何一个子节点
// 计算当前节点区域的垂直中线和水平中线
double verticalMidpoint = bounds.getX() + (bounds.getWidth() / 2);
double horizontalMidpoint = bounds.getY() + (bounds.getHeight() / 2);
// 判断物体是否完全位于上半部分的两个象限内（顶部两个子节点）
boolean topQuadrant = (pRect.getY() < horizontalMidpoint &&
pRect.getY() + pRect.getHeight() < horizontalMidpoint);
// 判断物体是否完全位于下半部分的两个象限内（底部两个子节点）
boolean bottomQuadrant = (pRect.getY() > horizontalMidpoint);
// 检查物体是否在左侧两个象限之一
if (pRect.getX() < verticalMidpoint &&
pRect.getX() + pRect.getWidth() < verticalMidpoint) {
if (topQuadrant) {
// 左上象限（对应子节点索引 1）
index = 1;
} else if (bottomQuadrant) {
// 左下象限（对应子节点索引 2）
index = 2;
}
// 检查物体是否在右侧两个象限之一
} else if (pRect.getX() > verticalMidpoint) {
if (topQuadrant) {
// 右上象限（对应子节点索引 0）
index = 0;
} else if (bottomQuadrant) {
// 右下象限（对应子节点索引 3）
index = 3;
}
}
return index;
}
getIndex 方法是四叉树的一个辅助函数，它通过确定物体可以放入哪个节点来决定物体在四叉树中的位置。
/*
* 将物体插入到四叉树中。如果当前节点中的物体数量
* 超过了设定的最大容量，该节点将进行分裂，并将所有物体
* 分配到它们对应的子节点中。
*/
public void insert(Rectangle pRect) {
// 如果当前节点已经有子节点（即已经分裂过）
if (nodes[0] != null) {
// 确定该物体属于哪个子节点
int index = getIndex(pRect);
// 如果物体可以放入某个子节点中
if (index != -1) {
// 递归地将物体插入到对应的子节点中
nodes[index].insert(pRect);
return;
}
}
// 否则将物体保留在当前节点中
objects.add(pRect);
// 如果当前节点的物体数量超过了最大容量，并且还没有达到最大层级
if (objects.size() > MAX_OBJECTS && level < MAX_LEVELS) {
// 如果尚未分裂，则先进行分裂
if (nodes[0] == null) {
split();
}
int i = 0;
while (i < objects.size()) {
// 再次尝试确定该物体属于哪个子节点
int index = getIndex(objects.get(i));
// 如果可以放入某个子节点
if (index != -1) {
// 将该物体从当前节点移除，并插入到对应的子节点中
nodes[index].insert(objects.remove(i));
} else {
// 否则继续检查下一个物体
i++;
}
}
}
}
insert 方法是四叉树中会调用所有逻辑函数的地方。该方法首先检查节点是否有子节点，并尝试将物体添加到合适的子节点中。如果没有子节点或者物体无法放入任何一个子节点，则将物体添加到当前（父）节点中。
一旦物体被添加，该方法会检查当前节点中的物体数量是否超过了允许的最大物体数量，以决定节点是否需要分裂。如果需要分裂，节点将会把能够放入子节点的物体分配给相应的子节点；否则，这些物体会继续留在父节点中。
/*
* 返回所有可能与给定物体发生碰撞的物体
*/
public List retrieve(List returnObjects, Rectangle pRect) {
// 确定该物体属于哪个子节点
int index = getIndex(pRect);
// 如果找到了对应的子节点，并且该子节点已经被创建
if (index != -1 && nodes[0] != null) {
// 递归地在该子节点中查找可能碰撞的物体
nodes[index].retrieve(returnObjects, pRect);
}
// 将当前节点中的所有物体添加到返回列表中
returnObjects.addAll(objects);
// 返回结果列表
return returnObjects;
}
retrieve 方法是四叉树的最后一个核心方法。它返回所有与给定物体可能产生碰撞的节点中的物体。此方法有助于减少需要检查碰撞的物体对的数量。
具体来说，retrieve 方法通过递归查询四叉树，找到所有与指定物体可能接触或重叠的节点，并收集这些节点中的所有物体。这样可以确保只对那些真正有可能发生碰撞的物体进行检测，而不是对每个物体都进行两两比较，从而大大提高了碰撞检测的效率。
将四叉树用于 2D 碰撞检测
现在我们已经实现了一个功能完整的四叉树，接下来就可以使用它来减少进行碰撞检测所需的检查次数。
在典型的 2D 游戏中，你通常会从创建一个根节点的四叉树开始，传入屏幕或游戏世界的边界作为初始区域。然后你可以将所有需要进行碰撞检测的对象插入到四叉树中，并通过 retrieve 方法获取每个对象可能碰撞的候选对象，而不是对所有物体进行两两比较。
Quadtree quad = new Quadtree(0, new Rectangle(0,0,600,600));
在每一帧中，为了确保四叉树反映当前帧物体的位置状态，通常需要先清空四叉树，然后重新插入所有物体。这是因为大多数游戏中的物体位置是动态变化的，如果不这样做，四叉树将保留旧的、不准确的信息，从而影响碰撞检测的准确性。
quad.clear();
for (int i = 0; i < allObjects.size(); i++) {
quad.insert(allObjects.get(i));
}
一旦所有物体都被插入到四叉树中，下一步就是遍历每个物体，并使用 retrieve 方法获取它可能与之发生碰撞的其他物体列表。然后，你将对这些潜在碰撞对象进行实际的碰撞检测。
List returnObjects = new ArrayList(); // 用于存储每次检索到的潜在碰撞物体
for (int i = 0; i < allObjects.size(); i++) {
returnObjects.clear(); // 清空上一次的检索结果
// 从四叉树中检索当前物体可能与之碰撞的所有物体
quad.retrieve(returnObjects, allObjects.get(i));
// 遍历所有潜在碰撞对象，进行实际的碰撞检测
for (int x = 0; x < returnObjects.size(); x++) {
// 在这里执行具体的碰撞检测算法
// 例如：检测两个矩形是否相交、圆形碰撞检测等
}
}
我们会在其它文章讨论碰撞监测算法，这里不做展开。
结论
碰撞检测可能是一个昂贵的操作，尤其是在处理大量物体时，可能会拖慢游戏的性能。四叉树是一种可以帮助加速碰撞检测、保持游戏流畅运行的方法。
相关阅读
Use Quadtrees to Detect Likely Collisions in 2D Space
