Skip to content

Instantly share code, notes, and snippets.

@yangfch3
Last active November 21, 2023 02:17
Show Gist options
  • Save yangfch3/0ca473b60d022689189d5ae5149b6235 to your computer and use it in GitHub Desktop.
Save yangfch3/0ca473b60d022689189d5ae5149b6235 to your computer and use it in GitHub Desktop.
2D SAT 碰撞的 Lua 实现
--- 两张牌的重叠检测,使用 SAT
function GamePlayUtils.OverlapCheckUseCardData(cb, ct)
local dtX = CellCardDef.Width / 2
local dtY = CellCardDef.Height / 2
local polygonCb = SAT.Polygon("polygonCb", {0, 0}, {{dtX, dtY}, {-dtX, dtY}, {-dtX, -dtY}, {dtX, -dtY}}, 0)
SAT.SetPolygon(polygonCb, cb.posX, -cb.posY, -cb.rotation)
local polygonCt = SAT.Polygon("polygonCt", {0, 0}, {{dtX, dtY}, {-dtX, dtY}, {-dtX, -dtY}, {dtX, -dtY}}, 0)
SAT.SetPolygon(polygonCt, ct.posX, -ct.posY, -ct.rotation)
return SAT.DetectPolygonAndPolygon(polygonCb, polygonCt)
end
local MathUtil = {}
---获取两点的距离
function MathUtil.GetDis(vec1, vec2)
local x1 = vec1.x or vec1[1]
local y1 = vec1.y or vec1[2]
local x2 = vec2.x or vec2[1]
local y2 = vec2.y or vec2[2]
local disX = x1 - x2
local disY = y1 - y2
local dis = math.sqrt(disX * disX + disY * disY)
return dis
end
---向量归一化
function MathUtil.Normalize(vec)
local x = vec[1] or vec.x
local y = vec[2] or vec.y
local mag = math.sqrt(x * x + y * y)
if type(vec) == "table" then
vec[1] = x / mag
vec[2] = y / mag
end
vec.x = x / mag
vec.y = y / mag
end
---点乘
function MathUtil.Dot(vec1, vec2)
local x1 = vec1.x or vec1[1]
local y1 = vec1.y or vec1[2]
local x2 = vec2.x or vec2[1]
local y2 = vec2.y or vec2[2]
return x1 * x2 + y1 * y2
end
---精确到小数点后n位
---num 浮点数
---n 浮点数精确位数
function MathUtil.FloatAccurateN(num, n)
if type(num) ~= "number" then
return num;
end
n = n or 0;
n = math.floor(n)
if n < 0 then
n = 0;
end
local nDecimal = 10 ^ n
local nTemp = math.floor(num * nDecimal);
local nRet = nTemp / nDecimal;
return nRet;
end
---二维向量的向量积
---大小的绝对值表示两个向量构成的三角形的面积的2倍
---正负表示与两个向量构成的平面的法线的方向
function MathUtil.VectorProduct(vec1, vec2)
local vec1X = vec1.x or vec1[1]
local vec1Y = vec1.y or vec1[2]
local vec2X = vec2.x or vec2[1]
local vec2Y = vec2.y or vec2[2]
return vec1X * vec2Y - vec2X * vec1Y
end
function MathUtil.Add(pt1, pt2)
return { x = pt1.x + pt2.x, y = pt1.y + pt2.y }
end
function MathUtil.Sub(pt1, pt2)
return { x = pt1.x - pt2.x, y = pt1.y - pt2.y }
end
-- 计算圆周上的点位置
function MathUtil.CalCirclePos(centerPos, radius, angleRadians)
return MathUtil.Add(centerPos, { x = math.cos(angleRadians) * radius, y = math.sin(angleRadians) * radius }), MathUtil.Sub(centerPos, { x = math.cos(angleRadians) * radius, y = math.sin(angleRadians) * radius })
end
--[[
--- SAT 开始 ---
--]]
---将角度转换为逆时针角度
---rotation (0 ~ 180逆时针,0 ~ -180顺时针)
local function ChangeRotationToInverse(rotation)
rotation = rotation or 0
if rotation < 0 then
rotation = rotation + 360
end
return rotation or 0
end
---多边形的边
---vertex1
---vertex2
local function CreateSegment(vertex1, vertex2)
local segment = { pointA = vertex1, pointB = vertex2, dir = { vertex2.x - vertex1.x, vertex2.y - vertex1.y } }
return segment
end
--- 创建一个多边形
--- name:多边形名字
--- offset:实际点与多边形的偏移量,offset为多边形的原点,多边形的顶点位置都是相对于这个点的偏移量
--- vertices : 多边形的顶点数组,位置相对于offset
--- rotation : 旋转角度(角度不是弧度(0~180为逆时针,0~-180为顺时针)
local function Polygon(name, offset, vertices, rotation)
local polygon = {}
polygon.name = name or "polygon"
polygon.offset = { offset.x or offset[1] or 0, offset.y or offset[2] or 0 }
-- 弧度
polygon.rotation = math.rad(ChangeRotationToInverse(rotation))
--- 模板顶点,相对于offset为原点的顶点数组
polygon._tempVertices = {}
for i, vertex in ipairs(vertices) do
local x = vertices[i][1]
local y = vertices[i][2]
table.insert(polygon._tempVertices, { x = x, y = y })
end
--顶点数组,实际顶点坐标
polygon._vertices = {}
-- 平面中,一个点(x,y)绕任意点(dx,dy)逆时针旋转a度后的坐标
-- xx= (x - dx)*cos(a) - (y - dy)*sin(a) + dx ;
-- yy= (x - dx)*sin(a) + (y - dy)*cos(a) +dy ;
for i, vertex in ipairs(vertices or {}) do
local x = (vertices[i][1] * math.cos(polygon.rotation)) - (vertices[i][2] * math.sin(polygon.rotation))
local y = (vertices[i][1] * math.sin(polygon.rotation)) + (vertices[i][2] * math.cos(polygon.rotation))
table.insert(polygon._vertices, { x = x, y = y })
end
---边
polygon._edges = {}
for i = 1, #polygon._vertices do
table.insert(polygon._edges, CreateSegment(polygon._vertices[i], polygon._vertices[1 + i % (#polygon._vertices)]))
end
polygon.centerPoint = { x = 0, y = 0 }
--- 注册点到中心点的距离
polygon._centerToAnchorDistance = MathUtil.GetDis({ 0, 0 }, polygon.offset)
--- 中心点相对于注册点的旋转弧度
polygon._centerToAnchorRadian = math.atan(polygon.offset[2], polygon.offset[1])
return polygon
end
---设置多边形的实际位置,更新多边形的信息
---polygon 多边形
---x 碰撞体的实际位置X
---y 碰撞体的实际位置y
---rotation 是角度不是弧度
local function SetPolygon(polygon, x, y, rotation)
rotation = ChangeRotationToInverse(rotation) or 0
local r = math.rad(rotation)
polygon.rotation = r
---相对于世界坐标系旋转的弧度
local radian = polygon._centerToAnchorRadian + r
local dx = polygon._centerToAnchorDistance * math.cos(radian)
local dy = polygon._centerToAnchorDistance * math.sin(radian)
---中心点的世界坐标
polygon.centerPoint.x = x + dx
polygon.centerPoint.y = y + dy
---更新多边形顶点位置(相对于世界坐标的)
for i, vertex in ipairs(polygon._vertices) do
local _x = polygon._tempVertices[i].x
local _y = polygon._tempVertices[i].y
polygon._vertices[i].x = polygon.centerPoint.x + (_x * math.cos(polygon.rotation)) - (_y * math.sin(polygon.rotation))
polygon._vertices[i].y = polygon.centerPoint.y + (_x * math.sin(polygon.rotation)) + (_y * math.cos(polygon.rotation))
end
---更新边的信息
for i = 1, #polygon._vertices do
local pointA = polygon._vertices[i]
local pointB = polygon._vertices[1 + i % (#polygon._vertices)]
polygon._edges[i].pointA = pointA
polygon._edges[i].pointB = pointB
polygon._edges[i].dir[1] = pointB.x - pointA.x
polygon._edges[i].dir[2] = pointB.y - pointA.y
end
end
---计算多边形在轴上的投影
---polygon 多边形
---axis 投影的轴
---返回值为投影两端的最大值与最小值
local function GetProjectionWithAxis(polygon, axis)
MathUtil.Normalize(axis)
---在轴上面的投影
local min = MathUtil.Dot(polygon._vertices[1], axis)
local max = min
for i, v in ipairs(polygon._vertices) do
local projection = MathUtil.Dot(v, axis)
if projection < min then
min = projection
end
if projection > max then
max = projection
end
end
return MathUtil.FloatAccurateN(min, 3), MathUtil.FloatAccurateN(max, 3)
end
local function CheckIsProjectionContains(a, b)
local aMin = a[1]
local aMax = a[2]
local bMin = b[1]
local bMax = b[2]
if (aMax < aMin) then
aMin = aMax
aMax = a[1]
end
if (bMax < bMin) then
bMin = bMax
bMax = b[1]
end
return not (aMin > bMax or aMax < bMin)
end
---polygonA 多边形
---polygonB 多边形
---分离轴,以多边形的每条边的法向量为轴,将多边形投影到轴上,如有任意一个轴上的两个多边形的投影不相交,那么这两个多边形就是分离的
local function DetectPolygonAndPolygon(polygonA, polygonB)
local aProjection = {}
local bProjection = {}
local segmentNormal = {}
for i, segment in ipairs(polygonA._edges) do
---边的法线向量
segmentNormal[1] = segment.dir[2]
segmentNormal[2] = -segment.dir[1]
---两个多边形在当前轴上的投影
aProjection[1], aProjection[2] = GetProjectionWithAxis(polygonA, segmentNormal)
bProjection[1], bProjection[2] = GetProjectionWithAxis(polygonB, segmentNormal)
if not CheckIsProjectionContains(aProjection, bProjection) then
return false
end
end
for i, segment in ipairs(polygonB._edges) do
---边的法线向量
segmentNormal[1] = segment.dir[2]
segmentNormal[2] = -segment.dir[1]
---两个多边形在当前轴上的投影
aProjection[1], aProjection[2] = GetProjectionWithAxis(polygonA, segmentNormal)
bProjection[1], bProjection[2] = GetProjectionWithAxis(polygonB, segmentNormal)
if not CheckIsProjectionContains(aProjection, bProjection) then
return false
end
end
return true
end
---多边形与点的碰撞(判断一个点是在多边形内,还是在多边形上,还是在多边形外)
---polygon 多边形
---point 需要检测的点
---多边形可看做从某点出发的闭合回路,内部的点永远在回路的同一边。通过边与点的连线的向量积(叉积)的正负表示方向,
---顺时针方向,所有向量积数值均为负,逆时针方向,所有向量积数值均为正
local function DetectPolygonAndPoint(polygon, point)
local pointX = point.x or point[1]
local pointY = point.y or point[2]
local firstVectorProduct = 0
for i, edge in ipairs(polygon._edges) do
local vertex = edge.pointA
---边的第一个顶点point的向量
local vertex2point = { pointX - vertex.x, pointY - vertex.y }
---边与vertex2point的向量积
local vectorProduct = MathUtil.FloatAccurateN(MathUtil.VectorProduct(edge.dir, vertex2point), 3)
---点在多边形的边上
if vectorProduct == 0 then
return true
end
if i == 1 then
firstVectorProduct = vectorProduct
else
if firstVectorProduct * vectorProduct < 0 then
return false
end
end
end
return true
end
local function PrintPolygon(polygon)
print(polygon.name .. " offset ", polygon.offset[1], polygon.offset[2])
print(polygon.name .. " centerPoint ", polygon.centerPoint.x, polygon.centerPoint.y)
print(polygon.name .. "模板顶点信息:===========================================")
for index, value in ipairs(polygon._tempVertices) do
print(string.format("x = %f, y = %f", polygon._tempVertices[index].x, polygon._tempVertices[index].y))
end
print(polygon.name .. "模板顶点信息:===========================================")
print(polygon.name .. "实际顶点信息:===========================================")
for index, value in ipairs(polygon._vertices) do
print(string.format("x = %f, y = %f", polygon._vertices[index].x, polygon._vertices[index].y))
end
print(polygon.name .. "实际顶点信息:=======================================")
print(polygon.name .. "边信息:===========================================")
for index, value in ipairs(polygon._edges) do
print(string.format("dir = (%f,%f)", polygon._edges[index].dir[1], polygon._edges[index].dir[2]))
end
print(polygon.name .. "边信息:=======================================")
end
local function Circle(offset, radius)
local circle = {}
circle.radius = radius or 0
circle.offset = { x = offset.x and offset[1] or 0, y = offset.y and offset[2] or 0 }
circle.centerPoint = { x = 0, y = 0 }
return circle
end
local function CircleSet(circle, x, y, radius)
circle.centerPoint.x = x + circle.offset.x
circle.centerPoint.y = y + circle.offset.y
circle.radius = radius or circle.radius
end
---计算圆形在轴上的投影
---axis 投影的轴
---返回投影两端的最大值与最小值
local function GetCircleProjectionWithAxis(circle, axis)
MathUtil.Normalize(axis)
---线段的夹角
local rad = math.atan(axis.y, axis.x)
---经过圆心,线段与圆相交的两个点的位置
local pointInCircle1, pointInCircle2 = MathUtil.CalCirclePos(circle.centerPoint, circle.radius, rad)
---分别两个点在轴上的投影
local min = MathUtil.Dot(pointInCircle1, axis)
local max = min
local min2 = MathUtil.Dot(pointInCircle2, axis)
if min2 < min then
min = min2
end
if min2 > max then
max = min2
end
return MathUtil.FloatAccurateN(min, 3), MathUtil.FloatAccurateN(max, 3)
end
---polygon 多边形
---circle 圆形
---原理与多边形判断一样
local function DetectPolygonAndCircle(polygon, circle)
local aProjection = {}
local bProjection = {}
local circleCenter = circle.centerPoint
for i, segment in ipairs(polygon._edges) do
---多边形的边的法线向量
local axes = { segment.dir[2], -segment.dir[1] }
---多边形在当前轴上的投影
aProjection[1], aProjection[2] = GetProjectionWithAxis(polygon, axes)
---圆在当前轴上的投影
bProjection[1], bProjection[2] = GetCircleProjectionWithAxis(circle, axes)
if not CheckIsProjectionContains(aProjection, bProjection) then
return false
end
end
return true
end
--[[
local polygonA = Polygon("polygonA",{ 0, 0},{ { 0, 1}, { -1, 0}, { -1, -1}, { 1, -1}, { 1, 0}},0)
SetPolygon(polygonA,0,0,60)
local polygonB = Polygon("polygonB",{ 0, 0},{ { 0, 1}, { -1, 0}, { -1, -1}, { 1, -1}, { 1, 0}},0)
SetPolygon(polygonB,0,0,-30)
print("多边形A,B碰撞 : ", DetectPolygonAndPolygon(polygonA, polygonB))
--]]
--[[
local polygonA = Polygon("polygonA", { 1, 1 }, { { 0, 1 }, { -1, 0 }, { -1, -1 }, { 1, -1 }, { 1, 0 } }, 0)
SetPolygon(polygonA, 0, 0, -45)
local circleA = Circle({ 0, 0 }, 1)
CircleSet(circleA, 2, 0, 1)
print("多边形A与圆B碰撞 : ", DetectPolygonAndCircle(polygonA, circleA))
--]]
--[[
local polygonA = Polygon("polygonA", { 0, 0 }, { { 0, 1 }, { -1, 0 }, { -1, -1 }, { 1, -1 }, { 1, 0 } }, 0)
SetPolygon(polygonA, 0, 0, 30)
local pointB = { x = 0, y = 1 }
print("多边形A与点B碰撞 : ", DetectPolygonAndPoint(polygonA, pointB))
--]]
return {
Polygon = Polygon,
SetPolygon = SetPolygon,
Circle = Circle,
CircleSet = CircleSet,
DetectPolygonAndPolygon = DetectPolygonAndPolygon,
DetectPolygonAndPoint = DetectPolygonAndPoint,
DetectPolygonAndCircle = DetectPolygonAndCircle,
PrintPolygon = PrintPolygon
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment