四叉树/基于网格的碰撞 – 将逻辑付诸行动

首先,我只是写了自己的游戏逻辑一段时间,所以我很抱歉,如果这看起来很简单。

我一直在阅读很多关于四叉树和基于网格的碰撞检测。 我理解逻辑 – 除非对象基本接近,否则基本上不检查碰撞。 但从来没有提到如何实际执行这一点。

我头脑中有一些可能的方法,但不知道哪一个是最好的

一般碰撞testing – 没有优化

for(var i:int = 0; i < objects.length; i++){ //find object A var objectA = objects[i]; for(var j:int = i + 1; j < objects.length; j++){ //find object B var objectB = objects[j]; if(objectA.collidesWith(objectB){ //handle collision logic } } 

存储邻居(方法1)但是如果我们想优化碰撞来只检查靠近的对象呢? 我们仍然遍历所有的对象,或者我们创建一个数组与近对象来检查?

 var objects:Array = new Array(); var neighbours:Array = new Array(); for(var i:int = 0; i < objects.length; i++){ //find object A var objectA = objects[i]; for(var j:int = i + 1; j < objects.length; j++){ //find object B var objectB = objects[j]; if(objectA.isNear(objectB){ neighbours.push(objectA, objectB); } } } //somewhere else for(i:int = 0; i < neighbours.length; i++){ //only check neighbours for(j:int = i + 1; j < neighbours.length; j++){ if(objectA.collidesWith(objectB){ //handle collision logic } } } 

循环所有的对象,但只检查邻居碰撞(方法3)另一种可能性是,我们仍然循环一切,但在testing碰撞之前检查对象是否靠近。

 for(var i:int = 0; i < objects.length; i++){ //find object A var objectA = objects[i]; for(var j:int = i + 1; j < objects.length; j++){ //find object B var objectB = objects[j]; if(objectA.isNear(objectB){ //they are near - check collision! if(objectA.collidesWith(objectB){ //handle collision logic } } } } 

将对象存储在瓦片数据中(方法3)使用基于瓦片的系统允许使用其他选项; 将特定图块上的对象存储在图块数据本身中。 检查对象是哪个瓦片周围的瓦片包含可能会碰撞的任何对象:

 var ObjectA; for(var i:int = 0; i < 4; i ++){ //check 4 surrounding tiles from object A if(Object.currentTile + surroundingTile[i] CONTAINS collidable object){ //check collision! if(objectA.collidesWith(surroundingTile.object){ //handle collision logic } } } 

我总是试图以现实世界为例。 如果我想比较具有相同颜色的物品,即使它们不匹配颜色(方法2,检查每个物品),检查每个整个物品也是不合逻辑的。 我可能会收集具有相同颜色的物品(彼此靠近的物品)并检查这些物品(方法1),而不是检查所有物品。

这不是一个适当的比较,因为在碰撞检查项目不断移动,所以顺序混合起来。 那什么让我困惑。

检查每个项目是否更高效,从而消除了继续生成邻居数组的压力。

或者是find邻居更有效率,因此不必循环太多的对象来检查碰撞?

不断改变每个瓷砖上的数据似乎非常密集,所以我不知道这是一个好主意..

我一直在考虑一个塔防游戏,如果物体在射击之前需要探测物体,那么塔需要探测物体。 检查所有物品似乎是愚蠢的,而在某些时候根本没有任何物体。

我为这个post道歉,总是无法解释自己!

您需要减less实际碰撞检查的次数。 是的,我知道很明显。 所以我们来详细说明一下:

您的第一个碰撞检查algorithm没有任何优化:一次运行多less次检查? 如果n是对象的数量,这将在n *(n-1)检查周围。 对于很多对象(> 100),这将是非常缓慢的。

你的邻居检查方法不会更快。 如果你的对象不是静态的并且移动了很多,你将需要为游戏循环中的每个对象创建这些邻居列表。 这实际上比第一个algorithm更糟糕,因为您正在执行n *(n-1)来构建邻居列表,然后检查每个对象是否与其邻居发生冲突。

你需要划分你的游戏空间。 让我们说你的游戏空间是400×400像素宽。 你可以将它分成4个子空间,每个子空间的大小为200×200,并检查每个对象是否属于哪个子空间(一个对象可以在多个子空间内)。 那么您只需要检查每个子空间中的对象是否与同一子空间中的其他对象发生冲突。

因此,运行时间成本将是:n用于构建4个子空间列表+(n / 4)*((n-1)/ 4),这比以前的运行时成本要好很多。 通过使子空间更小(例如50×50),可以进一步减less这种情况。

所以我们的algorithm现在看起来像这样:

 for each (object in objects) check into which subspace the object belongs for each (subspace in subspaces) for each (object in subspace) check object for collision with other objects in same subspace 

这有点类似于你的瓷砖数据的想法。 但子空间不需要与瓦片大小相同。

我们可以做最后一步,使用四叉树进一步优化。 设k是子空间的数量。 要构建空间对象列表,我们正在进行k * n个检查,如果您的游戏世界变大,将导致大量检查。

为了降低成本,我们使用四叉树。 四叉树是另一种划分我们游戏空间的方式。 游戏空间不是将我们的400×400空间划分成64个50×50子空间,并且检查每个对象当前在哪个子空间中的64个子空间,而是将游戏空间划分为游戏空间尺寸的一半(200×200)的四个子空间,更小的子空间(100×100),而子空间又被划分为50×50子空间。 这是我们的四叉树。

现在,如果我们想知道对象属于哪个50×50子空间,我们检查它属于哪个200×200子空间。 然后,我们在四叉树的深处进行一级检查,并检查刚刚find的200×200子空间内的4个100×100子空间。 直到我们知道对象属于哪个50×50的子空间。 那么现在需要多less支票? 4为四叉树的每个级别(记住一个对象可以在两个子空间的边缘)。 所以我们需要4 * 3的检查来分配一个对象到正确的50×50子空间。 比64支票好很多。

因此,我们的四叉树algorithm需要4 * 3 * n检查来构建子空间列表,然后像k *(n / k)检查来检查每个对象的冲突。