GKObstacleGraph 如何找到最近的有效点？

Question

在用户想要通过鼠标导航或触摸到某些无法通过的地图的场景中。将点发送到 GKObstacleGRpah FindPath 时，它只是 returns 一个空数组。

我希望设备到达最近（或足够接近）的可通行点。

在 GKObstacleGraph 中找到最近的有效点的合适方法是什么？

我知道我可以获得 GKObstacle 所以我可以枚举它的顶点，我知道我的单位的位置...

但是...下一步是什么？

注意：我没有使用 GKAgengts。

Answer 1

这是我解决这个问题时的想法。可能有更简单的答案，但我还没有找到。

1.判断一个点是否有效。

为此，我实际上有每个障碍的 CGPath 表示。我从 PhysicsEditor 导出路径，然后通过将它们转换为 CGPath 的自定义脚本加载它们。我总是将该 CGPath 与我从该路径创建的 GKObstacle 一起存储。最后，我可以调用 CGPathContainsPoint 来确定障碍物包含的点。如果为真，我知道该点无效。

2。一旦点无效，找出点击了哪个障碍物

使用#1 中的方法，我已经掌握了 CGPath 及其所属的障碍。

3。找到最近的顶点

现在我知道了障碍物，找到离移动的单位最近的顶点。我不会找到点击点的壁橱顶点，因为它可能在拐角处。相反，找出所需位置和单位之间的向量。然后，从所需位置通过顶点绘制一条不可见的线。我用这个等式找出线条交叉的位置。

   // 
    let k = ((end.y - start.y) * (hitPoint.x - start.x) - (end.x - start.x) * (hitPoint.y - start.y)) / ((end.y - start.y) * (end.y - start.y) + (end.x - start.x) * (end.x - start.x))
    let x4 = hitPoint.x - k * (end.y - start.y)
    let y4 = hitPoint.y + k * (end.x - start.x)
    let ret = float2(x: x4, y: y4)

4.按单位大小向移动单位偏移交点

知道路径与朝向单位的向量相交的位置，我们可以移动到交点 +（向量 * 单位大小）。

5.边缘案例

当你有两个障碍物相互接触，或者你有非常大的障碍物时，这会变得棘手。用户可能认为他们正在移动到地图的另一边，但该脚本将返回到可能在附近的壁橱有效点。因此，我放弃了所有的代码，我只是不允许你移动到无效的位置。出现红色 X 和嗡嗡声，提示用户 select 在地图上找到一个新的有效位置。

6.演示机器人

我可能是错的，但我依稀记得 Apple 的 DemoBots 具有类似的逻辑——它们可能也是一个很好的参考。

7.调试层

我花了很长时间才得到一个概念证明。我强烈建议在调试层上画线来验证您的逻辑。

GKObstacleGraph 如何找到最近的有效点？

GKObstacleGraph How to Find Closest Valid point?

path-finding

gameplay-kit