Egret社区
本帖最后由 csujin 于 2015-11-13 13:14 编辑

洒家七步,又来了,嘿嘿~之前发过一个点与凸多边形检测的例子,不过只能用点碰,还只能与凸的多边形碰,想想实在太鸡肋了,所以这次重新写了一版,如标题所述,新版的基本能满足所有类型的碰撞检测了,包括点/线/圆/凸/凹多边形(但还不包括镂空和边有交叠的情况),支持凹多边形自动分解,而且也加入了四叉树来管理场景,希望能对大家有所帮助

老规矩,先上Demo(点选物体可以编辑形状及位置):

egret2.5-EUI版本(推荐):演示地址

egret2.0-GUI版本(不包括凹多边形部分阉割版,还有点bug没改,不过数量多时貌似效率比2.5版本高些。。还没找到原因,有几个地方是不太好的,在2.5里改了,不过。。。然并卵,这个版本就是帧率会高些。。。):演示地址


2015.11.16更新:
更新简单的2D光照演示(效率还有待优化,建议同场景不要超过一个)参考文档:http://www.redblobgames.com/articles/visibility/
微信截图_20151116214235.png

效果图:
各种形状的碰撞检测
微信截图_20151106170508.png
微信截图_20151106170721.png
四叉树分割管理
微信截图_20151106170809.png
拖动脚点会自动计算分割凹多边形
微信截图_20151106172241.png

演示中,边数为0就是圆形了,半径也为0就是点了,边数为2就是线段,大于3就是多边形,可以拖拽多边形顶点来改变形状。有一些细节还没来得及修改,见谅一下哈

这里还有一些之前发过的帖子,感兴趣的朋友可以顺手翻翻:
A*寻路算法-Egret代码分享及新思路讨论
分离轴多边形碰撞检测源码分享
简单的格子2D地图编辑器-源码分享
点与任意凸多边形碰撞检测源码分享

本贴目录:
1、分离轴怎么弄
2、怎么处理点,线,圆以及凹多变型
3、四叉树是什么鬼
4、实际代码中一些优化技巧5、简单的使用说明

第一部分:分离轴怎么弄
        碰撞检测是大家在做游戏过程中不可避免会遇到的问题,比如两个矩形的碰撞,这种就比较简单,只要比较两个轴上最小点与最大点是否交叠就行了。但是如果把其中一个矩形旋转一个角度呢,也许有的童鞋就要摇头想一想了。其实原理是一样的,都是把两个图形投影到某一条轴上,然后看这个轴上是否有交叠。(PS:这里说的轴并不是指坐标轴,而是投影轴,可以是360°任意角度的轴)

不过这里有一点需要注意,也是最关键的一点,就是即使真的发现某一条轴上有交叠,其实我们也并不能保证两个多边形就是相交的的。那怎么才能确定呢,嗯,你猜对了,就是要把所有轴全都尝试一遍才行,只有在所有轴上全都没有交叠的情况下,我们才能确定他们是相交的。但是反过来,我们还可以得到一条结论,就是只要有一条轴上没有交叠,那么我们就可以确定,他们是不相交的了。 微信截图_20151106151455.png
      如图所示,红色的线即为一条可以把他们分离开的分离轴所以呢现在问题就从检测碰撞转到了找到这条可以把他们分开分离轴。

      那么我们要怎么找到这条轴呢,真的要把360°全都试一遍么?当然不用,经研究发现,只要把每条边的法线都试验一遍就可以了。这样问题就大大滴简化了。我们需要做的就是用一点小小的向量知识,取到每条边的向量,然后计算出法线就可以了。当然,两个多边形,一般情况下是会有重复投影轴的,我们在取轴的时候需要规定一下正方向,比如30°的和270°的,我们就只取一条就可以了。
      最重要的一步完成了,我们就可以将两个多边形在投影轴上投影了,然后计算出每个多边形对应的最小点与最大点,就可以很容易的判断出是否碰撞了
       这里只说大概的原理,就不多讲了,感兴趣的朋友可以参考一下这篇文章http://www.metanetsoftware.com/technique/tutorialA.html,虽然是英文的,但是里面的例子做的很棒,可以非常清晰的看明白到底是怎么分离的,还有一个中文的http://blog.csdn.net/zc55803903/article/details/7837918,当然,也可以直接去看源码

第二部分:怎么处理点,线,圆以及凹多变型
      点其实就是半径为0的圆,那么圆要怎么处理呢。其实通过观察我们不难发现,我们根本不用去管圆形的分离轴,它就是个小受儿,你用啥它用啥就完全可以了。
微信截图_20151106153030.png
      如图所示,我们只需要比较这个四边形的两条投影轴上,圆与它是否相交就可以了。那么线段呢,线段还是有点骨气的,他有自己的投影轴,但也非常简单,只要算出多边形的投影轴后,把线段自己的投影轴也加进去就好了。

     下面我们来说一下凹多边形,这个就有一点点复杂了,因为用分离轴的方法,并不能搞定这个东东,为什么呢, 微信截图_20151106153526.png
      看个图就明白了,因为这货是可以用来插的!!(由于节操等原因,此图略去一组凹凸多边形二者的表情)。这可怎么破!没关系,对这种奇怪的形状粗暴点就粗暴点吧,直接宰了算了。可是怎么宰呢,这也就是算法中常说的分而治之的思想了。
微信截图_20151106154032.png
      如图所示,我们可以把这个图形强行拆成两个凸多边形。只要每个凸多边形都和另一个东西不相交,那么这个奇怪的东西整体上也一定不会相交了。

    于是,这就引出了另外一个问题,“凹多边形分解”。说起来要真要把这个奇怪的东西宰了也并不容易。洒家也颇费了些周折,现在主要有两种算法来解决这个问题。第一个方法很容易理解,因为解决凹多边形的问题,其实就是减少凹点(就是凹进去的点)的过程。 微信截图_20151106154746.png
      如图中绿色线所示,干掉他只需要三步:第一步,把凹多边形洗干净了,遍历顶点,第二步,如果发现是凹点,那么就把他的一条边延长,这样凹多边形就被一分为二了。第三步,重复前两步,直到再没有凹点存在了。
      这种方法虽然容易理解,但是实际分割出来的图形并不理想(理想情况有一些不同的标准,有的需要分割后的形状好看,有的需要分割成的多边形数量最少),所以便有了第二种情况
   第二个方法略微复杂,但原理大同小异,也是减少凹点。首先还是找到凹点,然后把凹点的两条边延长, 微信截图_20151106155226.png
      如图所示,这样就会把多边形分割为A/B/C/D四个区域。然后我们会遇到两种情况,D区域为空,D区域不为空。当D区域不为空的时候,我们会通过算法,选出D区域内一个合适的点来与凹点相连来分割。如过D区域为空,则在那条线段上通过算法来找一个点,与凹点相连。具体算法有点小复杂,这里只说大概的原理,就不多讲了,感兴趣的朋友可以参考一下这篇文章http://www.doc88.com/p-114690887292.html,也可以直接去看源码


三、四叉树是什么鬼
     现在我们有了对两个形状比较的方法,那么如果场景里有10个物体,我们要怎么判断某一个物体是否已经碰撞了呢。显然,我们要把这个物体和其他9个全都比较一遍才可以确认他没有被碰撞到。这样的话,我们就不得不做指数级的碰撞检测,随着场景内物体的增多,这是一件很可怕的事儿。那怎么办呢。
       微信截图_20151106160756.png      
      如图中所示,我们现在有A、B、C三个图形。其中A与B、C远的八竿子打不着,我们真的有必要还要去比较一遍么。是的,没必要!
      那么现在问题的关键就是,我们怎么来确定两个图形是处于八竿子打不着的位置呢?
      这时候就轮到四叉树上场了。其实你用二叉树八叉树神马的也能实现的,不过就是分的块数不同(当然,八叉树主要用于3D场景),这里只是以四叉树来说明问题。所谓四叉树,顾名思义,就是把屏幕分成四份,所谓一个萝卜一个坑,我们就是要把所有的形状,按照自己的位置,给她丢到应该在的区域内,然后做碰撞检测的时候,我们就只需要和自己框框内的形状比较就可以了,完全无视掉八竿子打不到的东西。细心的朋友会发现了,那么像图中
C这种,同时在两个框框内的怎么办呢。很简单,两个办法,第一,把他归到父对象框框里去,第二,两个框框全都把他算上就好了。我这里采用的是第二个办法,因为感觉这样更容易理解一点。


     那么我们应该按照什么样的规则来分块呢,又要分多少块呢,这就可以自己设定一个合适的阙值。比如我的示例中阙值=10;俗话说,世上本没有路,走得人多了,就有了。嗯,就是这个道理,屏幕最开始的时候是没有块的,或者说只有一个块(因为我准备做的就是多形状的场景,所以初始有四个块)。当这个区域内的形状数量大于10的时候,就把这个区域分成4个块,然后把其内的每个物体放到相应的子块中。当某个子块中的形状大于10以后,就把这个子块再拆分成4个子块,不断的重复(不过会设置一个层级上限)。这样在一般情况下,判断某个物体是否碰撞了,只需要检查自己格子里的形状就行了(一般会小于阙值)。这样,就大大减少了碰撞检测的开销。
     当然,故事听起来是美好的,但总会有“但是”。其实上面减少的开销,有一部分是转化到了分配每个形状所在四叉树节点去了,对于运动的物体,每一帧都要检查他的节点数据(不过可以针对具体项目做一些优化,不用每一帧都做,这里先不说了)。所以可以看出来,四叉树其实更适合于有大量静态物体的场景的。比如你的地图已经设计好了,大部分都不会动,然后小人是移动的,这样,只要每次检查一下小人的四叉树数据就可以了,而不用每个物体都检查。如过有一些动态物体的场景,可以把动态物体单独管理起来,也可以大幅度优化性能。
     PS:因为一般场景内物体都比较均匀,所以我并没有做成平衡四叉树。偷个小懒~。~
具体算法有点小复杂,这里只说大概的原理,就不多讲了,感兴趣的朋友可以参考一下这篇文章http://blog.csdn.net/zhouxuguang236/article/details/12312099,也可以直接去看源码(别打洒家哈。。。如果都展开写,实在是写不下,其实原理看懂了,具体算法就容易理解了~。~)


4、实际代码中一些优化技巧


        开始的时候,洒家传了两个2.0和2.5两个版本的演示地址,其实2.0的是开始写的,2.5出了以后,又改了一版,加了一些优化,不过。。。。不过。。。。悲剧的是,后面改的版本在数量多的时候貌似并没有2.0的版本帧率高。。。。。。。。还不知道是我改的问题还是2.5版本的问题。因为把碰撞检测关闭掉,也没有原来的版本帧率高。。。
        不过洒家还是硬着头皮说一下后边改动的地方吧。开始的时候,检查碰撞检测我传的参数是多边形每个顶点转化成舞台坐标后的顶点坐标,这样参数简单,不过后面发现,如果物体每一帧都在移动的话,这个每次都要循环遍历并计算新顶点,于是干掉了,改成了传入坐标和局部顶点坐标。
        在取物体在四叉树中周围物体的时候,比如,A,B,C三个物体都在一个区域内,那么,A会取到,BC,B,会取到,AC,C会取到AB,这样就会有很多重复的判断,所以在取周围数据的时候,getChildArounds中加入了一个fetchSig的标记,来保证不会被重复计算。
        然后,做碰撞检测的时候,会先判断每个形状的包围盒进行粗略的检测,如果包围盒碰撞,在做进一步检测。这是比较通用的做法。不过有一个特殊情况,就是本身就是一个没旋转的矩形,他的包围盒和形状本身重合了,那么就不必做进一步检查了。

5、简单的使用说明         
      目录层级如下:
         微信截图_20151106175354.png
         通过名字应该就很容易看出来了。
         首先说一下碰撞检测的库,都在sat文件夹下,包括三个文件SAT.ts,SAT_SIMPLE.ts和ConvxCal.ts
第二个其实就是第一个文件的简化版,第三个文件是做凹多边形分解的。
碰撞检测的使用方法很简单,直接用                       SAT.sat(pos1:egret.Point,pos2:egret.Point,p1:Array<any>,p2:Array<any>,iscircle1:boolean=false,iscircle2:boolean=false):boolean
就可以了。前两个参数是两个多边形的坐标。然后是两个多边形的顶点坐标。这里可以是二维数组,主要用于凹多边形分解后的多个凸多边形顶点坐标。最后两个参数为是否为圆形。

四叉树使用方法:
四叉树的部分都在quadtree这个目录下。其中,需要加入四叉树的对象需要实现QuadChild这个接口。
使用时,先new一个四叉树的对象(根节点,下面这个变量也是调用的这个对象)


QuadTree:参数分别代表,这是第0个位置,层级为0,父节点为空,以及该节点的范围:
var _quadTree = new QTree.QuadTree(0,0,null,[0,0,this.width,this.height]);

当对象位置发生变化时,只需要调用下面这个函数即可,这个函数包含了对象的添加和修正:
this._quadTree.matchToQuadTree(p)

然后使用这个函数来删除节点:
this._quadTree.removeFromeTree(p)

这个是用来获取某个对象周围节点的函数,其中的sigmark就是前面说的用来避免重复判断的参数,如果没这个需求可以直接修改源码把这部分去掉:
this._quadTree.getArounds(p,szarounds,sigmark),

这个是用来清空四叉树的函数:
this._quadTree.clearTree();

这个可以取出四叉树分割信息:
this._quadTree.getTreeBoundInfo(szbounds);

最后附上源码地址,如果哪位朋友有什么意见或建议,非常欢迎您能提出来,一起交流学习~
源码地址:源码Coding链接

最后,这是个人微信公众号,欢迎大家关注哈,内置逗比智能机器人
qrcode_for_gh_5518eebd0683_430.jpg
        



















参与人数 2银子 +20 收起 理由
cast099 + 10 赞一个!
xsstomy + 10 很给力!

查看全部评分

分享到 :
30 人收藏

33 个回复

倒序浏览
xsstomy  渐入佳境 | 2015-11-5 17:51:22
原理讲的很赞。
感觉还需要一篇文章来详细的介绍在代码的使用就更赞了。
csujin  圆转纯熟 | 2015-11-5 18:12:31
xsstomy 发表于 2015-11-5 17:51
原理讲的很赞。
感觉还需要一篇文章来详细的介绍在代码的使用就更赞了。 ...

是我疏忽了,先补充了一个简单的使用说明
xsstomy  渐入佳境 | 2015-11-5 18:22:27
csujin 发表于 2015-11-5 18:12
是我疏忽了,先补充了一个简单的使用说明

赞,真效率
tnewbie  登堂入室 | 2015-11-6 09:57:33
不明觉厉~顶一下
cy3502398  登堂入室 | 2015-11-6 13:02:47
city  初窥堂奥 | 2015-11-6 13:46:33
老牛掰了!赶紧顶!d=====( ̄▽ ̄*)b
culture  登堂入室 | 2015-11-7 16:34:49
很赞的一个实验碰撞
ink  初窥堂奥 | 2015-11-9 11:51:06
真棒的帖子,再写的教程就更好啦
csujin  圆转纯熟 | 2015-11-10 21:50:06
以后得空了写个详细的,现在被公司的项目搞得焦头烂额
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|京网文[2014]0791-191号|京ICP证150115号|Egret社区 ( 京ICP备14025619号 )

Powered by Discuz! X3.4 © 2001-2019 Comsenz Inc.

返回顶部