每日算法 — 使用java实现AABB碰撞检测：包围盒层次结构与四叉树空间加速

引言

AABB（Axis-Aligned Bounding Box，轴对齐包围盒）碰撞检测是2D游戏物理引擎的基石。从早期的《吃豆人》到现代的《王者荣耀》，几乎每一款游戏都离不开高效的碰撞检测系统。当场景中同时存在成百上千个动态对象时，暴力O(n²)的两两检测将迅速成为性能瓶颈。本文将用Java实现一套完整的AABB碰撞检测系统，核心讲解四叉树空间划分算法如何将碰撞检测复杂度从O(n²)降低到O(n log n)。

AABB基础概念

轴对齐包围盒定义

AABB是与坐标轴平行的矩形，由左下角坐标 (minX, minY) 和右上角坐标 (maxX, maxY) 唯一确定：

public class AABB {
    public float minX, minY, maxX, maxY;
    public int id; // 对象唯一标识

    public AABB(int id, float minX, float minY, float maxX, float maxY) {
        this.id = id;
        this.minX = minX;
        this.minY = minY;
        this.maxX = maxX;
        this.maxY = maxY;
    }

    /**
     * 判断两个AABB是否相交
     * 分离轴定理的简化版：若两矩形在X轴或Y轴上投影不重叠，则不相交
     */
    public boolean intersects(AABB other) {
        return this.minX <= other.maxX && this.maxX >= other.minX &&
               this.minY <= other.maxY && this.maxY >= other.minY;
    }

    /**
     * 计算AABB的面积
     */
    public float area() {
        return (maxX - minX) * (maxY - minY);
    }

    /**
     * 判断点是否在AABB内
     */
    public boolean contains(float x, float y) {
        return x >= minX && x <= maxX && y >= minY && y <= maxY;
    }

    @Override
    public String toString() {
        return String.format("AABB[%d](%.1f,%.1f,%.1f,%.1f)", id, minX, minY, maxX, maxY);
    }
}

暴力检测与性能瓶颈

import java.util.*;

public class BruteForceCollision {

    /**
     * 暴力两两检测所有对象对
     * 时间复杂度: O(n²)
     */
    static List<String> bruteForceDetect(List<AABB> objects) {
        List<String> collisions = new ArrayList<>();
        int n = objects.size();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (objects.get(i).intersects(objects.get(j))) {
                    collisions.add(objects.get(i).id + "-" + objects.get(j).id);
                }
            }
        }
        return collisions;
    }
}

当 n = 1000 时，需要进行约50万次相交测试；当 n = 10000 时，测试次数飙升至约5000万次。这在实时游戏中是不可接受的。

四叉树空间划分加速

四叉树核心思想

四叉树（Quadtree）递归地将2D空间划分为四个象限。每个节点最多包含 MAX_OBJECTS 个对象；当对象数量超过阈值时，节点分裂为四个子节点：

public class QuadTree {

    private static final int MAX_OBJECTS = 4;  // 节点最大对象数
    private static final int MAX_LEVELS = 5;   // 最大递归深度

    private int level;
    private AABB bounds;       // 当前节点覆盖的矩形区域
    private List<AABB> objects; // 落入该区域的对象
    private QuadTree[] nodes;   // 四个子节点：0=NW, 1=NE, 2=SW, 3=SE

    public QuadTree(int level, AABB bounds) {
        this.level = level;
        this.bounds = bounds;
        this.objects = new ArrayList<>();
        this.nodes = new QuadTree[4];
    }

    /**
     * 将当前节点分裂为4个子节点
     */
    private void split() {
        float subWidth = (bounds.maxX - bounds.minX) / 2;
        float subHeight = (bounds.maxY - bounds.minY) / 2;
        float x = bounds.minX;
        float y = bounds.minY;

        // 右上 (NE)
        nodes[0] = new QuadTree(level + 1, new AABB(-1, x + subWidth, y, x + 2*subWidth, y + subHeight));
        // 左上 (NW)  
        nodes[1] = new QuadTree(level + 1, new AABB(-1, x, y, x + subWidth, y + subHeight));
        // 右下 (SE)
        nodes[2] = new QuadTree(level + 1, new AABB(-1, x + subWidth, y + subHeight, x + 2*subWidth, y + 2*subHeight));
        // 左下 (SW)
        nodes[3] = new QuadTree(level + 1, new AABB(-1, x, y + subHeight, x + subWidth, y + 2*subHeight));
    }

    /**
     * 判断对象完全落入哪个象限
     * 返回值: 0=NE, 1=NW, 2=SE, 3=SW, -1=跨越多个象限
     */
    private int getIndex(AABB obj) {
        float midX = (bounds.minX + bounds.maxX) / 2;
        float midY = (bounds.minY + bounds.maxY) / 2;

        boolean top = obj.minY >= bounds.minY && obj.maxY <= midY;
        boolean bottom = obj.minY >= midY && obj.maxY <= bounds.maxY;
        boolean left = obj.minX >= bounds.minX && obj.maxX <= midX;
        boolean right = obj.minX >= midX && obj.maxX <= bounds.maxX;

        if (top) {
            if (right) return 0; // NE
            if (left) return 1;  // NW
        } else if (bottom) {
            if (right) return 2; // SE
            if (left) return 3;  // SW
        }
        return -1; // 跨越多个象限，留在当前节点
    }
}

插入与检索

/**
 * 将对象插入四叉树
 */
public void insert(AABB obj) {
    // 若有子节点，尝试放入子节点
    if (nodes[0] != null) {
        int index = getIndex(obj);
        if (index != -1) {
            nodes[index].insert(obj);
            return;
        }
    }

    objects.add(obj);

    // 超过容量且未达最大深度，分裂节点
    if (objects.size() > MAX_OBJECTS && level < MAX_LEVELS) {
        if (nodes[0] == null) split();

        // 将当前对象重新分配到子节点
        Iterator<AABB> it = objects.iterator();
        while (it.hasNext()) {
            AABB o = it.next();
            int index = getIndex(o);
            if (index != -1) {
                nodes[index].insert(o);
                it.remove();
            }
        }
    }
}

/**
 * 检索可能与给定对象碰撞的所有对象
 */
public List<AABB> retrieve(List<AABB> result, AABB obj) {
    int index = getIndex(obj);
    if (index != -1 && nodes[0] != null) {
        nodes[index].retrieve(result, obj);
    }
    result.addAll(objects);
    return result;
}

/**
 * 清空四叉树（每帧重建）
 */
public void clear() {
    objects.clear();
    for (int i = 0; i < 4; i++) {
        if (nodes[i] != null) {
            nodes[i].clear();
            nodes[i] = null;
        }
    }
}

基于四叉树的碰撞检测系统

public class QuadTreeCollisionSystem {

    private QuadTree tree;
    private Set<String> collisionPairs;

    public QuadTreeCollisionSystem(AABB worldBounds) {
        this.tree = new QuadTree(0, worldBounds);
        this.collisionPairs = new HashSet<>();
    }

    /**
     * 每帧执行碰撞检测
     */
    public Set<String> detectCollisions(List<AABB> objects) {
        collisionPairs.clear();
        tree.clear();

        // 构建四叉树
        for (AABB obj : objects) {
            tree.insert(obj);
        }

        // 对每个对象，检索候选碰撞对象并精确检测
        for (AABB obj : objects) {
            List<AABB> candidates = new ArrayList<>();
            tree.retrieve(candidates, obj);

            for (AABB other : candidates) {
                if (obj.id != other.id && obj.intersects(other)) {
                    // 使用有序对去重
                    String pair = obj.id < other.id ? 
                        obj.id + "-" + other.id : other.id + "-" + obj.id;
                    collisionPairs.add(pair);
                }
            }
        }

        return collisionPairs;
    }
}

性能对比测试

public static void main(String[] args) {
    Random rand = new Random(42);
    int[] sizes = {100, 500, 1000, 5000};

    for (int n : sizes) {
        List<AABB> objects = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            float x = rand.nextFloat() * 800;
            float y = rand.nextFloat() * 600;
            float w = 10 + rand.nextFloat() * 40;
            float h = 10 + rand.nextFloat() * 40;
            objects.add(new AABB(i, x, y, x + w, y + h));
        }

        // 暴力检测
        long start = System.nanoTime();
        List<String> brute = BruteForceCollision.bruteForceDetect(objects);
        long bruteTime = System.nanoTime() - start;

        // 四叉树检测
        AABB world = new AABB(-1, 0, 0, 800, 600);
        QuadTreeCollisionSystem qt = new QuadTreeCollisionSystem(world);
        start = System.nanoTime();
        Set<String> quad = qt.detectCollisions(objects);
        long quadTime = System.nanoTime() - start;

        System.out.printf("n=%d: 暴力=%d对 (%.2fms), 四叉树=%d对 (%.2fms), 加速比=%.1fx%n",
            n, brute.size(), bruteTime / 1e6, quad.size(), quadTime / 1e6, 
            (double)bruteTime / quadTime);
    }
}

Sweep and Prune优化（一维投影）

对于物体分布密集的场景，Sweep and Prune（SAP）是另一种高效方法：

public class SweepAndPrune {

    /**
     * SAP算法：按X轴投影排序，仅检查投影重叠的相邻对象
     */
    static List<String> sapDetect(List<AABB> objects) {
        // 构建端点列表（每个对象产生minX和maxX两个端点）
        List<Endpoint> endpoints = new ArrayList<>();
        for (AABB obj : objects) {
            endpoints.add(new Endpoint(obj.minX, obj, true));  // 起始端点
            endpoints.add(new Endpoint(obj.maxX, obj, false)); // 终止端点
        }

        // 按X坐标排序
        endpoints.sort(Comparator.comparingDouble(e -> e.value));

        List<String> collisions = new ArrayList<>();
        Set<AABB> active = new HashSet<>(); // 当前活跃的区间

        for (Endpoint ep : endpoints) {
            if (ep.isStart) {
                // 新对象开始：与所有活跃对象进行Y轴相交测试
                for (AABB other : active) {
                    if (ep.obj.intersects(other)) {
                        String pair = ep.obj.id < other.id ?
                            ep.obj.id + "-" + other.id : other.id + "-" + ep.obj.id;
                        collisions.add(pair);
                    }
                }
                active.add(ep.obj);
            } else {
                active.remove(ep.obj);
            }
        }
        return collisions;
    }

    static class Endpoint {
        float value;
        AABB obj;
        boolean isStart;
        Endpoint(float v, AABB o, boolean s) { value=v; obj=o; isStart=s; }
    }
}

复杂度分析

其中 k 为实际碰撞对数。

小结

本文实现了完整的2D AABB碰撞检测系统：
– AABB相交测试的分离轴定理简化实现
– 四叉树空间划分的插入、检索与分裂机制
– 基于四叉树的批量碰撞检测流程
– Sweep and Prune作为补充优化方案

四叉树的核心价值在于：通过空间局部性原理，将全局O(n²)问题转化为局部的O(1)或O(log n)问题。这种”分而治之”的思想，正是算法设计中最具普适性的策略之一。