使用lua实现各种算法，先从分离轴定理开始

萧山财神

接下来我们可以实现一种在2D游戏中常用的物理引擎算法：分离轴定理（Separating Axis Theorem, SAT）。SAT用于检测凸多边形之间的碰撞，是一种高效且准确的碰撞检测算法。

以下是用 Lua 实现的分离轴定理（SAT）碰撞检测算法：

-- 向量点积
function dotProduct(v1, v2)
    return v1.x * v2.x + v1.y * v2.y
end

-- 向量减法
function vectorSubtract(v1, v2)
    return {x = v1.x - v2.x, y = v1.y - v2.y}
end

-- 向量法线
function normalVector(v)
    return {x = -v.y, y = v.x}
end

-- 投影点到轴
function projectPolygon(axis, polygon)
    local min = dotProduct(axis, polygon[1])
    local max = min

    for i = 2, #polygon do
        local projection = dotProduct(axis, polygon[i])
        if projection < min then
            min = projection
        elseif projection > max then
            max = projection
        end
    end

    return min, max
end

-- 检查投影是否重叠
function isOverlapping(minA, maxA, minB, maxB)
    return maxA >= minB and maxB >= minA
end

-- 分离轴定理碰撞检测
function checkCollisionSAT(polygonA, polygonB)
    local polygons = {polygonA, polygonB}

    for _, polygon in ipairs(polygons) do
        for i = 1, #polygon do
            local nextIndex = (i % #polygon) + 1
            local edge = vectorSubtract(polygon[nextIndex], polygon[i])
            local axis = normalVector(edge)

            local minA, maxA = projectPolygon(axis, polygonA)
            local minB, maxB = projectPolygon(axis, polygonB)

            if not isOverlapping(minA, maxA, minB, maxB) then
                return false
            end
        end
    end

    return true
end

-- 测试分离轴定理碰撞检测
local polygonA = {
    {x = 0, y = 0},
    {x = 50, y = 0},
    {x = 50, y = 50},
    {x = 0, y = 50}
}

local polygonB = {
    {x = 25, y = 25},
    {x = 75, y = 25},
    {x = 75, y = 75},
    {x = 25, y = 75}
}

local polygonC = {
    {x = 100, y = 100},
    {x = 150, y = 100},
    {x = 150, y = 150},
    {x = 100, y = 150}
}

if checkCollisionSAT(polygonA, polygonB) then
    print("polygonA 和 polygonB 发生碰撞")
else
    print("polygonA 和 polygonB 没有发生碰撞")
end

if checkCollisionSAT(polygonA, polygonC) then
    print("polygonA 和 polygonC 发生碰撞")
else
    print("polygonA 和 polygonC 没有发生碰撞")
end

在这个实现中：

1. dotProduct 函数计算两个向量的点积。
2. vectorSubtract 函数计算两个向量的差。
3. normalVector 函数计算一个向量的法线（垂直向量）。
4. projectPolygon 函数将多边形的顶点投影到一个轴上，返回投影的最小值和最大值。
5. isOverlapping 函数检查两个投影是否重叠。
6. checkCollisionSAT 函数实现分离轴定理碰撞检测，接受两个多边形 polygonA 和 polygonB，返回它们是否发生碰撞。
7. 测试代码定义了三个多边形，并调用 checkCollisionSAT 函数来检测它们之间的碰撞情况。

分离轴定理的基本思想是，如果两个凸多边形在某个轴上的投影不重叠，则它们不发生碰撞。通过检查所有边的法线作为分离轴，可以确定两个多边形是否发生碰撞。

SAT碰撞检测适用于许多2D游戏场景，如复杂形状的角色与障碍物的碰撞、物理模拟中的多边形碰撞等。它比简单的AABB碰撞检测更为精确，适合处理复杂的几何形状。