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

Question

假设我们在A点有一个物体.它想知道它是否可以移动到B点.它的速度有限,所以它只能一步一步地移动.它向正在移动的方向投射光线.Ray与一个对象碰撞,我们检测到它.如何安全地传递我们的光线(避免碰撞)？

顺便说一句,有没有办法让这种东西在对象投射的情况下工作,它会像简单的光线投射一样快/近吗？

有没有办法在某些vay路径中找到最优？

Answer 1

你所询问的实际上是一个寻路问题; 更具体地说,这是"任意角度寻路问题".

如果您可以将障碍物的边缘限制为网格,那么流行的解决方案是在该网格上使用A*,然后应用路径平滑.但是,有一种(相当新近的)算法既可以更容易实现/理解,也可以提供比路径平滑更好的结果.它被称为Theta*.

有一个很好的文章,解释西塔*(从我偷了上面的图片)在这里

如果您不能将障碍限制在网格中,则必须为地图生成导航网格:

有许多方法可以做到这一点,具有不同的复杂性; 例如,在这里,这里或这里看到.快速谷歌搜索还会提供大量可用于此的库,例如这一个或这个.

Answer 2

从一个简单的方法开始怎么样......

如果这只是一个对象，您可以计算障碍物所有顶点的凸包，以及起点和终点。然后，您可以通过顺时针和逆时针穿过船体来检查从 A 到 B 的两个方向。选择最短路径。

它有点复杂，因为您移动的形状不仅仅是一个点。你不能盲目地移动它的中心，否则它会发生碰撞。当它移动经过顶点时，它会变得更加复杂，因为你必须将物体的边缘擦过障碍物的顶点。

但希望这能给你一个思考的想法，这在概念上并不难理解。