logo标签列表

如何在Bullet中找到避免碰撞的光线投射位置？

c++algorithmpath-findingbulletraycasting
7
假设我们有一个在点A的物体。它想知道是否能够移动到点B。由于速度受限，因此它只能一步一步地移动。它沿着它移动的方向投射出一条光线。光线与物体碰撞并被我们检测到。如何安全地通过我们的光线（避免碰撞）？
顺便问一下，在物体投射的情况下，是否有办法使这样的事情起作用？它是否像简单的光线投射那样快？
是否有一种方法可以找到最优路径？
它是一个要避免的对象还是任意数量的对象？它在平面空间还是三维空间中？当A在路上时，障碍物是否移动？ - s.bandara
逃逸选择的成功衡量标准是什么？ - argentage
需要避免的是一个对象还是任意数量的对象？ 是 - 10k个对象，三维空间。当A在路上时，障碍物是否会移动？ 不会。 - myWallJSON
逃脱选择的成功是由什么衡量的？在（物体）射线投射中，给定步长距离内不应与任何障碍物发生碰撞。 - myWallJSON
5个回答
10
您所询问的实际上是一个寻路问题，更具体地说，是“任意角度寻路问题”。
如果您可以将障碍物的边缘限制在网格内，那么一个流行的解决方案就是在该网格上使用A*算法，然后应用路径平滑。然而，现在有一种算法叫做Theta*，它比路径平滑更简单易懂，并且能够获得更好的结果。

Theta* vs. path smoothing

这里有一篇很好的文章介绍了Theta*算法（我从中偷走了上面的图片）点击这里查看

如果您无法将障碍物限制在网格内，您需要为地图生成导航网格：

Navigation mesh

有很多方法可以做到这一点，复杂程度不同；例如，请参见这里、这里或这里。快速的谷歌搜索也会找到很多可用于为您完成此操作的库，例如这个或这个。

3
一种方法是使用绳索，或者多个绳索，其中一个绳索由几个点线性连接而成。您可以在空间中随机初始化这些点的位置，但第一个点是A的初始位置，最后一个点是A的最终位置。
最初，绳索将是一条非常糟糕的路径。为了进行优化，沿着能量梯度移动这些点。在您的情况下，能量函数非常简单，即绳索的总长度。
这并不是一个新的想法，但在计算机视觉中用于检测对象的边界，尽管能量函数要复杂得多。然而，可以查看“蛇”来了解如何移动每个点，给出其两个邻居：http://en.wikipedia.org/wiki/Snake_(computer_vision 然而，在您的情况下，仅从其邻居施加的力推导出每个点的方向就足够了。
你的问题是一个受限制的问题，需要考虑碰撞。我建议采用 @paddy 的想法，使用凸包或者每个物体都用一个球来解决问题。在后一种情况下，不要将一个点移动到距离B的距离小于A半径加上B半径再加上一个容错因子的位置，因为你没有无限数量的点。
一个有效的解决方案要求任何相邻点之间的最长距离小于一个阈值，否则两点之间的连线会与障碍物相交。
绳索/蛇快吗？（比如在Core i7上，有10,000个简单的盒子和金字塔物体随机运动） - myWallJSON
如果您计划将10,000个对象的路径考虑为障碍物，我恐怕这种方法对您来说可能不太适用。 - s.bandara
2

让我们从一个简单的方法开始...

如果只涉及一个对象，您可以计算障碍物所有顶点、起点和终点的凸包。然后，沿着凸包顺时针和逆时针遍历两个方向以从A到B。选择最短路径。

这会有些复杂，因为您要移动的形状不仅仅是一个点。您不能盲目地移动它的中心，否则它就会碰撞。当它经过一个顶点时，情况变得更加复杂，因为您必须让对象的一个边缘与障碍物的顶点紧贴在一起。

但希望这能给您提供一个思考的想法，这并不难理解。

我有10k个物体，它们都在移动...并且都不应该发生碰撞并保持速度... - myWallJSON
0

我制作了这张图片来表达我的想法，以便到达B点的目标。 图像中的对象： 深蓝色点代表物体。红线是障碍物。灰色点和线是可以到达的区域。紫色箭头是指向B点的方向。物体的灰色线是可见度范围。 理解图像： 物体将具有一定的可见度范围。这是一个二维情况，因此我假设可见度范围为180度。（人类可见度范围请参考http://en.wikipedia.org/wiki/Human_eye#Field_of_view）物体将使用声纳的思想来测量距离。借助声纳，物体可以找出它可以到达的区域。使用回溯法，物体可以找到到达目标的方法。如果没有路可走，物体必须改变其可见度范围。
0

从一个角度来看，这可以看作是一个阴影投射问题。将A作为“光源”，然后决定场景中每个点是否在阴影中。那些不在阴影中的点可以通过从A发出的光线访问。其他区域则不能。如果您发现B处于阴影中，则只需找到场景中最近的处于光照中的点。

如果您将此问题离散化为“像素”，则上述方法在大量计算机图形学文献中有非常著名的解决方案，用于阴影渲染。例如，您可以使用Shadow Map将每个像素涂上布尔标志，指示它是否在阴影中。查找最近的亮像素只需要在B周围逐渐扩大的同心圆中进行简单搜索即可。这两个操作都可以通过利用GPU硬件而变得极其快速。

另外一点：您可以将一般的对象路径查找问题视为点路径问题。秘诀是使用Minkowski差异适当地“增加”障碍物的大小。例如，请参见这项关于机器人路径规划的工作。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接