LOFTER-网易轻博

碰撞检测的基本原理

        一个游戏物体（Actor）由本体和包裹着它的碰撞结构构成。本体是任意的集合形状，而碰撞结构中的碰撞包围盒则是简单的图形，sgf-py目前支持矩形和圆形两种：

        AABB轴对齐包围盒和圆形包围盒

        一般在三维游戏中，有立方体，球体，胶囊体，任意凸体积，多边形汤（polygon soup或poly soup）等。确定它们是否碰撞，即判断它们是否相交或相接触，要涉及到立体解析几何的方法。

        在sgf-py中，（领域为2d），判断是否碰撞，只需要简单的解析几何知识就可以了。下面介绍sgf-py中的判断方法。注意一下方法是针对sgf-py中定义的坐标系统，即原点为左上角，x轴正方向右，y轴正方向向下

        1. 点是否包含于矩形中：

        这个比较简单：

            Rectangle.x + Rectangle.w > point.x > Rectangle.x and Rectangle.y < point.y < Rectangle.y + Rectangle.h

        2. 矩形与矩形是否相交：

        这个可以采用分离轴定理，事实上所有的2d图形都可以采用这种方法，这个定理的内容是：

        若能找出一条轴，两个凸形状在该轴上的投影不重叠，就能确定两个形状不相交。

        分离轴定律是方法之一，在框架中，我选择了另外一种方法即重心投影判断法，这个方法对于矩形来说比较好实现，原理是：

        两矩形重心的距离，分别在x，y方向上距离的两倍，小于等于他们在该方向上的边长之和，则可以说明这两个矩形相交

        代码如下：

def intersects(self, rect, oth) -> bool:
    if not isinstance(oth, Rectangle) :
        raise Exception("Param '{}' not a subclass of Shape::Rectangle".format(oth))
        center1 = rect.barycenter()  # 获取自身的重心坐标
    center2 = oth.barycenter()  # 获取要检测的重心坐标

    dist_x = abs(center1.x - center2.x)  # 重心位于x方向上的距离
    dist_y = abs(center1.y - center2.y)  # 重心位于y方向上的距离

    sum_x = rect.w + oth.w  # x方向上的边长之和
    sum_y = rect.h + oth.h  # y方向上的边长之和

    if dist_x * 2 <= sum_x and dist_y * 2 <= sum_y:
        return True
    return False

        3. 点是否包含于圆中：

        这个也比较简单：

        d = pow((point.x - self.x), 2) + pow((point.y - self.y), 2)
        return d <= self.squared_r

        4. 圆与圆的相交：

        这个也比较简单，判断两圆心的距离即可，但这里存在一个陷阱：

        就是距离s，一般求解距离s需要开平方，而计算机计算平方根需要消耗大量的运算资源，如果有大量的球体需要检测，则程序的运行速度必然会下降。所以一般会将|s| <= r1 + r2，改写成(|s|)^2 <= (r1 + r2)^2， 避免开方运算。

        5. 射线是否相交：

        这里的射线，有方向没有长度，或无限长，比如光线。严密的证明方法我参考了wiki百科的line-line intersection条目,里面介绍了两种方法:

         (x1, y1), (x2, y2)为直线L1上的任意两点，这里可取单位向量来表示射线，容易获取两点，(x3, y3)，(x4, y4)为直线L2上的任意两点，这里的两点不一定是线，也可以是某个物体的外轮廓的某条边（直线）等。

        方法一：交点p可以采用行列式表示为：

即：

但这种方法太复杂了，还有另外的方法，方法二：

        可以将这两条直线表示成一阶贝塞尔曲线（first degree Bézier curve）的形式：

其中的t和u的参数为：

如果0 < t < 1 并且 u > 0，则交点为：

其它情况则没有交点

以下是实现的代码：

def cast(self, a, b):
        x1 = a.x
        y1 = a.y
        x2 = b.x
        y2 = b.y

        x3 = self.pos.x
        y3 = self.pos.y
        x4 = self.pos.x + self.dir.x
        y4 = self.pos.y + self.dir.y
        dt = dtm2(x1 - x3, x3 - x4, y1 - y3, y3 - y4)
        du = dtm2(x1 - x2, x1 - x3, y1 - y2, y1 - y3)
        dd = dtm2(x1 - x2, x3 - x4, y1 - y2, y3 - y4)
        dd_val = dd.val()

    if dd_val == 0:
        return

    t = dt.val() / dd_val
        u = du.val() / dd_val

    if 0 < t < 1 and u > 0:
        return vec2(x1 + t * (x2 - x1), y1 + t * (y2 - y1))
    else:
        return

（dtm2为sgf-py中的二阶行列式类型）

QuadTree（四叉树）

        quadtree是一种用于解决大量物体碰撞减少检测量的方式，当然不仅仅可以用于碰撞检测，同时quadtree也可以用于二维图形分割等。三维空间中一般使用它的升级版，Octree（八叉树）

        在一般的常识下，检测一个物体是否与其他的物体发生了碰撞需要逐个检测例如有a,b,c三个物体，在一帧的时刻里检测它们是否发生了碰撞，需要进行双重的for循环，即时间复杂度为n方，如果有1000个物体，在每一帧的时间里即必须遍历1000x1000=1000000次，极大的影响处理速度。而QuadTree是为了解决这一问题的优秀方法之一。

        什么是QuadTree？

        QuadTree是一种树状数据结构，将一个平面分成四个块，比如二维坐标系统中的一，二，三，四象限，然后在每个象限的基础上递归的划分四个象限，以此类推，形成一个每个根节点都有四个子节点的树状结构。

        为什么QuadTree能简化碰撞检测？

        之前的遍历，问题就在于一个位置为(0, 0)的A物体在进行循环遍历时要同位置为(600, 600)的B物体进行检测，而A物体的大小也只不过是10x10，所以这个检测就显得没有必要，因为它们无论如何也不会相碰。

        QuadTree的基本思路也是这样，在碰撞检测的时候，A物体只与在它附近的若干物体检测，B物体也是一样，因为在附近的物体才是有可能碰撞的。

        用法：

        将物体插入QuadTree中，QuadTree的每一个节点都有一个container（容器），一旦插入量大于容器的容积，QuadTree便会在相应位置分离出四个子节点（在该象限划分四个象限），将过剩的元素存入相应的节点中。在遍历时只取到A物体所在的节点，与自身所在节点容器中的其它物体进行检测即可。

测试与效果

            1000个物体测试效果一

        1000个物体测试效果二