标签: collision-detection

有人可以帮我理解碰撞检测在JS中是如何工作的吗？我不能使用jQuery或gameQuery - 已经使用原型 - 所以,我正在寻找一些非常简单的东西.不要求完整的解决方案,只需指出正确的方向.

让我们说:

<div id="ball"></div>
and 
<div id="someobject0"></div>

现在球正在移动(任何方向)."Someobject"(0-X)已经预先定义,其中有20-60个随机定位如下:

#someobject {position: absolute; top: RNDpx; left: RNDpx;} 

我可以创建一个带有"someobject(X)"位置的数组,并在"ball"移动时测试碰撞...类似于:

for(var c=0; c<objposArray.length; c++){
........ and code to check ball's current position vs all objects one by one....
}

但我想这将是一个"noob"解决方案,它看起来很慢.有更好的吗？

我糊涂了.好吧不要混淆,不要想做6个测试程序,看看哪个算法最好.所以我想我会问我在这里的专家朋友给我带来他们经验的好处.

该场景是一个3d场景,与其内部对象的大小相比,可能面积相当大.场景中可能存在数千个对象.物体的大小从十分之一到大约10个单位不等,但不大(或更小).对象倾向于聚集在一起,但这些聚类可能会出现在场景中的任何位置.所有物体都是动态的,动人的.集群倾向于一起移动,但是当它们发生时,它们的速度可能不会一直相同.还需要考虑静态几何.虽然有大量的动态对象,但场景中也有一些静态对象(静态对象往往比动态对象大一到两个数量级).

现在,我想要的是一个空间数据结构,用于有效地对场景中的所有项目执行碰撞检测.如果算法也支持可见性查询,那么对于渲染管道来说会很棒.为简单起见,假设此处的碰撞检测是宽相的(即所有动态对象都是完美的球体).

所以,在我的研究中,我可以使用以下方法之一:

(1)八叉树(2)松散八叉树(3)线性八叉树(+松散)(4)KD树(5)BSP树(6)哈希

到目前为止(6)是我尝试过的唯一一个.它实际上是在速度方面完全高超(8192项碰撞下1ms的检查我的系统上),如果场景中的对象是平均均匀地分布.如果所有物体都被卷入一个较小的区域,这不是一个好的算法,我想这是可能的.

有没有人对使用哪一个有所了解,或者我可以用来加快速度的任何技巧？我想无论发生什么,我都可以使用单独的BSP树作为静态几何体.我想动态的"领域"是我最关心的问题.注意:没有CUDA,这只是CPU:p.

谢谢

编辑:好的,多亏了Floris,我发现了更多关于AABB Trees的信息.这里有关于GameDev的旧讨论:http://www.gamedev.net/topic/308665-aabb-tree---wheres-the-poly-o_o/ .看起来是一个很好的妥协.

最终编辑:决定不重新发明轮子.子弹物理库可能会为我做所有这些(它有AABB树,也可能非常优化).

我正在使用three.js.

我的场景中有两个网格几何体.

如果这些几何形状相交(或会相交,如果翻译)我想这种情况作为碰撞.

如何使用three.js执行碰撞检测？如果three.js没有碰撞检测设施,是否还有其他库可以与three.js结合使用？

嗨,我正在用Java制作体素游戏,在研究我需要学习的所有不同的东西时,我注意到很多游戏都使用AABB进行碰撞检测.然后我记得在Minecraft中也看到了AABB.但是,当我谷歌AABB是什么时,它只提出了其他人的代码,或者历史书中的某些组织.Stackoverflow,什么是AABB？

我写了一个简单的物理建模器,它允许我在屏幕周围弹跳球.您可以单击并拖动以启动球,或者您可以一次生成数百个球并观察它们彼此交互.

alt text http://i41.tinypic.com/2zr0oic.png
[链接到更大的版本]

这是一个很有趣的小程序,如果可以的话,我想进一步研究它.我知道他们说早熟优化是所有邪恶的根源,但我开始遇到实际的性能障碍,我想知道是否有任何有游戏/模拟器开发经验的人可以帮助我.

问题:

现在,如果你添加太多球(我的机器上似乎无法处理超过800个),我的程序就会窒息.如果这样做,模拟不再现实,并且所有球在底部彼此重叠.

问题在于碰撞检测.在最天真的情况下,碰撞检测是O(N ^ 2)问题.每个球都会检查每一个球.这很快就会导致性能下降(即使在100个球之后,你也会在每个循环周期进行10k次碰撞检查).

如果你看这里,你可以看到我添加了几百个球的截图.模拟器无法跟上,它们开始相互重叠.

alt text http://i41.tinypic.com/2nsnuqd.png
[链接到更大的版本]

目前,我通过寻找重叠球来检测碰撞.如果我找到两个重叠的球,我将它们按最小平移距离(MTD)分开,或将它们分开.然后,我使用一个简单的物理方程来调整它们的脉冲矢量,然后在碰撞后它们向不同的方向移动.

它的效果很好,除非有太多的球,最小的平移距离变得明显.它们开始大量重叠并且不断地在底部互相挤压.我越是"增加"引力就越糟糕.它们上的压力增加,它们被压缩/相互重叠的量增加.

再说一次,我没有问题,直到我击中了相当数量的N球.

当前优化方法:

碰撞检测 -
扫描和修剪 - (又称排序和扫描)

我在我的球上使用插入排序,每个循环沿x轴循环.由于插入排序的性质,我可以利用我的模拟器的时间一致性.框架到框架,球的位置只是稍微改变,因此排序没有太多工作要做.这使得线性分类分摊运行时间为O(N)或线性而不是其平均运行时间O(N ^ 2).

由于球是排序的,我在检查碰撞之前在第二个循环中做了几次预检查.现在我只需要检查彼此附近的球(因为它们沿着x轴排序),并且当我检查球与另一个球的xmin大于当前球的xmax时,我会突破第二个循环.所以它跳过了成千上万的支票.

当我实现这一点时,它带来了巨大的速度提升.但是,我仍然希望能够处理超过600-800个球.我已经阅读过物理引擎,可以轻松地同时处理10k个物体之间的碰撞检测,所以我想我可以通过一点点工作达到1-2k.

在运行了一个分析器之后,碰巧检测器占用了大约55%的时间,而渲染器占用了大约45%.所以,这是我最昂贵的两个成本.

题:

你能想到任何更好的算法或技术,让我的模拟器能够处理更多的球吗？

相关守则:

整个项目:

svn checkout http://simucal-projects.googlecode.com/svn/ballbounce/trunk/

或者,单击此处在浏览器中手动浏览文件.

感兴趣的部分:

• Pastebin:checkCollisions() - w/Sweep和Prune
• Pastebin:resolveCollision() - 如果仍未通过Sweep和Prune删除,则进行昂贵的真正冲突检查和解决.
• Pastebin:render() - 单独渲染占用了大约45%的时间.

我正在尝试制作一个游戏,玩家必须在游戏板上从头到尾找到自己的方式.![游戏板] [1]

如你所见,这个游戏板包含一堆红色的圆形障碍物.为了赢得比赛,玩家必须移除最少量的障碍物.所以我的问题是,我如何以编程方式找出要移除的最小障碍物,以释放路径？自由路径将被视为之间的空间,圆圈不重叠且不接触.

所以我真正需要的是要移除的最小圆圈量,我不需要实际的路径.是否有捷径可寻？

并且为了补充对该游戏板的理解,每个圆圈具有相同的半径,并且受到黑线的限制.

也没有必要沿直线移动.

我将开发一个二维球类游戏,其中两个球(圆圈)碰撞.现在我遇到了确定碰撞点的问题(事实上,确定它们是否在x轴/ y轴上碰撞).我知道当2个球的y坐标之间的差异大于x坐标差异时,它们会在y轴上发生碰撞,否则它们会在x轴上发生碰撞.我的想法是否正确？我在游戏中实现了这个功能.通常它运作良好,但有时,它失败了.谁能告诉我我的想法是否正确？如果没有,那么为什么,还有更好的方法吗？

通过x轴上的碰撞,我的意思是圆的第1,第4,第5或第8个八分圆,y轴表示圆的第2,第3,第6或第7个八分圆.

提前致谢!

给出2组积分

((x1,y1,z1),(x2,y2,z2),(x3,y3,z3))和

((p1,q1,r1),(p2,q2,r2),(p3,q3,r3))各自在3D空间中形成三角形.

你怎么知道这些三角形是否相交？

该问题的一个显而易见的解决方案是找到由每个三角形形成的平面的方程.如果平面是平行的,则它们不相交.

否则,使用这些平面的法向矢量找出由这些平面的交点形成的线的方程.

现在,如果该线位于两个三角形区域中,则这两个三角形相交,否则不相交.

trianglesIntersect(Triangle T1, Triangle T2)
{
   if(trianglesOnParallelPlanes(T1, T2))
   {
      return false
   }
   Line L1 = lineFromPlanes(planeFromTriangle(T1), planeFromTriangle(T2))
   if(lineOnTriangle(T1, L1) AND lineOnTriangle(T2, L1))
   {
      return true
   }
   return false
}

鉴于我知道如何编写上述函数,我应该考虑使用trianglesIntersect的其他实现吗？

是否有更快的算法来解决这个问题？

我已经尝试搜索一个javascript函数,它将检测两条线是否相互交叉.

该函数将获取每一行的两个起始端点的x,y值(我们称之为A行和B行).

如果相交则返回true,否则返回false.

功能示例.如果答案使用矢量对象,我很高兴.

Function isIntersect (lineAp1x, lineAp1y, lineAp2x, lineAp2y, lineBp1x, lineBp1y, lineBp2x, lineBp2y) 
{

    // JavaScript line intersecting test here. 

}

一些背景信息:这段代码是我想在html5画布中制作的游戏,也是我碰撞检测的一部分.

我有一个应用程序,我需要在屏幕上随机移动一些对象,他们不能互相撞击.我正在寻找一种算法,它允许我生成不会产生冲突的路径并且可以无限期地继续(即:对象一直移动直到用户驱动的事件将它们从程序中移除).

我不是游戏程序员,但我认为这看起来像AI问题,你们可能会闭着眼睛解决它.从我读过的内容来看,A*似乎是推荐的'基本理念',但我真的不想在没有确认的情况下投入大量时间.

任何人都可以对方法有所了解吗？反重力运动可能吗？

1. 如果这很重要,这将在iOS上实现
2. 需要在每个路径的末尾生成新路径
3. 没有可见的'网格'.2D空间中的运动完全免费
4. 物体是在屏幕上走动直到它们被杀死的昆虫