标签: collision-detection

重力游戏如何处理玩家,怪物,物体和地板等移动物体之间的关系？玩家是否经常"落入"地板并被反弹回来？

我发现的两种对碰撞作出反应的方法是将玩家移回到碰撞前的前一个位置,并在移动之前测试新位置以查看是否会导致碰撞,但我看不出这些中的任何一种可以处理一个向上升起并且需要能够提升玩家的平台.我从2D游戏设计的角度来看这个,但我想3D游戏设计中也会出现同样的问题.任何提示？我应该查看的任何参考文献？谢谢.

我想编写一个模拟许多粒子碰撞的小程序,首先从2D开始(我稍后将其扩展到3D),到(在3D中)模拟向Boltzmann分布的收敛,并且还看到分布如何在2D中演化.

我还没有开始编程,所以请不要问代码示例,这是一个相当普遍的问题,应该可以帮助我开始.这个问题背后的物理问题对我没有任何问题,而事实是我必须模拟至少200-500个粒子,以实现非常好的速度分布.我想实时做到这一点.

现在,对于每个时间步,我将首先更新所有粒子的位置,然后检查碰撞,以更新新的速度矢量.然而,这包括很多检查,因为我必须看看每个粒子是否与其他每个粒子发生碰撞.我发现这个帖子或多或少都是同一个问题,而且那里使用的方法也是我唯一能想到的.但是,我担心这不会在实时工作得很好,因为它会涉及太多的碰撞检查.

所以现在:即使这种方法在性能上有所提升(说得40fps),有人可以想办法避免不必要的碰撞检查吗？

我自己的想法是将板(或3D:空间)分成具有至少粒子直径的尺寸的正方形(立方体),并且如果两个粒子的中心在adjecent正方形内,则实现仅检查碰撞的方式在网格中......

我很乐意听到更多的想法,因为我想尽可能多地增加粒子数量,并且仍在进行实时计算/模拟.

编辑:所有碰撞都是纯粹的弹性碰撞,没有任何其他力量对粒子进行处理.我将实现的初始情况由用户选择的一些变量确定,以选择随机起始位置和速度.

EDIT2:我发现了粒子碰撞的模拟一个很好的和非常有益的纸在这里.希望它可以帮助一些对更深层次感兴趣的人.

您认为在2D环境中描述用于碰撞检测的算法或技术的最佳资源(书籍或网页)是什么？

我只是渴望学习不同的技术来制作更复杂,更高效的游戏.

我一直在研究这几个小时,但没有用.基本上我有

struct rectangle {
    int x, y, w, h;
};

rectangle player::RegionCoordinates() // Region Coord
{
    rectangle temp;
    temp.x = colRegion.x + coordinates.x;
    temp.w = colRegion.w;
    temp.y = colRegion.y + coordinates.y;
    temp.h = colRegion.h;

    return temp;
}

// Collision detect function
bool IsCollision (rectangle * r1, rectangle * r2)
{
    if (r1->x < r2->x + r2->w &&
        r1->x + r1->w > r2->x &&
        r1->y < r2->y + r2->h &&
        r1->y + r1->h > r2->y) 
        {
            return true;
        }
    return false; …

我想知道两个3D凸包（vs ）之间的碰撞位置的大概3D位置和 3D法线。 AB

括号中的CPU显示了我完成的程序所需的相对CPU时间。

第1部分：抢先体验（CPU 1％）

第一步，我使用一种非常便宜的算法- 分离轴定理。
例如，我将15轴用于2个多维数据集。（在实际情况下，形状会更复杂。）
如果至少有1个可以分开的轴，return "no-collide"。
否则，请执行下一部分。

第2部分：顶点与体积（CPU 10％）

• 检查-的每个顶点A是否在内部B。
• 检查-的每个顶点B是否在内部A。

第3部分：Edge vs Edge（CPU> 20％）

有一个奇怪的情况，例如https://gamedev.stackexchange.com/questions/75437/collision-detection-3d-rectangles-using-sat。我从那里偷了图像：

因此，我还需要edge vs edge。

• 对于每对A和B的边缘（12 * 12 = 144对），在找到边缘最近点A对的边缘B。检查顶点是否在内部B。
• （反之亦然）对于每对B＆A边，检查该顶点是否在内部A。

哇，这是很多计算。
但是，还没有结束。

问题

1. 报告的碰撞位置不太准确（左：当前，右：希望）：-

   

   为了解决这个问题，我考虑过要生成一个新的凸形= A intersect B。
   有一些免费的C ++库（例如OpenMesh），但是我认为它过于占用 CPU资源。
   请注意，我不需要准确无误。

2. 有时还会报告错误的正常状态（左：当前，右：希望）：-

   

   ^这个问题可能通过增加来解决边缘 …

如图所示

我绘制了一组轮廓(多边形)作为GL_LINE_STRIP.现在我想选择鼠标下的曲线(多边形)来删除,在3D中移动..等.

我想知道使用哪种方法:

1.使用OpenGL挑选和选择.(glRenderMode(GL_SELECT))

2.使用拾取射线检查手动碰撞检测,并检查射线是否在每个多边形内.

这在过去的几周里一直困扰着我.在这段时间里,我一直在网上进行研究,甚至在Borders的计算机部分读书,试图找到答案,但我没有太多运气.

我为侧卷轴视频游戏编写了2D级编辑器.现在我想把它变成一个游戏,我有一个可以跑步和跳跃探索关卡的玩家,类似于"马里奥".

真正给我带来麻烦的是碰撞响应(不是检测:我已经知道如何判断两个块是否发生碰撞).以下是我将要说明的一些场景,以便您可以看到我的问题(阴影块是地面,箭头是玩家的速度矢量,虚线是玩家的投影路径).

查看此碰撞响应方案图像:

http://dl.dropbox.com/u/12556943/collision_detection.jpg

假设情景(1)和(2)中的速度矢量相等(相同的方向和幅度).然而,在场景(1)中,玩家正在击中该区块的一侧,并且在场景(2)中,该玩家落在该区块的顶部.这使我得出结论,确定碰撞响应不仅取决于玩家的速度矢量,还取决于玩家相对于碰撞块的相对位置.这引出了我的第一个问题:知道速度矢量和玩家的相对位置,我如何确定玩家与该块碰撞的方向(左侧,右侧,顶部或底部)？

我遇到的另一个问题是如果玩家与同一帧中的多个块发生碰撞,如何确定碰撞响应.例如,假设在场景(3)中,玩家同时与这两个块碰撞.我假设我将不得不遍历玩家正在碰撞的每个区块并相应地调整每个区块的反应.总结一下,这是我的第二个问题:如果玩家与多个块碰撞,我该如何处理碰撞响应？

请注意,我从未透露过我正在编程的语言; 这是因为我更喜欢你不知道(不过是个人的,但是:).我对伪代码比对特定语言代码更感兴趣.

谢谢!

我刚刚在我正在开发的Android游戏中添加了一些计算代价昂贵的代码.有问题的代码是碰撞检测例程的集合,它们经常被调用(游戏循环的每次迭代)并且正在进行大量的计算.我觉得我的碰撞检测实现相当发达,而且我可以用Java编写它.

我一直在使用Traceview来分析代码,这个新的碰撞检测代码在某种程度上让我的游戏逻辑的持续时间翻了一番.这显然是一个令人担忧的问题,因为对于某些设备而言,这种性能打击可能会使我的游戏从可玩的状态变为无法玩的状态.

我一直在考虑不同的方法来优化这些代码,我想知道如果将代码移动到C++并使用JNI访问它,我是否会获得一些显着的性能节省？

以上问题是我主要关心的问题和我的问题.我已经确定以下两个原因是使用JNI的其他积极结果.但是,仅仅说服我将代码移植到C++是不够的.

• 这将使代码更清晰.由于大多数碰撞检测都是某种向量数学,因此能够使用重载运算符而不是在Java中使用更冗长的向量类更为清晰.

• 内存管理会更简单.你说比较简单吗？好吧,这是一款游戏,因此垃圾收集器运行不受欢迎,因为如果GC不断中断清理,GC最终可能会破坏游戏的性能.在CI中不必担心垃圾收集器,所以我可以避免使用临时静态变量在Java中做的所有丑陋的事情,并且只依赖于C++的旧旧堆栈内存

这问题可能是啰嗦,我想我已经涵盖了所有的观点.鉴于此信息,是否值得将我的代码从Java移植到C++并使用JNI访问它(出于提高性能的原因)？此外,有没有办法衡量或估计潜在的性能增益？

编辑:

所以我做到了.结果？从TraceView的角度来看,它的碰撞检测程序速度提高了6倍.

虽然到达那里并不容易.除了必须进行JNI舞蹈之外,我还必须进行一些我没想到的优化.主要是,使用直接分配的浮点缓冲区将数据从Java传递到本机.我最初的尝试只是使用一个float数组来保存有问题的数据,因为从Java到C++的转换更自然,但这真的很慢.直接缓冲完全侧向性能问题与java和本机之间的数组复制,并留下了6倍的凹凸.

另外,我只使用了Eigen数学库,而不是滚动我自己的矢量类.我不确定这会对性能有多大的影响,但至少,它为我节省了开发自己(效率较低)的矢量类的时间.

另一个经验教训是过度记录对性能不利(jic并不明显).

我知道如何检查一个圆是否要与一个正方形碰撞,我知道如何检测一个正方形是否即将与一个正方形碰撞,但我如何检测一个多边形是否即将与一个正方形碰撞？

或者更好的是,当多边形即将与多边形碰撞时.

或者更好的是,当由不直的线组成的形状与另一个相似的形状,多边形或圆/矩形碰撞时

是否有任何方法可以获得像素的形状可能占用的像素和另一个形状的像素将占用并检查它们中的任何一个是否相同？

我希望有一些解决方案不需要大量的形状特定计算.

我使用javascript和html5 canvas来做到这一点.

我的游戏碰撞检测系统有点问题.在游戏中有几个相互连接的结构.但是,当它们之间存在另一个结构时,它们不应该连接.

由于一些奇怪的原因,当它们后面有直接线的结构时,它有时无法连接到直接相邻的结构.很少会产生其他奇怪的联系.

图片:

应该连接红色标记的节点.

码:

public void drawConnections(Graphics g) {
    ArrayList<EnergyContainer> structurecopy = (ArrayList<EnergyContainer>) Mainclass.structures.clone(); //all structures in a list
    structurecopy.remove(this); //as we are member of the list
    structurecopy.removeIf(t -> (!hasStructureInRangeWithoutObstaclesInBetween(t))); 
    structurecopy.removeIf(t -> !t.receivesEnergyfromNeighbors()); //unimportant check if it is allowed to connect (its working)
    structurecopy.forEach(t -> drawConnectionTo(t, g)); //also works fine 
}

public boolean hasStructureInRangeWithoutObstaclesInBetween(Structure structureWhichShouldBeInRange) {
    // if in Range
    if (getRange() >= Math.hypot(structureWhichShouldBeInRange.getX() - getX(),
            structureWhichShouldBeInRange.getY() - getY())){ //checks if structure is in range
        ArrayList<EnergyContainer> structureclone = (ArrayList<EnergyContainer>) …