如何让SAT碰撞算法实现适配墙体碰撞检测？

我参考OneLoneCoder的教程实现了SFML游戏中的SAT碰撞算法，但该算法无法正确处理墙体碰撞器，碰撞修复逻辑存在问题，无法实现阻止玩家穿墙的效果。以下是我的实现代码：

碰撞修复函数 #

// 返回玩家（碰撞体为sf::ConvexShape a）需要移动的位移以解决碰撞
sf::Vector2f Collision::is_colliding_SAT_resolve(sf::ConvexShape& a, sf::ConvexShape& b, float dt)
{
    float overlap = std::min(find_min_overlap(a, b), find_min_overlap(b, a));
    if (overlap >= 0) {
        sf::Vector2f d = (b.getPosition() - a.getPosition());
        float s = sqrtf(d.x * d.x + d.y * d.y);
        if (s != 0)
            return { overlap * d.x * dt / s, overlap * d.y * dt / s };
    }
    return { 0,0 };
}

最小重叠量计算函数 #

float Collision::find_min_overlap(sf::ConvexShape& a, sf::ConvexShape& b)
{
    float overlap = std::numeric_limits<float>::max();
    std::vector<sf::Vector2f> va(a.getPointCount()), vb(b.getPointCount());

    for (int i = 0; i < va.size(); i++)
        va[i] = a.getTransform().transformPoint(a.getPoint(i));
    for (int i = 0; i < vb.size(); i++)
        vb[i] = b.getTransform().transformPoint(b.getPoint(i));

    // 遍历a的所有边的法向量
    for (int i = 0; i < va.size(); i++) {
        int j = (i + 1) % va.size();
        sf::Vector2f normal = { -(va[j].y - va[i].y), (va[j].x - va[i].x) };

        float max_overlap_a, min_overlap_a, max_overlap_b, min_overlap_b;
        max_overlap_a = max_overlap_b = std::numeric_limits<float>::min();
        min_overlap_a = min_overlap_b = std::numeric_limits<float>::max();

        // 将a的所有点投影到当前法向量
        for (int x = 0; x < va.size(); x++) {
            float q = dot_projection(va[x], normal);
            max_overlap_a = std::max(max_overlap_a, q);
            min_overlap_a = std::min(min_overlap_a, q);
        }

        // 将b的所有点投影到当前法向量
        for (int x = 0; x < vb.size(); x++) {
            float q = dot_projection(vb[x], normal);
            max_overlap_b = std::max(max_overlap_b, q);
            min_overlap_b = std::min(min_overlap_b, q);
        }

        overlap = std::min(overlap,
            (std::min(max_overlap_a, max_overlap_b) - std::max(min_overlap_a, min_overlap_b)));

        if (!(max_overlap_b >= min_overlap_a && max_overlap_a >= min_overlap_b))
            return -1;
    }
    return overlap;
}

辅助函数 #

float Collision::dot_projection(const sf::Vector2f& a, const sf::Vector2f& b)
{
    return (a.x * b.x + a.y * b.y);
}

float Collision::deg_to_rad(float angle)
{
    return angle * 3.141592 / 180.f;
}

问题根源与修复方案 #

1. 法向量未归一化
   计算的法向量没有进行归一化，导致投影值的尺度不一致，重叠量计算失真。需要对法向量进行单位化：

   // 归一化法向量
   float length = sqrtf(normal.x * normal.x + normal.y * normal.y);
   if (length != 0)
       normal /= length;
   

2. 位移方向错误
   当前用物体中心连线作为位移方向，正确的方向应该是产生最小重叠量的分离轴法向量。需要修改find_min_overlap，让它同时返回重叠量和对应的法向量：

   // 修改返回值为pair，存储重叠量和法向量
   std::pair<float, sf::Vector2f> Collision::find_min_overlap(sf::ConvexShape& a, sf::ConvexShape& b)
   {
       float min_overlap = std::numeric_limits<float>::max();
       sf::Vector2f best_axis;
       std::vector<sf::Vector2f> va(a.getPointCount()), vb(b.getPointCount());
   
       for (int i = 0; i < va.size(); i++)
           va[i] = a.getTransform().transformPoint(a.getPoint(i));
       for (int i = 0; i < vb.size(); i++)
           vb[i] = b.getTransform().transformPoint(b.getPoint(i));
   
       for (int i = 0; i < va.size(); i++) {
           int j = (i + 1) % va.size();
           sf::Vector2f normal = { -(va[j].y - va[i].y), (va[j].x - va[i].x) };
           // 归一化法向量
           float length = sqrtf(normal.x * normal.x + normal.y * normal.y);
           if (length != 0)
               normal /= length;
   
           float max_overlap_a, min_overlap_a, max_overlap_b, min_overlap_b;
           max_overlap_a = max_overlap_b = std::numeric_limits<float>::min();
           min_overlap_a = min_overlap_b = std::numeric_limits<float>::max();
   
           for (int x = 0; x < va.size(); x++) {
               float q = dot_projection(va[x], normal);
               max_overlap_a = std::max(max_overlap_a, q);
               min_overlap_a = std::min(min_overlap_a, q);
           }
   
           for (int x = 0; x < vb.size(); x++) {
               float q = dot_projection(vb[x], normal);
               max_overlap_b = std::max(max_overlap_b, q);
               min_overlap_b = std::min(min_overlap_b, q);
           }
   
           if (!(max_overlap_b >= min_overlap_a && max_overlap_a >= min_overlap_b))
               return { -1, {} };
   
           float current_overlap = std::min(max_overlap_a, max_overlap_b) - std::max(min_overlap_a, min_overlap_b);
           if (current_overlap < min_overlap) {
               min_overlap = current_overlap;
               best_axis = normal;
           }
       }
       return { min_overlap, best_axis };
   }
   

3. 修复位移的计算逻辑错误
   不需要将重叠量乘以dt，dt应该用于玩家的移动更新，碰撞修复直接应用完整的修正位移。同时要根据物体位置关系调整法向量的方向，确保玩家被推离墙体：

   sf::Vector2f Collision::is_colliding_SAT_resolve(sf::ConvexShape& player, sf::ConvexShape& wall)
   {
       auto [overlapA, axisA] = find_min_overlap(player, wall);
       auto [overlapB, axisB] = find_min_overlap(wall, player);
   
       float min_overlap = std::min(overlapA, overlapB);
       sf::Vector2f best_axis = (overlapA < overlapB) ? axisA : axisB;
   
       if (min_overlap >= 0) {
           // 计算玩家到墙体的方向，确保轴方向正确（推离墙体）
           sf::Vector2f to_wall = wall.getPosition() - player.getPosition();
           if (dot_projection(to_wall, best_axis) < 0)
               best_axis = -best_axis;
           // 返回修正位移
           return best_axis * min_overlap;
       }
       return { 0, 0 };
   }
   

4. 静态墙体的处理
   墙体作为静态物体，碰撞修复时只需要移动玩家，不需要对墙体做任何位移调整，确保修正量完全作用在玩家身上。

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