II · 碰撞检测与物理§ 2.1

基础相交测试：AABB、圆与射线

子弹有没有打中敌人？角色是不是站在平台上？鼠标点中了哪个单位？碰撞检测的一切都从几个最简单的形状开始：轴对齐盒子、圆和射线。

卷二导读：一次碰撞检测要经过哪些步骤

游戏里每一帧都要回答“谁和谁碰到了”。物体一多，两两检查就会变成 n² 的灾难，所以物理引擎通常把这个问题拆成三步：

阶段	做什么	本卷章节
宽相（broad phase）	用很粗糙但很快的方法，排除绝大多数不可能相碰的物体对	2.4 ~ 2.6
窄相（narrow phase）	对剩下的物体对做精确的相交测试，并算出接触信息	2.1 ~ 2.3
响应（response）	根据接触信息把物体分开，调整速度	2.7 ~ 2.9

这一篇是窄相的起点：三种最简单、也最常用的形状。它们简单到几乎每个游戏都会直接用，复杂的形状也往往先套一个盒子或圆做初步判断。

问题：最常见的三个问题

两个东西重叠了吗？ 玩家碰到了金币、敌人进入了警戒范围、子弹打中了箱子。
重叠了多少，往哪边分开？ 角色撞到墙上，需要被推回去，而且推回的距离要恰好。
一条射线最先碰到什么？ 激光、即时命中的武器、鼠标点选、AI 的视线检查。

三种形状

// 轴对齐包围盒（Axis-Aligned Bounding Box）：边与坐标轴平行的矩形
struct Aabb {
    Vec2 min, max;
    Vec2 center() const { return (min + max) * 0.5f; }
    Vec2 half() const { return (max - min) * 0.5f; }
};

struct Circle {
    Vec2 center;
    float radius;
};

// 射线：origin + t * dir，t ≥ 0。dir 不要求是单位向量，t 以 dir 的长度为单位
struct Ray {
    Vec2 origin, dir;
    Vec2 at(float t) const { return origin + dir * t; }
};

AABB（Axis-Aligned Bounding Box，轴对齐包围盒）是边与坐标轴平行的矩形，用左上角和右下角两个点表示。它不能旋转，但正因为如此，所有测试都可以拆成 x、y 两个方向分别处理，非常快。

相交判断

// 两个区间 [a0, a1] 和 [b0, b1] 有重叠，当且仅当谁都不完全在对方的一侧
inline bool overlaps(const Aabb& a, const Aabb& b) {
    return a.min.x < b.max.x && b.min.x < a.max.x &&  // x 方向有重叠
           a.min.y < b.max.y && b.min.y < a.max.y;    // y 方向有重叠
}

// 比较距离的平方，省掉一次开方
inline bool overlaps(const Circle& a, const Circle& b) {
    Vec2 d = b.center - a.center;
    float r = a.radius + b.radius;
    return dot(d, d) < r * r;
}

// 盒子上离 p 最近的点：把 p 的每个坐标夹到盒子的范围内
inline Vec2 closestPoint(const Aabb& box, Vec2 p) {
    return {std::clamp(p.x, box.min.x, box.max.x), std::clamp(p.y, box.min.y, box.max.y)};
}

inline bool overlaps(const Circle& c, const Aabb& box) {
    Vec2 d = c.center - closestPoint(box, c.center);
    return dot(d, d) < c.radius * c.radius;
}
inline bool overlaps(const Aabb& box, const Circle& c) { return overlaps(c, box); }

三个测试各有一个值得记住的思路：

AABB 与 AABB：两个盒子重叠，当且仅当它们在 x 方向和 y 方向上都有重叠。只要有一个方向分开了，它们就不相交。这个“找一个分开的方向”的想法，下一篇会推广成分离轴定理。
圆与圆：圆心距离小于半径之和。比较距离的平方，可以省掉一次开方。
圆与 AABB：先找到盒子上离圆心最近的点，只需要把圆心的每个坐标夹到盒子的范围内，再判断这个点是否在圆里。

亲手试一试

图 2.1拖动盒子 A、B 和圆 C、D。重叠的形状描红，红色箭头是最小分离向量，数字是穿透深度。拖动射线的起点（实心圆）和方向柄（空心圆，t = 1 的位置）。slabs 显示盒子 A 的两条板以及射线在其中的参数区间；separate 沿最小分离向量把重叠的形状推开。单独打开 ↗

几个值得做的小实验：

把圆 D 拖到盒子 B 的角上，观察分离向量：它从盒子的角点指向圆心，而不是沿着某条边。
把圆 C 的圆心完全拖进盒子 A 里面。分离向量变成垂直于最近的那条边，长度是“圆心到这条边的距离 + 半径”。
打开 slabs，让射线穿过盒子 A，对比两段区间：射线先进入 x 板、后进入 y 板（或者反过来），两段区间重叠的部分就是射线在盒子里的部分。
让射线与 x 轴平行地擦过盒子的上边，看看它什么时候算命中。

不只是“是否重叠”：接触信息

知道两个物体重叠还不够。把角色从墙里推出来，需要知道往哪个方向推、推多远。这就是最小分离向量（Minimum Translation Vector，MTV）：沿着它移动，两个形状恰好分开，而且移动的距离最短。

// 接触信息：把 b 沿 normal 移动 depth，两者就恰好分开（最小分离向量，MTV）。
// normal 是单位向量，从 a 指向 b。
struct Contact {
    Vec2 normal;
    float depth;
    Vec2 point;  // 一个代表性的接触点，用于显示和计算力矩
};

inline std::optional<Contact> contact(const Aabb& a, const Aabb& b) {
    // 每个轴上，b 可以往正方向推出（推到 a.max 外）或往负方向推出（推到 a.min 外），取较短的一个。
    // 注意：这不等于两个区间的重叠长度 —— 一个区间包含另一个时，要推出的距离比重叠长度更长
    float px = std::min(a.max.x - b.min.x, b.max.x - a.min.x);
    float py = std::min(a.max.y - b.min.y, b.max.y - a.min.y);
    if (px <= 0 || py <= 0) return std::nullopt;
    float sx = (a.max.x - b.min.x) < (b.max.x - a.min.x) ? 1.0f : -1.0f;
    float sy = (a.max.y - b.min.y) < (b.max.y - a.min.y) ? 1.0f : -1.0f;
    Vec2 lo{std::max(a.min.x, b.min.x), std::max(a.min.y, b.min.y)};
    Vec2 hi{std::min(a.max.x, b.max.x), std::min(a.max.y, b.max.y)};
    Vec2 mid = (lo + hi) * 0.5f;  // 重叠区域的中心
    // 沿推出距离较短的轴分开
    if (px < py) return Contact{{sx, 0}, px, mid};
    return Contact{{0, sy}, py, mid};
}

inline std::optional<Contact> contact(const Circle& a, const Circle& b) {
    Vec2 d = b.center - a.center;
    float dist2 = dot(d, d), r = a.radius + b.radius;
    if (dist2 >= r * r) return std::nullopt;
    float dist = std::sqrt(dist2);
    Vec2 n = dist > 1e-6f ? d / dist : Vec2{1, 0};  // 圆心重合时随便选一个方向
    return Contact{n, r - dist, a.center + n * a.radius};
}

// 盒子 a 与圆 b
inline std::optional<Contact> contact(const Aabb& a, const Circle& b) {
    Vec2 q = closestPoint(a, b.center);
    Vec2 d = b.center - q;
    float dist2 = dot(d, d);
    if (dist2 > 1e-12f) {  // 圆心在盒子外：沿"最近点 → 圆心"分开
        if (dist2 >= b.radius * b.radius) return std::nullopt;
        float dist = std::sqrt(dist2);
        return Contact{d / dist, b.radius - dist, q};
    }
    // 圆心在盒子内：找最近的一条边，从那里推出去
    Vec2 p = b.center;
    float left = p.x - a.min.x, right = a.max.x - p.x, top = p.y - a.min.y, bottom = a.max.y - p.y;
    float m = std::min({left, right, top, bottom});
    Vec2 n = m == left ? Vec2{-1, 0} : m == right ? Vec2{1, 0} : m == top ? Vec2{0, -1} : Vec2{0, 1};
    return Contact{n, b.radius + m, p + n * m};
}

圆与盒子的接触分两种情况。圆心在盒子外时，分离方向就是“最近点 → 圆心”；圆心已经进入盒子内部时，最近点就是圆心自己，方向无从谈起，这时改为找最近的一条边，从那里推出去。

射线检测

射线与 AABB：slab 法

一个 AABB 可以看成两条“板”（slab）的交集：一条是 min.x ≤ x ≤ max.x 的竖条，一条是 min.y ≤ y ≤ max.y 的横条。

射线 origin + t·dir 穿过每条板时，都对应一段参数区间 [t进入, t离开]。射线在盒子里，当且仅当它同时在两条板里，也就是两段区间的交集。交集的起点，就是射线进入盒子的位置；最后进入的那条板，决定了命中的是哪个面。

struct RayHit {
    float t;      // 命中参数：命中点 = ray.at(t)
    Vec2 point;
    Vec2 normal;  // 命中表面的外法线；射线起点在形状内部时为零向量
};

// slab 法：盒子是 x 方向和 y 方向两条"板"（slab）的交集。
// 分别求出射线在每条板内的参数区间 [tEnter, tExit]，两个区间的交集非空就命中
inline std::optional<RayHit> raycast(const Ray& ray, const Aabb& box,
                                     float tMax = std::numeric_limits<float>::infinity()) {
    float tMin = 0;
    Vec2 normal{0, 0};
    for (int axis = 0; axis < 2; ++axis) {
        float o = axis == 0 ? ray.origin.x : ray.origin.y;
        float d = axis == 0 ? ray.dir.x : ray.dir.y;
        float lo = axis == 0 ? box.min.x : box.min.y;
        float hi = axis == 0 ? box.max.x : box.max.y;
        if (std::abs(d) < 1e-9f) {  // 与这条板平行：起点必须在板内，否则永远碰不到
            if (o < lo || o > hi) return std::nullopt;
            continue;
        }
        float t1 = (lo - o) / d, t2 = (hi - o) / d;  // 进入、离开这条板的参数
        float sign = -1;                             // 从 lo 一侧进入时，法线指向负方向
        if (t1 > t2) {
            std::swap(t1, t2);
            sign = 1;
        }
        if (t1 > tMin) {  // 最晚进入的那条板决定了命中面
            tMin = t1;
            normal = axis == 0 ? Vec2{sign, 0} : Vec2{0, sign};
        }
        tMax = std::min(tMax, t2);
        if (tMin > tMax) return std::nullopt;  // 两个区间不再重叠
    }
    return RayHit{tMin, ray.at(tMin), normal};
}

// 解 |origin + t·dir - center|² = r²，取较小的根
inline std::optional<RayHit> raycast(const Ray& ray, const Circle& c,
                                     float tMax = std::numeric_limits<float>::infinity()) {
    Vec2 m = ray.origin - c.center;
    float a = dot(ray.dir, ray.dir);
    float b = dot(m, ray.dir);
    float k = dot(m, m) - c.radius * c.radius;  // k > 0：起点在圆外
    if (k > 0 && b > 0) return std::nullopt;    // 起点在圆外且背对圆心
    float disc = b * b - a * k;
    if (disc < 0) return std::nullopt;  // 射线所在的直线与圆不相交
    float t = (-b - std::sqrt(disc)) / a;
    if (t < 0) return RayHit{0, ray.origin, {0, 0}};  // 起点在圆内
    if (t > tMax) return std::nullopt;
    Vec2 p = ray.at(t);
    return RayHit{t, p, (p - c.center) / c.radius};
}

射线与圆

把射线方程代入圆的方程 |p - center|² = r²，得到一个关于 t 的一元二次方程。判别式小于 0，说明射线所在的直线与圆不相交；否则较小的根就是进入圆的位置。

注意 dir 不要求是单位向量，t 以 dir 的长度为单位。演示里方向柄所在的位置是 t = 1。这很方便：用“起点到终点”作为 dir，t ≤ 1 就表示命中点在线段上，同一套代码就可以做线段检测。

常见陷阱

问题	原因	解决
角色站在地面上不停抖动	边缘接触也算作重叠	相交判断用严格小于；或者给接触留一个很小的容差
推出墙后又陷进另一面墙	AABB 穿透深度用了重叠长度	分别计算两个方向的推出距离，取较小者
射线检测偶尔返回 NaN	射线与板平行，起点又恰好在板的边界上	显式处理平行的情况
射线起点在物体内部时行为奇怪	不同实现约定不同：有的返回 t = 0，有的返回离开的位置	明确约定；本文返回 t = 0、法线为零
高速子弹穿过薄墙	每帧只检查一次位置，两帧之间直接越过了墙	用射线检测上一帧到这一帧的线段，见 2.9
大地图上碰撞判断出错	坐标很大时 float 精度不够	以玩家附近为原点做相对坐标，或使用 double

在游戏中的应用

触发区域：存档点、陷阱、剧情触发器，几乎都是 AABB 或圆。
平台跳跃的地面检测：从角色脚下向下发射两三条很短的射线，判断是否站在地面上，以及地面的法线（斜坡）。
即时命中武器与激光：一条射线，找最近的命中。
鼠标点选：把屏幕坐标转换成世界坐标，判断落在哪个物体的包围盒里；3D 中则是从摄像机发出一条射线。
AI 的视线检查：从敌人眼睛向玩家发射射线，中间如果先命中了墙，就看不见。0.2 的视野锥判断加上这一步，就是完整的“能否看见”。

练习

实现线段与 AABB 的相交测试，只需要调用 raycast 并传入合适的 tMax。
移动的盒子：盒子 A 这一帧要移动 v，它会不会撞上静止的盒子 B？提示：把 B 向四周扩大 A 的半宽和半高，再从 A 的中心沿 v 发射一条射线。这就是 2.9 连续碰撞检测的基础。
实现“胶囊”（两端是半圆的线段）与圆的相交测试。提示：找线段上离圆心最近的点。
实现射线与凸多边形的相交测试，思路与 slab 法相同：每条边定义一个半平面。