从SAT到GJK再到EPA：2D游戏碰撞检测算法实战指南
在2D游戏开发中，碰撞检测系统的性能直接影响着游戏体验的流畅度。当角色卡进墙壁、子弹穿过障碍物或物理堆叠出现抖动时，往往意味着底层碰撞算法需要优化。本文将深入解析SAT、GJK和EPA三种主流算法的实现原理，通过性能对比和实际案例，帮助开发者做出合理的技术选型。
1. 碰撞检测基础与算法选型逻辑
任何碰撞检测系统的核心任务都是回答两个问题：物体是否相交（碰撞判断）？如果相交，如何量化穿透情况（碰撞响应）？在2D环境中，开发者通常面临三类典型场景：
- 简单几何的快速检测：适用于休闲游戏中的矩形/圆形碰撞
- 复杂凸多边形的精确判断：常见于物理模拟和平台跳跃游戏
- 高速运动物体的连续检测：解决子弹时间等特效中的穿透问题
算法性能关键指标对比表：
| 指标 | SAT算法 | GJK算法 | EPA算法 |
|---|---|---|---|
| 时间复杂度 | O(n²) | O(迭代次数) | O(迭代次数) |
| 适用形状 | 凸多边形 | 任意凸体 | 任意凸体 |
| 内存消耗 | 低 | 中 | 高 |
| 穿透深度计算 | 不支持 | 不支持 | 支持 |
| 实现复杂度 | 简单 | 中等 | 复杂 |
实际项目中，建议通过以下决策树选择算法：
- 如果只需要布尔型碰撞判断且形状简单 → 选择SAT
- 如果需要处理复杂凸体且关注性能 → 选择GJK
- 如果需要精确的穿透向量用于物理响应 → 结合GJK+EPA
2. SAT算法：简单几何的利刃
分离轴定理(SAT)的核心思想令人惊讶地直观：如果能找到一条直线，使得两个多边形的投影在此直线上不重叠，则它们必定没有碰撞。这种方法的优势在于将二维碰撞问题转化为一维区间判断。
典型实现步骤：
def sat_collision(poly_a, poly_b): axes = get_all_axes(poly_a, poly_b) for axis in axes: proj_a = project(poly_a, axis) proj_b = project(poly_b, axis) if not overlap(proj_a, proj_b): return False # 存在分离轴 return True # 所有轴都重叠实际开发中容易遇到的三个陷阱：
- 顶点顺序问题：必须保证多边形顶点按统一时针方向排列
- 法向量计算错误：边的法向量应通过
(y, -x)计算而非(-y, x) - 投影优化：可以提前计算并缓存多边形的最小/最大投影值
提示：对于包含圆弧的凸形状，可将圆弧离散为多个线段后应用SAT
3. GJK算法：凸体碰撞的高效解法
Gilbert-Johnson-Keerthi算法通过明可夫斯基差将碰撞检测转化为原点包含问题，其精妙之处在于用迭代方式逼近结果，避免了直接计算复杂的几何差集。
关键组件实现：
// Support函数示例 Vector2 Support(const Shape& shape, const Vector2& dir) { float max_dot = -FLT_MAX; Vector2 best_vertex; for (const auto& v : shape.vertices) { float dot = v.Dot(dir); if (dot > max_dot) { max_dot = dot; best_vertex = v; } } return best_vertex; }性能优化技巧：
- 方向向量缓存：保留上一次成功的搜索方向作为初始值
- 提前终止：当单纯形顶点与原点距离小于阈值时提前返回
- Warm Start：利用物体运动的连续性，用上一帧的单纯形初始化当前检测
在物理引擎中常见的实现缺陷包括：
- 未处理共线/共面顶点导致算法陷入死循环
- 浮点误差累积造成误判
- 未实现适当的迭代次数限制
4. EPA算法：穿透深度的专业解决方案
当GJK检测到碰撞后，扩展多边形算法(EPA)通过逐步扩展单纯形来计算穿透向量。这个过程类似于用多边形包裹原点，直到找到最近的边缘。
EPA实现要点：
- 初始化阶段使用GJK终止时的单纯形
- 每次迭代选择当前多边形中距离原点最近的边
- 沿该边法线方向获取新的support点
- 当新点不改变最近边距离时终止
def epa_penetration(gjk_simplex): polytope = build_initial_polytope(gjk_simplex) while True: edge = find_closest_edge(polytope) new_point = support(edge.normal) distance = new_point.dot(edge.normal) if abs(distance - edge.distance) < EPSILON: return edge.normal * distance # 穿透向量 polytope.insert_point(edge.index, new_point)实际项目中建议：
- 设置最大迭代次数防止极端情况下的性能问题
- 对穿透深度施加阈值，避免微观穿透导致的物理不稳定
- 结合运动预测减少EPA调用频率
5. 混合策略与进阶优化
成熟的物理引擎往往采用混合策略。例如Box2D的处理流程：
- 先用AABB快速排除不相交物体
- 简单形状使用特化算法（如圆-圆碰撞）
- 复杂凸体调用GJK进行粗检测
- 需要碰撞响应时触发EPA计算
内存优化方案：
- 对象池模式：重用单纯形和多边形数据结构
- SIMD加速：用并行指令优化向量运算
- 惰性计算：只在首次碰撞时构建完整几何数据
对于特殊场景的处理建议：
- 高速物体：结合扫掠形状和连续碰撞检测(CCD)
- 堆叠物体：增加穿透容差并启用休眠机制
- 可破坏物体：预计算凸分解并建立碰撞代理
在实现过程中，建议使用可视化调试工具实时显示单纯形构建过程、搜索方向和支持点，这能极大降低算法调试难度。一个实用的技巧是用不同颜色标记GJK的各迭代阶段，当算法出现异常时，这些视觉线索往往比日志输出更有助于定位问题根源。
