[Godot] 通过AABB包围盒和射线法检测碰撞

前言最近需要做鼠标选择单位的功能所以给大家分享一下我是如何实现的简单来说是在鼠标点击后通过我写的获取单位点集的方法先通过AABB包围盒进行粗筛然后再通过射线法进行精确判定最后根据Y轴的大小得到选中的单位下面我给大家分享一下我的实现逻辑效果展示代码实现鼠标点击这里本来没有什么好说的但是给大家分享一个普遍可能会遇到的问题就是鼠标点击UI因为比如我直接用的Input.IsActionJustPressed()方法做点击这回导致当我们点击UI的时候也会去做点击单位解决办法如下://当点击UI时直接返回if(gameManager.GetViewport().GuiGetHoveredControl()!null){return;}这样我们只需要注意把不会遮挡的UI比如占满全屏的Control节点的的Mouse-Filter设置为Ignore就好AABB包围盒介绍AABB(Axis-Aligned Bounding Box)的全称是轴对齐包围盒。简单来说,就是找一个最小的矩形,能把你的多边形完全框住,我们先用他进行粗筛否则如果每次都要对所有单位做精确的多边形判定,CPU会直接原地爆炸包围盒计算首先注意我们要提前设置好单位的点集因为之后的射线法判断所以需要按顺序设置这里我用的是List存的点集用Rect2存的AABB包围盒接下来我们需要计算包围盒注意计算好的包围盒需要跟着单位作为常量publicRect2CalulateAABB(ListpointSet){floatminXpointSet[0].X;floatmaxXpointSet[0].X;floatminYpointSet[0].Y;floatmaxYpointSet[0].Y;for(inti0;ipointSet.Count;i){Vector2ppointSet[i];if(p.XminX)minXp.X;elseif(p.XmaxX)maxXp.X;if(p.YminY)minYp.Y;elseif(p.YmaxY)maxYp.Y;}returnnewRect2(newVector2(minX,minY),newVector2(maxX-minX,maxY-minY));}这里的逻辑就是:不断更新四个边界值,最后用左下角坐标和宽高构造出矩形因为我们是用的Rect2所以注意用的两个点分别是position和size使用AABB进行粗筛// 先通过AABB包围盒粗筛foreach(varunitinunitPointSet){if(unit.AABB.HasPoint(mousePos-unit.nowPos)){// 通过射线法判断是否在多边形内if(IsPointInPolygon(mousePos-unit.nowPos,unit.pointSet))tmpUnit.Add(unit);}}这里有个细节:mousePos - unit.nowPos是把鼠标坐标转换到单位的局部坐标系。因为我们存储的点集都是相对于单位中心(0,0)的,所以需要先做这个转换射线法精确判定通过了AABB粗筛之后,就要进入真正的重头戏了:判断点是否在多边形内部射线法的核心思想想象你站在某个位置,往右边射出一根无限长的射线。这根射线会和多边形的边界相交。如果交点数量是奇数,说明你在多边形内部;如果是偶数(包括0),说明你在外部我们可以把它想象成翻墙的过程:你在外面,翻过1道墙,就进去了(奇数)再翻1道墙,就出来了(偶数)再翻1道墙,又进去了(奇数)所以,统计撞击次数的奇偶性,就能判断最终位置是在内还是外代码实现//射线法连接点(顺序)判断碰撞为奇数在多边形内privateboolIsPointInPolygon(Vector2mouse,ListpointSet){boolinsidefalse;for(inti0,jpointSet.Count-1;ipointSet.Count;ji){if((pointSet[i].Ymouse.Y)!(pointSet[j].Ymouse.Y)mouse.X(pointSet[j].X-pointSet[i].X)*(mouse.Y-pointSet[i].Y)/(pointSet[j].Y-pointSet[i].Y)pointSet[i].X)inside!inside;}returninside;}这段代码非常精简,接下来我给大家拆开讲解一下1) 双指针首先看循环头部:for (int i 0, j pointSet.Count - 1; i pointSet.Count; j i)这里为什么要用两个指针,而不是直接用(i 1) % pointSet.Count?原因如下:性能考虑: 模除运算在底层涉及除法,比简单的赋值和自增要慢。在需要对成百上千个单位进行实时判定的游戏中,这种细微差别会累积成可观的性能开销逻辑清晰:j i这种指针尾随的写法是图形学算法的标准写法,一开始就处理封口边,循环体内部非常纯净2) 坐标计算高度判断(pointSet[i].Ymouse.Y)!(pointSet[j].Ymouse.Y)这一行是在判断:这条边的两个端点,一个在鼠标上方,一个在鼠标下方如果两个点都在鼠标上方,或者都在下方,那这条边根本不会和水平射线相交,直接跳过就行计算交点X坐标这是整个算法最核心的数学部分:mouse.X(pointSet[j].X-pointSet[i].X)*(mouse.Y-pointSet[i].Y)/(pointSet[j].Y-pointSet[i].Y)pointSet[i].X我们把它看作**“相似三角形”或者“线性插值比例”**就很容易理解了 先算垂直进度比例(mouse.Y - p1.Y) / (p2.Y - p1.Y)。这就是算出当前鼠标的高度占这条线段总高度的百分之几 。应用到水平方向因为点在同一条斜线上你垂直方向爬了 50%水平方向也一定移动了总宽度的 50% 。所以用线段总宽度 (p2.X - p1.X) 乘以这个比例算出 X 轴上的偏移量。坐标还原最后加上起点的 p1.X就是地图上的真实绝对坐标了 。对应的数学公式表现为hitXΔX×mouseOffsetΔYXstarthitX \Delta X \times \frac{\text{mouseOffset}}{\Delta Y} X_{\text{start}}hitXΔX×ΔYmouseOffset​Xstart​完整判断代码//注意我这里返回的是我单位的唯一Id-1就是空大家根据自己的需要修改publiclongCalculateChooseUnit(Vector2mousePos,List(longid,ListVector2pointSet,Rect2 AABB,Vector2 nowPos)unitPointSet){List(pointSet,Rect2 AABB,Vector2 nowPos)tmpUnitnew();// 先通过AABB包围盒粗筛foreach(varunitinunitPointSet){if(unit.AABB.HasPoint(mousePos-unit.nowPos)){// 通过射线法判断是否在多边形内if(IsPointInPolygon(mousePos-unit.nowPos,unit.pointSet))tmpUnit.Add(unit);}}if(tmpUnit.Count0)return(-1);// 如果有多个单位重叠,选择Y坐标最大的(最下面的)varmaxYtmpUnit[0];for(inti1;itmpUnit.Count;i){if(tmpUnit[i].nowPos.YmaxY.nowPos.Y)maxYtmpUnit[i];}return(maxY.id);}结尾以上就是我实现鼠标选择检测碰撞的思路。AABB粗筛保证性能,射线法保证准确性,两者结合能处理各种复杂形状感谢大家观看