常见的2D碰撞检测全解析：原理、实现与优化策略

2025年11月14日 互联网

常见的2D碰撞检测：原理、实现与优化策略

一、基础几何形状的碰撞检测

1.1 矩形碰撞检测（AABB）

轴对齐边界框（Axis-Aligned Bounding Box, AABB）是最基础的2D碰撞检测方法，其核心原理是通过比较两个矩形的边界坐标判断是否重叠。

实现原理：

  • 矩形A的坐标范围：(x1, y1)到(x2, y2)
  • 矩形B的坐标范围：(x3, y3)到(x4, y4)
  • 碰撞条件：x1 < x4 && x2 > x3 && y1 < y4 && y2 > y3

代码示例：

  1. function checkAABBCollision(rectA, rectB) {
  2.     return (rectA.x < rectB.x + rectB.width &&
  3.             rectA.x + rectA.width > rectB.x &&
  4.             rectA.y < rectB.y + rectB.height &&
  5.             rectA.y + rectA.height > rectB.y);
  6. }

优缺点分析：

  • 优点：计算简单，效率极高（仅需4次比较）
  • 缺点：无法处理旋转矩形，精度较低

应用场景：

  • 适用于角色、障碍物等规则形状的快速检测
  • 常作为粗检测阶段与其他方法结合使用

1.2 圆形碰撞检测

圆形碰撞通过比较两圆心距离与半径之和判断碰撞，数学原理清晰且计算高效。

数学原理：

  • 圆A：(x1, y1), radius r1
  • 圆B：(x2, y2), radius r2
  • 碰撞条件：distance(A,B) ≤ r1 + r2

代码实现：

  1. function checkCircleCollision(circleA, circleB) {
  2.     const dx = circleA.x - circleB.x;
  3.     const dy = circleA.y - circleB.y;
  4.     const distance = Math.sqrt(dx * dx + dy * dy);
  5.     return distance < circleA.radius + circleB.radius;
  6. }

性能优化技巧：

  • 避免使用平方根运算，改用距离平方比较： 
    1. function optimizedCircleCollision(circleA, circleB) {
    2.   const dx = circleA.x - circleB.x;
    3.   const dy = circleA.y - circleB.y;
    4.   const distanceSquared = dx * dx + dy * dy;
    5.   const radiusSum = circleA.radius + circleB.radius;
    6.   return distanceSquared < radiusSum * radiusSum;
    7. }

1.3 像素级碰撞检测

像素级检测通过比较两个精灵的透明像素区域实现最高精度碰撞判断。

实现方法：

  1. 创建两个精灵的遮罩图（Alpha通道）
  2. 对每个重叠像素检查Alpha值
  3. 若存在非透明像素重叠则判定碰撞

性能考量：

  • 计算复杂度与重叠区域面积成正比
  • 现代引擎通常提供优化方案：
    • 分辨率降低（如32x32像素块检测）
    • 缓存遮罩数据
    • 多线程处理

典型应用：

  • 复杂形状的精确检测
  • 物理引擎中的精细碰撞

二、空间分区优化技术

2.1 网格分区法（Spatial Hashing）

将游戏世界划分为固定大小的网格，每个对象只与所在网格及相邻网格的对象检测。

实现步骤：

  1. 确定网格单元大小（通常为最大对象尺寸的2倍）
  2. 计算对象中心点所属网格坐标： 
    1. function getGridCoord(x, y, cellSize) {
    2.  return {
    3.      x: Math.floor(x / cellSize),
    4.      y: Math.floor(y / cellSize)
    5.  };
    6. }
  3. 维护网格字典，存储各网格中的对象
  4. 碰撞检测时只需检查当前网格及8个相邻网格

性能优势：

  • 将O(n²)复杂度降至O(n + k)，k为相邻网格对象数
  • 适合动态对象较多的场景

2.2 四叉树空间分区

四叉树通过递归分割空间实现高效对象管理，特别适合非均匀分布的对象。

数据结构：

  1. class QuadTree {
  2.     constructor(boundary, capacity) {
  3.         this.boundary = boundary; // 矩形边界 {x,y,width,height}
  4.         this.capacity = capacity; // 节点容量
  5.         this.points = []; // 存储的对象
  6.         this.divided = false; // 是否已分割
  7.         this.northeast = null; // 四个子节点
  8.         // ...其他三个方向
  9.     }
  10. }

插入算法：

  1. 检查当前节点是否已满
  2. 若满则分割为4个子节点
  3. 将对象插入到合适的子节点或当前节点

查询优化：

  • 只需查询与查询区域相交的节点
  • 递归检查子节点直到叶子节点

三、高级检测算法

3.1 分离轴定理（SAT）

SAT是处理凸多边形碰撞的通用方法，通过检测投影重叠来判断碰撞。

算法步骤：

  1. 获取两个多边形的边
  2. 对每条边计算分离轴（垂直于边的法线）
  3. 将两个多边形投影到分离轴上
  4. 若任一轴上的投影不重叠，则无碰撞

代码框架：

  1. function SATCollision(polygonA, polygonB) {
  2.     const polygons = [polygonA, polygonB];
  4.     for (let i = 0; i < polygons.length; i++) {
  5.         const polygon = polygons[i];
  6.         // 获取所有边
  7.         for (let j = 0; j < polygon.vertices.length; j++) {
  8.             const edge = getEdge(polygon, j);
  9.             const axis = {x: -edge.y, y: edge.x}; // 垂直法线
  10.             normalize(axis);
  12.             // 投影两个多边形到轴上
  13.             const projA = projectPolygon(polygonA, axis);
  14.             const projB = projectPolygon(polygonB, axis);
  16.             // 检查投影是否重叠
  17.             if (!overlaps(projA, projB)) {
  18.                 return false; // 发现分离轴
  19.             }
  20.         }
  21.     }
  22.     return true;
  23. }

性能特点：

  • 计算复杂度与多边形边数成正比
  • 适用于任意凸多边形
  • 可扩展用于最小平移向量（MTV）计算

3.2 GJK碰撞检测算法

GJK（Gilbert-Johnson-Keerthi）算法通过迭代逼近实现高效碰撞检测，特别适合连续碰撞检测。

核心思想：

  1. 维护一个单纯形（点、线段、三角形或四面体）
  2. 每次迭代寻找新的支持点
  3. 通过单纯形收缩确定是否包含原点

实现要点：

  • 支持函数计算： 
    1. function support(shapeA, shapeB, direction) {
    2.   const ptA = shapeA.getFarthestPointInDirection(direction);
    3.   const ptB = shapeB.getFarthestPointInDirection(direction.negate());
    4.   return ptA.sub(ptB);
    5. }
  • 单纯形处理逻辑
  • 终止条件判断

优势：

  • 不需要预先计算距离
  • 适用于任意凸形状
  • 可扩展用于连续碰撞检测

四、实际应用建议

4.1 分层检测策略

推荐采用三级检测体系：

  1. 粗检测层：使用空间分区快速排除不可能碰撞的对象
  2. 中检测层：使用AABB或圆形检测进一步筛选
  3. 精检测层：对可能碰撞的对象使用SAT或GJK进行精确检测

4.2 性能优化技巧

  • 对象池技术：重用碰撞检测对象减少内存分配
  • 批处理检测：将检测任务分配到多个帧处理
  • 动态调整精度：根据对象速度和重要性调整检测精度
  • 缓存结果：对静态对象缓存碰撞结果

4.3 工具与框架选择

  • 简单2D游戏：使用Box2D等成熟物理引擎
  • 自定义需求：实现基础检测+空间分区优化
  • WebGL应用：考虑使用gl-matrix等数学库加速计算

五、未来发展趋势

  1. GPU加速检测：利用计算着色器实现并行碰撞检测
  2. 机器学习辅助：训练神经网络预测碰撞可能性
  3. 物理引擎融合：更紧密地集成检测与响应系统
  4. VR/AR应用：针对空间定位的特殊检测需求

本文系统梳理了2D碰撞检测的核心技术体系，从基础几何检测到高级空间分区算法，提供了完整的实现方案和优化策略。开发者可根据项目需求选择合适的技术组合，构建高效可靠的碰撞检测系统。

最新文章
热门标签