2D游戏中常见的碰撞检测算法思路(附详细思路及部分源码)

目录¹

1. 点与点的碰撞
2. 点与直线
3. 点与圆的碰撞
4. 点与矩形的碰撞
5. 点与多边形的碰撞
6. 点与地图格子的碰撞
7. 直线与直线的碰撞
8. 直线与圆的碰撞
9. 直线与矩形多边形的碰撞
10. 圆与圆的碰撞
11. 圆与矩形多边形的碰撞
12. 圆矩形与地图格子的碰撞
13. 矩形与矩形多边形的碰撞
14. 多边形与多边形的碰撞

点与点的碰撞

通过比较两个点坐标是否相同判断

function M.pointPoint(point1, point2)
local ret = false
if (point1.x == point2.x) and (point1.y == point2.y) then
ret = true
end
return ret
end


点与直线

直线：一般不做判断（可以根据直线公式判断）

线段：

• 先根据线段的直线公式判断点是否在线段所处的直线上
• 如果处于直线上，在判断该点是否处于线段所在的区间内

也可以使用叉积

点与圆的碰撞

通过计算点到圆心的距离与半径比较判断

function M.pointInCircle(point, circle)
local center = circle.center
local radius = circle.radius
return cc.pGetDistance(point, center) <= radius
end


cc.pGetDistance² source code:

function cc.pGetDistance(startP,endP)
return cc.pGetLength(cc.pSub(startP,endP))
end
function cc.pGetLength(pt)
return math.sqrt( pt.x * pt.x + pt.y * pt.y )
end
function cc.pSub(pt1,pt2)
return {x = pt1.x - pt2.x , y = pt1.y - pt2.y }
end


点与矩形的碰撞

通过判断点坐标是否在矩形四个顶点围成的坐标区域内

function M.pointInRect(point, rect)
return cc.rectContainsPoint(rect, point)
end


cc.rectContainsPoint³ source code:

function cc.rectContainsPoint( rect, point )
local ret = false
if (point.x >= rect.x) and (point.x <= rect.x + rect.width) and
(point.y >= rect.y) and (point.y <= rect.y + rect.height) then
ret = true
end
return ret
end


点与多边形的碰撞

对于任意多边形，可以运用引射线法：从目标点出发引一条射线，红点是要计算的点，通过该点引一条水平线，计算多边形各边与该水平线的交点（蓝点），如果红点两侧的射线与多边形各边的交点数都是奇数，那么红点在多边形内，反之不在。

处理特殊情况：

详细方法可参考下列贴子：

点是否在多边形内

点是否在多边形内GIS

点与地图格子的碰撞

主要是根据获取的地图格子的属性是否是碰撞格来判断，例如该格子是只可碰撞格子，碰撞可移动格子等。

直线与直线的碰撞

直线相交

直线与圆的碰撞

判断圆心到直线的距离与半径的大小即可

直线与矩形多边形的碰撞

取矩形多边形的边与直线判断相交，参考直线与直线的碰撞

线段与矩形：

function M.isLineIntersectRectangle(linePointX1,
linePointY1,
linePointX2,
linePointY2,
rectangleLeftTopX,
rectangleLeftTopY,
rectangleRightBottomX,
rectangleRightBottomY)
local lineHeight = linePointY1 - linePointY2
local lineWidth = linePointX2 - linePointX1 -- 计算叉乘
local c = linePointX1 * linePointY2 - linePointX2 * linePointY1
if (lineHeight * rectangleLeftTopX + lineWidth * rectangleLeftTopY + c >= 0 and lineHeight * rectangleRightBottomX + lineWidth * rectangleRightBottomY + c <= 0)
or (lineHeight * rectangleLeftTopX + lineWidth * rectangleLeftTopY + c <= 0 and lineHeight * rectangleRightBottomX + lineWidth * rectangleRightBottomY + c >= 0)
or (lineHeight * rectangleLeftTopX + lineWidth * rectangleRightBottomY + c >= 0 and lineHeight * rectangleRightBottomX + lineWidth * rectangleLeftTopY + c <= 0)
or (lineHeight * rectangleLeftTopX + lineWidth * rectangleRightBottomY + c <= 0 and lineHeight * rectangleRightBottomX + lineWidth * rectangleLeftTopY + c >= 0) then
if rectangleLeftTopX > rectangleRightBottomX then
local temp = rectangleLeftTopX
rectangleLeftTopX = rectangleRightBottomX
rectangleRightBottomX = temp
end
if rectangleLeftTopY local temp1 = rectangleLeftTopY
rectangleLeftTopY = rectangleRightBottomY
rectangleRightBottomY = temp1
end
if (linePointX1 or (linePointX1 > rectangleRightBottomX and linePointX2 > rectangleRightBottomX)
or (linePointY1 > rectangleLeftTopY and linePointY2 > rectangleLeftTopY)
or (linePointY1 return false
else
return true
end
else
return false
end
end


圆与圆的碰撞

如果两圆的圆心距小于或等于两圆半径和则认为发生碰撞

function M.circleIntersectsCircle(circle1, circle2)
return cc.pGetDistance(circle1.center, circle2.center) <= (circle1.radius + circle2.radius)
end


圆与矩形多边形的碰撞

圆与矩形的碰撞：

function M.rectIntersectsCircle(rect, circle)
local lx = cc.rectGetMidX(rect)
local ly = cc.rectGetMinY(rect)
local rx = cc.rectGetMaxX(rect)
local ry = cc.rectGetMaxY(rect)
local ret = false
local center = circle.center
local radius = circle.radius
if (center.x >= lx - radius) and (center.x <= rx + radius) and (center.y >= ly) and (center.y <= ry) then
ret = true
elseif (center.x >= lx) and (center.x <= rx) and (center.y >= ly - radius) and (center.y <= ry + radius) then
ret = true
else
local d1 = cc.pGetDistance(cc.p(lx, ly), center)
local d2 = cc.pGetDistance(cc.p(lx, ry), center)
local d3 = cc.pGetDistance(cc.p(rx, ly), center)
local d4 = cc.pGetDistance(cc.p(rx, ry), center)
if d1 <= radius or d2 <= radius or d3 <= radius or d4 <= radius then
ret = true
end
end
return ret
end


简单碰撞检测

对于凸多边形，分离轴定理：若两个物体没有发生碰撞，则总会存在一条直线，能将两个物体分离 。于是，我们把这条能够隔开两个物体的线称为分离轴。取两个多边形各个顶点在各条边上的对应投影之间是否都有交集，都有则说明发生碰撞

• 从需要检测的多边形中取出一条边，并找出它的法向量（垂直于它的向量），这个向量将会是我们的一个“投影轴”。

• 循环获取第一个多边形的每个点，并将它们投影到这个轴上。（记录这个多边形投影到轴上的最高和最低点）

• 对第二个多边形做同样的处理。

• 分别得到这两个多边形的投影，并检测这两段投影是否重叠

如果你发现了这两个投影到轴上的“阴影”有间隙，那么这两个图形一定没有相交。但如果没有间隙，那么它们则可能接触，你需要继续检测直到把两个多边形的每条边都检测完。如果你检测完每条边后，都没有发现任何间隙，那么它们是相互碰撞的。

如果你记录了哪个轴上的投影重叠值最小（以及重叠了多少），那么你就能用这个值来分开这两个图形

如果是圆的话，圆是没有任何的边，所以是没有明显的用于投影的轴。但它有一条“不是很明显的”的投影轴。这条轴就是途经圆心和多边形上离圆心最近的顶点的直线。

把圆投影到轴上，那你只用简单地把圆心投影上去，然后加上和减去半径就能得到投影长度

详细可参考凸多边形的碰撞检测

圆矩形与地图格子的碰撞

点取样法：可以按照地图格子对圆和矩形的包围盒进行点取样，转换成点的集合与地图格子的碰撞，然后参考点与地图格子的碰撞

矩形与矩形多边形的碰撞

矩形与矩形的碰撞可以对其四个顶点比较

function M.rectIntersectsRect(rect1, rect2)
return cc.rectIntersectsRect(rect1, rect2)
end
function cc.rectIntersectsRect( rect1, rect2 )
local intersect = not ( rect1.x > rect2.x + rect2.width or
rect1.x + rect1.width rect1.y > rect2.y + rect2.height or
rect1.y + rect1.height return intersect
end


也可以用分离轴算法可参考圆与矩形多边形的碰撞

多边形与多边形的碰撞

参考圆与矩形多边形的碰撞