游戏客户端架构 / 系统课时

矩形碰撞检测

矩形碰撞检测

轴对齐包围盒检测可以用常数时间判断两个矩形是否相交。本课将从“是否存在分离间隙”出发实现完整算法,并明确边缘接触、坐标约定和输入合法性。

学习目标

  • 根据矩形四条边判断两个 AABB 是否分离
  • 编写可运行的矩形相交函数并验证结果
  • 理解边缘接触规则与时间复杂度

问题定义

轴对齐包围盒简称 AABB,它的边始终与坐标轴平行。每个矩形只需保存 left、top、right、bottom 四个边界,并保证 left <= right、top <= bottom。

两个矩形相交,不必直接计算重叠面积。更简单的做法是先判断它们是否在水平方向或垂直方向完全分离;只要任意方向存在间隙,就一定没有碰撞。

分离条件

水平方向有两种分离情况:A 在 B 左侧,或 B 在 A 左侧。垂直方向也有两种:A 在 B 上方,或 B 在 A 上方。四个条件均不成立时,两个矩形发生重叠或边缘接触。

AABB 的四种分离情况

若项目把边缘接触也视为碰撞,分离判断使用严格小于号 <。若边缘接触不算碰撞,则改用小于等于号 <=,规则必须在物理系统中保持一致。

完整实现与验证

下面的 C++17 示例实现 AABB 相交函数,并分别验证重叠与完全分离两种情况。示例采用屏幕坐标系,y 轴向下,但算法本身只依赖边界大小关系。

cpp
#include <iostream>

struct Rect {
    float left;
    float top;
    float right;
    float bottom;
};

bool intersects(const Rect& a, const Rect& b) {
    // 任一水平方向存在间隙,就不可能相交。
    if (a.right < b.left || b.right < a.left) {
        return false;
    }

    // 任一垂直方向存在间隙,同样可以立即结束判断。
    if (a.bottom < b.top || b.bottom < a.top) {
        return false;
    }

    return true;
}

int main() {
    Rect a{0.0F, 0.0F, 40.0F, 30.0F};
    Rect b{30.0F, 10.0F, 60.0F, 35.0F};
    Rect c{50.0F, 40.0F, 80.0F, 70.0F};

    std::cout << std::boolalpha;
    std::cout << "A intersects B: " << intersects(a, b) << "\n";
    std::cout << "A intersects C: " << intersects(a, c) << "\n";
}

预期输出:

text
A intersects B: true
A intersects C: false

A 与 B 在水平和垂直方向都有重叠,因此返回 true;A 与 C 在两个方向都存在间隙,因此返回 false。

边界规则与复杂度

该算法只进行固定次数的比较,时间复杂度为 O(1)O(1),额外空间复杂度为 O(1)O(1)。它适合大量对象的基础检测,但若每帧让所有对象两两比较,总体仍会达到 O(n2)O(n^2),后续需要空间划分降低候选对数量。

输入矩形必须先规范化。若对象可能出现负缩放,应在生成世界 AABB 时重新计算最小边和最大边,而不是直接假设左边界小于右边界。浮点坐标还可能出现极小误差,必要时可以引入统一容差,但不能在不同系统中使用不同阈值。

本课总结

  • AABB 相交判断的核心是排除四种完全分离情况
  • < 与 <= 决定边缘接触是否算作碰撞
  • 单次检测是 O(1)O(1),大量对象仍需配合空间划分优化

下一课预告

下一课将扩展到圆形碰撞检测,并比较圆圆、圆矩形两类判定的核心差异。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

矩形碰撞检测

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通