是否有一种算法可以为避障机器人找到自由 space 中的最短路径？
Is there an algorithm to find the shortest path in a free space for an obstacle avoidance robot?
考虑机器人必须在非网格状平面中从一个点行进到另一个点。如果有森林之类的东西，我将如何找到最短路径？我知道网格可以使用 A* 算法。但是我正在努力实现的另一个例子是僵尸，它对地层有很好的了解，试图找到它到人类的最短路径。
如果您做出一些简单的假设，您可以将其简化为更易于处理的内容：robot/zombie 是一个点。
这是为了避免检查您是否适合等事情。如果 robot/zombie 是一个圆圈，您可以通过将障碍物的所有边缘按圆圈的半径向对象外部移动来使所有其他对象 'fatter' 。如果 robot/zombie 是一个矩形，你仍然可以将边缘推出，但使用立方体尺寸来做到这一点，但如果矩形应该旋转，这就不起作用了。
一旦你试图找到一个点的路径，它就会变得更简单。将 'fat' 多边形障碍物的每个顶点转换为图中的一个节点，并将其连接到直接可见的每个其他节点（不穿过某些障碍物）。如果你在 3d 中，你需要考虑边缘，问题变得有点乏味。
一旦你有了图表，做 A*/Dijkstra/whatever 就可以解决你的问题。
如果你想要真正精确的结果，如果你的 robot/combie 是一个圆，你需要小心转角，因为转过转角会变成在弧段上移动。如果你是 运行 和 game/simulation 除了非常薄的障碍物和相对较大的 circles/robots/zombies.
之外，差异不太可能可见
为了提高性能，如果设置是静态的，您可以预先计算图形。此外，节点的数量取决于障碍物的顶点数量，因此对于 path-finding。
可能值得 运行 较低质量的对象
考虑机器人必须在非网格状平面中从一个点行进到另一个点。如果有森林之类的东西，我将如何找到最短路径？我知道网格可以使用 A* 算法。但是我正在努力实现的另一个例子是僵尸，它对地层有很好的了解，试图找到它到人类的最短路径。
如果您做出一些简单的假设，您可以将其简化为更易于处理的内容：robot/zombie 是一个点。
这是为了避免检查您是否适合等事情。如果 robot/zombie 是一个圆圈，您可以通过将障碍物的所有边缘按圆圈的半径向对象外部移动来使所有其他对象 'fatter' 。如果 robot/zombie 是一个矩形，你仍然可以将边缘推出，但使用立方体尺寸来做到这一点，但如果矩形应该旋转，这就不起作用了。
一旦你试图找到一个点的路径，它就会变得更简单。将 'fat' 多边形障碍物的每个顶点转换为图中的一个节点，并将其连接到直接可见的每个其他节点（不穿过某些障碍物）。如果你在 3d 中，你需要考虑边缘，问题变得有点乏味。
一旦你有了图表，做 A*/Dijkstra/whatever 就可以解决你的问题。
如果你想要真正精确的结果，如果你的 robot/combie 是一个圆，你需要小心转角，因为转过转角会变成在弧段上移动。如果你是 运行 和 game/simulation 除了非常薄的障碍物和相对较大的 circles/robots/zombies.
之外，差异不太可能可见为了提高性能，如果设置是静态的，您可以预先计算图形。此外，节点的数量取决于障碍物的顶点数量，因此对于 path-finding。
可能值得 运行 较低质量的对象