0

为了阐明这个目的,想象一个二维游戏,其中玩家控制一个可以被赋予任意速度的小精灵。它仅受重力作用。它最初位于一个横跨屏幕底部大部分的大平台上,在它上方一小段距离是另一个小得多的平台。如果精灵直接向上跳跃,它将能够从平台底部向上穿过,在其上方移动一段时间,然后下降并降落在上方平台的顶部。它可以从底部向上穿过,但不能从顶部向下穿过。

可以通过将屏幕上对象的每个实体边缘视为可以从右侧、左侧或两者穿过的矢量来做到这一点;在这个例子中,你需要一个边缘用于主基础平台的顶部(如果它从右上角指向左角,它将从右侧不透水),另一个用于较小平台的顶部,还有更多对于精灵(四个,如果它是一个小矩形)。如果一个点从错误的方式穿过边缘,它会向碰撞解决算法发送一个信号,以确保该点不会这样做。

这一切都很好,唯一的问题是它不是很有效。使用传统的碰撞检测机制,正方形是一个对象。如果你有一个n 个方块的列表来测试它们之间的碰撞,你必须运行 - 最多;大多数方法都会缩小这个数字——n平方碰撞测试。使用点-边法,每个正方形大约有四个边,每个边都有两个要测试的端点。这意味着对于n 个正方形,您将运行大约 (8 n ) 个平方碰撞测试。碰撞测试次数增加 64 倍;这太可怕了。

那么,几乎有没有任何广泛使用或更被接受的碰撞检测方法可以完成与点边缘方法相同的事情,但不会过度负担计算机的处理能力?请注意,这仅适用于 2D;它的目的是让事物层来表示一种轴内,而 3D 完全能够表示空间的所有三个维度并且不需要增强。

4

1 回答 1

0

这通常使用边界框的四叉树来完成。树的每个节点都有包围其直接子节点的边界。对于n 个节点,您最多需要k log ( n ) 比较。这是二维的二分搜索。

请注意,边界框不一定与您的正方形完全对应。它们是网格对齐的,用于通过范围比较进行廉价命中测试。

一旦你命中了一个原子的边界框,就对原子进行一次完整的命中测试。

这种方法最常与多边形命中测试结合使用,这对于具有多边的多边形来说非常昂贵(不要称它们为复杂多边形,复杂多边形是与相交边“扭曲”的多边形)。

于 2014-01-30T02:20:53.727 回答