假设我们在 A 点有一个物体。它想知道它是否可以移动到 B 点。它的速度有限，所以它只能一步一步地移动。它向其移动的方向投射光线。射线与物体碰撞，我们检测到它。如何获得一种安全地通过我们的光线（避免碰撞）的方法？
顺便说一句，有没有办法在对象投射的情况下使这种事情起作用，它会像简单的光线投射一样/几乎快吗？
有没有办法在一些不同的路径中找到最优的？
问问题
1660 次
5 回答
10
您要问的实际上是一个寻路问题；更具体地说，它是“任意角度的寻路问题”。
如果您可以将障碍物的边缘限制为网格，那么一个流行的解决方案是在该网格上使用 A*，然后应用路径平滑。但是，有一种（相当新的）算法，它既更易于实现/理解，又比路径平滑提供更好的结果。它被称为Theta*。
有一篇很好的文章解释了 Theta*（我从中偷了上面的图片）here
如果您无法将障碍物限制在网格中，则必须为地图生成导航网格：
有很多方法可以做到这一点，复杂程度各不相同；例如，请参见此处、此处或此处。快速的 google 搜索还可以找到大量可用的库来为您执行此操作，例如this one或this one。
于 2013-01-14T22:44:12.417 回答
3
一种方法是使用一根绳子或几根绳子，其中一根绳子由几个线性连接的点组成。您可以在空间中的随机位置初始化点，但第一个点是A的初始位置，最后一个点是A的最终位置。
最初，绳索将是一条非常糟糕的路线。为了优化，沿着能量梯度移动点。在您的情况下，能量函数非常简单，即绳索的总长度。
这不是一个新想法，而是在计算机视觉中用于检测物体的边界，尽管能量函数要复杂得多。然而，看看“蛇”，让你知道如何在给定两个邻居的情况下移动每个点：http ://en.wikipedia.org/wiki/Snake_(computer_vision )
但是，在您的情况下，只需从其邻居施加的力中为每个点得出一个方向就可以了。
您的问题是您考虑碰撞的受限问题。我真的会在这里使用@paddy 的想法来使用凸包，甚至只是为每个对象使用一个球体。在后一种情况下，考虑到您没有无限数量的点，请不要将点移动到其与B的距离小于A的半径加上B的半径加上软糖因子的地方。
一个有效的解决方案要求任何邻居之间的最长距离小于一个阈值，否则，两点之间的连接线将与障碍物相交。
于 2013-01-14T21:40:05.167 回答
2
一个简单的方法如何开始......
如果这只是一个对象，您可以计算障碍物所有顶点的凸包，以及起点和终点。然后，您将通过顺时针和逆时针穿过船体来检查从 A 到 B 的两个方向。选择最短路径。
它有点复杂，因为你移动的形状不仅仅是一个点。你不能只是盲目地移动它的中心，否则它会发生碰撞。当它经过一个顶点时，它会变得更加复杂，因为您必须将对象的边缘擦过障碍物的顶点。
但希望这能给你一个思考的想法，这在概念上并不难理解。
于 2013-01-14T21:30:03.070 回答
0
看待这个问题的一种方法是作为阴影投射问题。制作A“光源”，然后决定场景中的每个点是否在阴影中。那些不在阴影中的人可以通过来自 的光线到达A。其他地区则不然。如果你发现B在阴影中，那么你只需要找到场景中最近的光照点。
如果将此问题离散为“像素”，则上述方法在有关阴影渲染的大量计算机图形学文献中具有非常著名的解决方案。例如，您可以使用阴影贴图为每个像素绘制一个布尔标志，该标志指示它是否处于阴影中。寻找最近的发光像素只是简单地搜索周围不断增长的同心圆B。通过利用 GPU 硬件，这两个操作都可以变得非常快。
另一个注意事项：您可以将一般对象路径查找问题视为点路径问题。秘诀是使用 Minkowski 差异“增加”适当数量的障碍。例如，参见关于机器人路径规划的这项工作。
于 2013-01-24T20:14:17.477 回答
0
我制作了这张图片来告诉我将物体到达 B 点的想法。图像中的物体：- 深蓝色的点代表物体。红线是障碍。灰色的点和线是可以到达的区域。紫色箭头是 B 点的方向。对象的灰色线是可见范围。理解图像：- 对象将具有一定的可见性。这是二维情况，所以我假设能见度为 180 度。（对于人类视野，请参阅http://en.wikipedia.org/wiki/Human_eye#Field_of_view) 物体将使用 SONAR 的思想来测量距离。在声纳的帮助下，物体可以找到它可以到达的区域。使用 BACKTRACKING，对象可以找到到达对象的路径。如果无路可走，则该对象必须更改其可见范围
于 2013-01-24T11:17:58.557 回答