c# - A*探路者障碍物碰撞问题

Question

我正在与一个机器人进行一个项目，该机器人必须找到通往物体的路，并在前往它必须拾取的物体时避开一些障碍物。

问题在于机器人和机器人需要拾取的物体在探路者中都是一个像素宽。实际上，它们要大得多。通常 A* 探路者选择将路线放置在障碍物的边缘，有时会使其与障碍物发生碰撞，我们不希望这样做。

我尝试在障碍物上添加更多不可步行的场地，但效果并不总是很好。它仍然与障碍物发生碰撞，还增加了太多不允许它行走的点，导致它没有可以运行的路径。

你对如何解决这个问题有什么建议吗？

编辑：

所以我按照贾斯汀 L 的建议做了，在障碍物周围增加了很多成本，导致以下结果：没有路径的网格 http://sogaard.us/uploades/1_grid_no_path.png

在这里你可以看到障碍物周围的成本，最初中间的两个障碍物应该看起来就像角落里的那些，但是在运行我们的探路者之后，成本似乎被覆盖了：

上图显示了图片上发现的东西。

这是我们之前遇到的问题也是遇到障碍的路径。

还有一张带有路径的成本图的图片。

所以我觉得奇怪的是为什么 A* 探路者会压倒这些非常高的现场成本。

是否会在使用当前字段评估打开列表中的节点以查看当前字段路径是否比打开列表中的路径短时？

这是我用于探路者的代码：

Pathfinder.cs： http: //pastebin.org/343774

score 3 · Accepted Answer

您是否考虑过为物体附近的像素添加梯度成本？

也许像线性渐变一样简单：

C = -mx + b

其中 x 是到最近对象的距离，b 是边界外的成本，m 是成本消失的速率。当然，如果 C 为负数，则应设置为 0。

也许是一个简单的双曲线衰变

C = b/x

其中 b 再次是边界外的期望成本。一旦达到某个低点，就会截止到 0。

或者，您可以使用指数衰减

C = k e^(-hx)

其中 k 是比例常数，h 是衰减率。同样，有一个截止是聪明的。

第二个建议

我从未将 A* 应用于像素映射地图；几乎总是，瓷砖。

您可以尝试大幅降低图块的“分辨率”吗？可能每 10×10 或 20×20 的像素集有一个图块；瓦片的成本是瓦片中像素的最高成本。

此外，您可以尝试降低用于 A* 的最短距离启发式算法的价值。

score 3 · Accepted Answer

考虑到机器人的大小，您可以尝试扩大障碍物。您可以绕过障碍物的角落以解决阻塞问题。然后，填充的间隙太小，机器人无论如何都无法挤过。

score 2 · Accepted Answer

我已经做了一个这样的物理机器人。我的解决方案是，每当需要左右转弯时，就向后退一步。

红线是我理解你的问题。黑线是我为解决问题所做的。机器人可以直接向后移动一步，然后右转。