基于Separating Axis Theorem的C语言2D等距游戏碰撞检测问题

问题背景 #

我自学C语言，正在学C++，用Allegro5开发一款2D等距视角游戏。已经实现玩家移动和非旋转正方形的碰撞检测，现在要做**玩家（移动平行四边形）与静止房屋（平行四边形）**的碰撞检测，采用分离轴定理（SAT）。当前调用fresh(house.vertices_x, house.vertices_y, player.vertices_x, player.vertices_y, 5);传入顶点（玩家顶点已叠加位置信息）。

当前实现流程 #

1. 将Allegro左上角坐标系转换为笛卡尔坐标系（翻转Y轴）
2. 从顶点数组生成图形的边向量
3. 计算每条边的垂直法线
4. 归一化法线向量
5. 将两个图形的所有顶点投影到每条法线上
6. 提取每个投影的最大/最小值
7. 比较投影极值，判断是否存在分离轴（无碰撞）或所有轴都重叠（有碰撞）

遇到的问题 #

碰撞检测结果不准确：本该触发碰撞的场景，仅在部分分离轴上能正确识别。已经用图形计算器验证了点积和归一化步骤的正确性，但仍找不到问题根源。

问题排查建议 #

1. 检查分离轴的完整性与正确性 #

• 平行四边形是对边平行的凸多边形，每个图形只需要测试2条独特的边法线（对边的法线方向相同或相反，不影响重叠判断），因此总共需要测试4条分离轴，而非8条。如果代码测试了8条轴（重复测试平行边的法线），虽逻辑没问题但可能引入误差；如果漏测了某一方的边法线，会直接导致碰撞判断错误。
• 验证法线是否与对应边向量垂直：边向量(dx, dy)的法线应为(-dy, dx)或(dy, -dx)，两者与原边向量的点积必须为0，可在代码中添加日志或断言验证这一点。

2. 确认坐标系转换的一致性 #

• 确保房屋和玩家的所有顶点都完成了Y轴翻转转换，不能只转换其中一方。如果房屋顶点仍使用Allegro坐标系，会导致两个图形不在同一坐标系下计算，投影结果完全错误。
• 检查转换公式是否正确：Allegro坐标系原点在左上角，Y轴向下；笛卡尔坐标系Y轴向上，转换公式应为y = 屏幕高度 - y，确认使用的屏幕高度值正确。

3. 检查顶点顺序与数量 #

• SAT要求多边形顶点按顺时针或逆时针顺序连续排列，如果顶点数组乱序，生成的边向量会出错，进而导致法线错误。
• 注意调用fresh时传入的最后一个参数是5，但平行四边形只有4个顶点。如果这个参数是顶点数量，会导致数组越界，读取错误内存数据，这大概率是碰撞检测异常的核心原因。

4. 投影极值计算与重叠判断的精度问题 #

• 初始化投影极值时，必须将min和max设为第一个顶点的投影值，不能设为0或其他默认值（比如所有投影为负数时，初始max=0会导致极值计算错误）。
• 浮点数比较时加入**epsilon（极小值，如1e-6）**避免精度误差：判断不重叠的条件应改为A.max + 1e-6 < B.min || B.max + 1e-6 < A.min，否则可能因为浮点精度问题，把本该重叠的投影判断为分离。

5. 归一化步骤的必要性 #

SAT的投影比较不需要归一化法线——归一化只是缩放投影值的大小，不改变极值的相对位置。去掉归一化步骤，不仅能减少计算量，还能避免归一化时除以接近0的数导致的精度问题，可以直接用未归一化的法线向量做投影计算。

简化实现思路 #

1. 利用平行四边形特性减少计算 #

平行四边形可以用中心坐标+两个边向量来表示，不需要存储4个顶点。比如玩家的平行四边形只需记录中心(x,y)、边向量u和v，四个顶点可通过(x±u.x±v.x, y±u.y±v.y)快速计算（根据坐标系调整符号）。这种方式能避免顶点数组的维护错误，边向量直接复用预设值，无需从顶点生成。

2. 复用Allegro内置数学工具 #

Allegro5提供了现成的向量运算函数（如al_fdot计算点积、al_fsub计算向量差），用这些函数代替手写的向量计算，能减少手动编码的错误。

3. 提前预计算静态图形的法线 #

房屋是静止的，其边法线只需预计算一次，不需要每次碰撞检测都重新计算，能提升性能。

内容的提问来源于stack exchange，提问作者Peter Robertson