常见的 2D 碰撞检测

2025年10月12日 互联网

在2D游戏开发中，碰撞检测是构建物理交互的核心技术。无论是角色移动、道具拾取还是技能释放，精准的碰撞检测直接影响游戏体验的流畅性与真实性。本文将从基础几何方法、空间分区优化及实用技巧三个维度，系统梳理常见的2D碰撞检测方案，为开发者提供可落地的技术参考。

一、基础几何方法：从简单到复杂的碰撞判定

1. 轴对齐边界框（AABB）检测

AABB（Axis-Aligned Bounding Box）是最基础的碰撞检测方法，通过比较两个矩形在X轴和Y轴上的投影是否重叠来判断碰撞。其核心逻辑如下：

  1. def aabb_collision(rect1, rect2):
  2.     return (rect1.x < rect2.x + rect2.width and
  3.             rect1.x + rect1.width > rect2.x and
  4.             rect1.y < rect2.y + rect2.height and
  5.             rect1.y + rect1.height > rect2.y)

优势：计算复杂度仅为O(1)，适合移动设备或大规模对象检测。
局限：无法处理旋转矩形，对非规则形状精度不足。
应用场景：角色与静态场景（如墙壁、平台）的快速检测。

2. 圆形碰撞检测

通过比较两个圆形的圆心距离与半径之和判断碰撞：

  1. def circle_collision(circle1, circle2):
  2.     dx = circle1.x - circle2.x
  3.     dy = circle1.y - circle2.y
  4.     distance = (dx**2 + dy**2)**0.5
  5.     return distance < (circle1.radius + circle2.radius)

优势：计算简单，适合子弹、粒子等圆形对象的检测。
优化技巧：使用距离平方比较避免开方运算：

  1. def optimized_circle_collision(circle1, circle2):
  2.     dx = circle1.x - circle2.x
  3.     dy = circle1.y - circle2.y
  4.     distance_squared = dx*dx + dy*dy
  5.     return distance_squared < (circle1.radius + circle2.radius)**2

3. 分离轴定理（SAT）检测

SAT适用于任意凸多边形，通过检测多边形在各轴上的投影是否分离来判断碰撞。核心步骤如下：

  1. 提取多边形的边法向量作为检测轴。
  2. 将两个多边形投影到各轴上，计算投影区间。
  3. 若任一轴上投影不重叠，则无碰撞。

实现示例（简化版）：

  1. def sat_collision(polygon1, polygon2):
  2.     axes = []
  3.     # 提取polygon1的边法向量
  4.     for i in range(len(polygon1)):
  5.         edge = (polygon1[(i+1)%len(polygon1)] - polygon1[i])
  6.         normal = (-edge.y, edge.x)  # 垂直于边的向量
  7.         axes.append(normal)
  8.     # 提取polygon2的边法向量
  9.     for i in range(len(polygon2)):
  10.         edge = (polygon2[(i+1)%len(polygon2)] - polygon2[i])
  11.         normal = (-edge.y, edge.x)
  12.         axes.append(normal)
  14.     for axis in axes:
  15.         # 投影polygon1到轴上
  16.         min1, max1 = project_polygon(polygon1, axis)
  17.         # 投影polygon2到轴上
  18.         min2, max2 = project_polygon(polygon2, axis)
  19.         # 检查投影是否重叠
  20.         if max1 < min2 or max2 < min1:
  21.             return False
  22.     return True

优势：支持任意凸多边形，精度高。
局限：计算复杂度为O(n+m)，n和m为多边形边数，需优化。

二、空间分区优化：提升大规模场景检测效率

1. 四叉树（Quadtree）分区

四叉树通过递归划分空间为四个象限，仅检测同一分区或相邻分区的对象。核心逻辑如下：

  1. class QuadtreeNode:
  2.     def __init__(self, boundary, capacity):
  3.         self.boundary = boundary  # 分区边界（矩形）
  4.         self.capacity = capacity  # 分区容量
  5.         self.points = []          # 存储对象
  6.         self.divided = False      # 是否已划分子分区
  7.         self.children = []        # 子分区（东北、西北、东南、西南）
  9.     def insert(self, point):
  10.         if not self.boundary.contains(point):
  11.             return False
  12.         if len(self.points) < self.capacity and not self.divided:
  13.             self.points.append(point)
  14.             return True
  15.         if not self.divided:
  16.             self.subdivide()
  17.         return (self.children[0].insert(point) or
  18.                 self.children[1].insert(point) or
  19.                 self.children[2].insert(point) or
  20.                 self.children[3].insert(point))

优势：将O(n²)的复杂度降至O(n log n)，适合动态对象较多的场景。
应用场景：开放世界游戏中的对象管理。

2. 网格（Grid）分区

网格将场景划分为固定大小的单元格，每个单元格存储其中的对象。检测时仅需检查当前单元格及相邻单元格的对象。

  1. class Grid:
  2.     def __init__(self, cell_size):
  3.         self.cell_size = cell_size
  4.         self.grid = {}  # 键为(x_cell, y_cell)，值为对象列表
  6.     def get_cell_key(self, x, y):
  7.         return (int(x // self.cell_size), int(y // self.cell_size))
  9.     def insert(self, obj):
  10.         key = self.get_cell_key(obj.x, obj.y)
  11.         if key not in self.grid:
  12.             self.grid[key] = []
  13.         self.grid[key].append(obj)
  15.     def query_range(self, x, y, radius):
  16.         # 查询以(x,y)为中心，radius为半径的范围内的对象
  17.         objects = []
  18.         min_cell_x = int((x - radius) // self.cell_size)
  19.         max_cell_x = int((x + radius) // self.cell_size)
  20.         min_cell_y = int((y - radius) // self.cell_size)
  21.         max_cell_y = int((y + radius) // self.cell_size)
  22.         for cell_x in range(min_cell_x, max_cell_x + 1):
  23.             for cell_y in range(min_cell_y, max_cell_y + 1):
  24.                 key = (cell_x, cell_y)
  25.                 if key in self.grid:
  26.                     for obj in self.grid[key]:
  27.                         if distance_squared(x, y, obj.x, obj.y) < radius * radius:
  28.                             objects.append(obj)
  29.         return objects

优势：实现简单，适合静态或低速移动对象。
优化技巧：动态调整单元格大小以平衡内存与性能。

三、实用技巧与注意事项

1. 宽相位与窄相位检测

  • 宽相位检测：使用AABB或圆形快速排除明显不碰撞的对象。
  • 窄相位检测：对宽相位筛选后的对象使用SAT或像素级检测。

2. 连续碰撞检测（CCD）

针对高速移动对象，传统检测可能漏判。CCD通过计算运动轨迹与对象的交点来避免穿透：

  1. def ccd_collision(obj1, obj2, dt):
  2.     # 计算obj1在dt时间内的运动向量
  3.     velocity = (obj1.velocity_x * dt, obj1.velocity_y * dt)
  4.     # 检测运动路径是否与obj2碰撞（需结合SAT或射线检测）
  5.     ...

应用场景：子弹、高速移动的角色。

3. 性能优化策略

  • 对象池：复用检测对象以减少内存分配。
  • 分层检测：按对象类型（如角色、道具）分层检测。
  • 多线程：将检测任务分配至多个线程。

四、总结与建议

  1. 简单场景优先AABB/圆形检测：快速且低开销。
  2. 复杂形状使用SAT：确保精度但需优化计算。
  3. 大规模场景结合空间分区：四叉树或网格可显著提升性能。
  4. 高速对象启用CCD：避免穿透问题。

通过合理选择检测方法与优化策略，开发者可在保证游戏性能的同时，实现流畅的物理交互体验。

最新文章