碰撞检测 SAT算法 示例

SAT算法（Separating Axis Theorem，分离轴定理）是一种常用于二维和三维碰撞检测的算法。它的基本思路是，如果两个物体之间不存在分离轴（即二者的投影重叠），则它们一定发生了碰撞。下面我们以二维碰撞检测为例，给出一个基于SAT算法的示例。

假设我们有两个矩形，分别用四个顶点表示为：

矩形A：A1(x1, y1), A2(x2, y1), A3(x2, y2), A4(x1, y2)
矩形B：B1(x3, y3), B2(x4, y3), B3(x4, y4), B4(x3, y4)

首先，我们需要找到所有可能成为分离轴的轴线。对于一个矩形而言，其边界上的法向量即可作为该矩形的分离轴。因此，我们需要计算出矩形A和矩形B的所有边界法向量，共计8条。具体计算方法如下：

矩形A的边界法向量：
- AB1: (y2 - y1, -(x2 - x1))
- A1A4: (-(y2 - y1), x2 - x1)
- A4A3: (y2 - y1, -(x2 - x1))
- A3A2: (-(y2 - y1), x2 - x1)

矩形B的边界法向量：
- B1B2: (y4 - y3, -(x4 - x3))
- B2B3: (-(y4 - y3), x4 - x3)
- B3B4: (y4 - y3, -(x4 - x3))
- B4B1: (-(y4 - y3), x4 - x3)

然后，我们需要将矩形A和矩形B分别投影到每个分离轴上，并计算它们在该轴上的投影重叠程度。如果存在任意一条分离轴上二者的投影不重叠，则二者一定不相交。具体计算方法如下：

对于一条分离轴(axis_x, axis_y)，矩形A在该轴上的投影长度为：

projA = (axis_x * x1 + axis_y * y1, axis_x * x2 + axis_y * y2, axis_x * x3 + axis_y * y3, axis_x * x4 + axis_y * y4)

即将矩形A的四个顶点坐标(x, y)带入分离轴的方程(ax + by = c)中，得到该点在该轴上的投影长度。

同理，矩形B在该轴上的投影长度为：

projB = (axis_x * x3 + axis_y * y3, axis_x * x4 + axis_y * y4, axis_x * x1 + axis_y * y1, axis_x * x2 + axis_y * y2)

接下来，我们需要判断投影重叠程度。如果二者在该轴上的投影重叠，则它们在该轴上没有分离。否则，它们在该轴上分离。判断投影重叠程度的方法如下：

maxA = max(projA)
minA = min(projA)
maxB = max(projB)
minB = min(projB)

如果maxA < minB 或者 maxB < minA，则二者在该轴上分离。

最后，我们需要判断所有可能的分离轴上二者是否都有重叠。如果所有分离轴上二者都有重叠，则它们相交；否则，它们不相交。具体实现如下：

def check_collision(A, B):
for axis_x, axis_y in A.edges + B.edges:
projA = [axis_x * x + axis_y * y for x, y in A.vertices]
projB = [axis_x * x + axis_y * y for x, y in B.vertices]
maxA, minA = max(projA), min(projA)
maxB, minB = max(projB), min(projB)
if maxA < minB or maxB < minA:
return False
return True

其中，A.edges和B.edges分别为矩形A和矩形B的所有边界法向量，A.vertices和B.vertices分别为矩形A和矩形B的所有顶点坐标。

以上就是一个基于SAT算法的碰撞检测示例。在实际开发中，我们可以将其应用于各种物体的碰撞检测，从而实现更加生动、丰富的游戏体验。